به دلیل اینکه این سوالات برای المپیاد کامپیوتر طراحی شده و محدودیت تست‌ها، امکان ارسال فقط با زبان سی‌پلاس‌پلاس ممکن است.

دبّه


  • محدودیت زمان: ۴ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • روز ۲ دوره ۳۰

«شرکت تولیدی دبّه‌ی آقای موز و دوستان» معروف به «شتدآمود» یکی از خوش‌نام‌ترین کارخانه‌های دبّه‌سازی است که همه ساله روز قبل از امتحانات عملی، از دبّه‌های جدیدش رونمایی می‌کند.

آقای موز اخیرا تصمیم گرفته کارخانه‌ی جدیدی در زمینه‌ی تولید رشته‌ها احداث کند. او می‌خواهد تا پیش از پایان امتحانات عملی رشته‌هایی بسازد و به دانش‌پژوهان هدیه دهد.

منظور از رشته، دنباله‌ای متشکّل از حروف کوچک انگلیسی است.

در ابتدا آقای موز باید به مغازه‌ی رشته‌فروشی برود و تعدادی رشته بخرد؛ سپس این رشته‌ها را به کارگرانش بدهد. کارگران کارخانه‌ی رشته‌سازی، می‌توانند پسوندی از هر رشته را حذف کنند و سپس رشته‌های باقی‌مانده را با ترتیب دلخواه پشت سر هم قرار دهند. در نهایت رشته‌ی حاصل را داخل کوره‌ی رشته‌پزی می‌گذارند تا این قطعات به یکدیگر متّصل شوند. دقّت کنید پسوندهایی که حذف می‌شوند می‌توانند تهی هم باشند، یعنی هیچ قسمتی از رشته حذف نشود.

مثلا اگر آقای موز دو رشته‌ی tanin، یک رشته‌ی qosxyz و یک رشته‌ی ehtemal به کارگرانش بدهد، آن‌ها می‌توانند با حذف پسوندی از هر رشته، چهار رشته‌ی qos، tan، tani و eh را بسازند و با پشت سر هم قرار دادن آن‌ها رشته‌ی qostantanieh را تولید کنند.

در مغازه‌ی رشته فروشی nn نوع رشته و از هر نوع رشته به تعداد نامحدود وجود دارد. این رشته‌ها را با t1,t2,,tnt_1, t_2, \cdots, t_n نمایش می‌دهیم. هزینه‌ی خرید هر یک از این رشته‌ها هم 11 ریال است.

هم‌چنین در دوره‌ی تابستانه(پاییزه؟) mm دانش‌پژوه وجود دارند؛ آقای موز رشته‌ی بزرگی(به طول LL) به نام SS دارد و به ازای mm زیررشته از SS که با [li,ri)[l_i, r_i) مشخّص می‌شوند(1im1 \le i \le m)، می‌خواهد رشته‌ای برابر با آن زیررشته تولید کند و به دانش‌پژوه iiام هدیه دهد. دقّت کنید حروف هر رشته به طول LL از چپ به راست با اعداد 00 تا L1L - 1 شماره‌گذاری می‌شوند و زیررشته‌ی [l,r)[l, r) نشان‌دهنده‌ی زیررشته‌ای است که از کنار هم قرار دادن حروف ll تا r1r - 1 آن رشته(به ترتیب) ایجاد می‌شود.

به آقای موز بگویید که کم‌ترین هزینه‌ی مورد نیاز برای تامین هدیه‌ی هر دانش‌پژوه چند ریال است.

ورودی🔗

در خط اول ورودی دو عدد nn و mm آمده است که به ترتیب تعداد رشته‌های داخل رشته‌فروشی و تعداد دانش‌پژوهان دوره‌ی تابستانه است.

در خط iiام از nn خط بعد، رشته‌ی tit_i آمده است. این رشته‌ها، رشته‌های موجود در مغازه‌ی رشته‌فروشی هستند.

پس از آن نیز رشته‌ی SS آمده است.

در خط iiام از mm خط بعد نیز دو عدد lil_i و rir_i آمده است که نشان‌دهنده‌ی بازه‌ی مربوط به هر دانش‌پژوه است.

1L,m300 0001 \le L, m \le 300\ 000 1n10 0001 \le n \le 10\ 000 0li<riL0 \le l_i < r_i \le L

مجموع طول tit_i ها نیز حداکثر 500 000500\ 000 است.

خروجی🔗

خروجی می‌بایست متشکّل از mm خط باشد. در iiامین خط، کم‌ترین هزینه‌ای که برای تولید رشته‌ی مربوط به دانش‌پژوه iiام نیاز است را چاپ کنید. هم‌چنین اگر این کار ممکن نیست، 1-1 چاپ کنید.

زیرمسئله‌ها🔗

زیرمسئله نمره محدودیت
۱ ۲۵ L500L \le 500
۲ ۲۵ m10m \le 10
۳ ۵۰ بدون محدودیت اضافی

مثال🔗

ورودی نمونه ۱🔗

3 13
ab
ac
aef
abaaceaef
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
1 2
6 9
5 9
4 9
Plain text

خروجی نمونه ۱🔗

1
1
2
3
3
-1
-1
-1
-1
-1
1
-1
-1
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.