میلاد وسواسی

رنگ بادکنک : سفید
محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۵۰ مگابایت

میلاد علاقه خاصی به اعداد دارد و می خواهد تعدادی از اعداد تمیز را قاب کند و به دیوار اتاقش بزند . از نظر میلاد عددی تمیز محسوب میشود که باقیمانده اش به هر کدام از اعداد اول تک رقمی ، برابر صفر باشد . میلاد که وقت حل کردن این سوالات بدیهی را ندارد این سوال را به شما واگذار می کند تا برایش حل کنید .

ورودی🔗

در تنها خط ورودی یک عدد X داده میشود $0 \le X \le 100000$

خروجی🔗

در تنها خط خروجی در صورت تمیز بودن x عبارت “tamiz” و در غیر این صورت عبارت "kasif" را چاپ کنید.

مثال🔗

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

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

tamiz

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

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

kasif

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

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

tamiz

+ رنگ بادکنک : صورتی ^_^ + محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۵۰ مگابایت ---------- میلاد و پرهام و آرمین رو میشناسید ؟! خوب اگر نمیشناسید هم زیاد مهم نیست. تنها چیزی که الان مهمه اینه که میلاد و دوستای فرز و شیطونش شنبه امتحان دارند. از آنجایی که میلاد و پرهام و آرمین تا به حال سر کلاس نرفته اند ، هیچی از درس نمیفهمند . اما جای شکرش باقیه که امتحان تستی ه ! امتحان ۳ گزینه ای هستش و جواب هر کدوم از سوال ها A یا B یا C هستش ! میلاد و پرهام و آرمین اصلا سوال ها رو نمیخونند و هر کدوم به صورت کاملا شانسی ، با الگو های زیر تو پاسخنامه جواب میدند . Milad : B , A , B , C , B , A , B , C , B , A , B , C , …… Parham : C , C , A , A , B , B , C , C , A , A , B , B , …. Armin : A , B , C , A , B , C , A , B , C , A , B , …… حالا ما به شما تعداد سوالات و جواب درست آن ها را میدهیم شما به ما بگویید بیشترین تعداد پاسخ درستی که میلاد ، آرمین و پرهام با استفاده از الگو های خودشون میدهند چنتاست و همچنین چه کسی(یا کسانی) بیشترین پاسخ درست را میدهند! # ورودی در خط اول یک عدد n به شما داده میشود که نشان دهنده تعداد سوال هاست. در خط بعدی یک رشته به طول n به شما داده میشود که کاراکتر i ام آن جواب درست برای i امین سوال است. $$1 \le n \le 100$$ # خروجی در خط اول ماکزیمم تعداد جواب درست را چاپ کنید . و در خطوط بعدی اسم کسانی که بیشترین جواب درست را داده اند چاپ کنید (به ترتیب حروف الفبا). ***به بزرگ و کوچک بودن حروف در خروجی دقت کنید!*** # مثال ## ورودی نمونه ۱ ``` 15 AAACBCCAAABCAAA ``` ## خروجی نمونه ۱ ``` 7 Armin Milad Parham ``` ## ورودی نمونه ۲ ``` 10 AAABCBACCB ``` ## خروجی نمونه ۲ ``` 3 Armin Parham ```

میلاد با دوستای فرز و شیطونش !

رنگ بادکنک : صورتی ^_^
محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۵۰ مگابایت

میلاد و پرهام و آرمین رو میشناسید ؟! خوب اگر نمیشناسید هم زیاد مهم نیست.

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

امتحان ۳ گزینه ای هستش و جواب هر کدوم از سوال ها A یا B یا C هستش !

میلاد و پرهام و آرمین اصلا سوال ها رو نمیخونند و هر کدوم به صورت کاملا شانسی ، با الگو های زیر تو پاسخنامه جواب میدند .

Milad : B , A , B , C , B , A , B , C , B , A , B , C , ……

Parham : C , C , A , A , B , B , C , C , A , A , B , B , ….

Armin : A , B , C , A , B , C , A , B , C , A , B , ……

حالا ما به شما تعداد سوالات و جواب درست آن ها را میدهیم شما به ما بگویید بیشترین تعداد پاسخ درستی که میلاد ، آرمین و پرهام با استفاده از الگو های خودشون میدهند چنتاست و همچنین چه کسی(یا کسانی) بیشترین پاسخ درست را میدهند!

ورودی🔗

در خط اول یک عدد n به شما داده میشود که نشان دهنده تعداد سوال هاست.

در خط بعدی یک رشته به طول n به شما داده میشود که کاراکتر i ام آن جواب درست برای i امین سوال است.

$1 \le n \le 100$

خروجی🔗

در خط اول ماکزیمم تعداد جواب درست را چاپ کنید .

و در خطوط بعدی اسم کسانی که بیشترین جواب درست را داده اند چاپ کنید (به ترتیب حروف الفبا).

به بزرگ و کوچک بودن حروف در خروجی دقت کنید!

مثال🔗

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

15
AAACBCCAAABCAAA

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

7
Armin
Milad
Parham

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

10
AAABCBACCB

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

3
Armin
Parham

گلاب،گلاب کاشوونِس! تولد میلاد جوونِس!

رنگ بادکنک : زرد
محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۵۰ مگابایت

این هفته تولد میلاد بود و آرمین به عنوان دوست صمیمی میلاد برایش یک کیک مستطیل شکل گرفته بود . آرمین عصر روز چهارشنبه به شیرینی فروشی واقع در میدان فاطمی رفت و از آنجا کیک رو تحویل گرفت و به اتاق ACM آورد.

وقتی به دانشکده رسید به میلاد زنگ زد تا بیاد به اتاق ACM دانشکده و سورپرایزش کنه. تو مدتی که منتظر میلاد بود یک مسئله جالب به ذهنش رسید . اگر بتونه حداکثر n تا برش ، که هر برش حتما در راستای طول یا در راستای عرض کیک هست ، بزنه، ماکزیمم تکه های کیک که بوجود میاد چقدره !؟

از اونجایی که این مسئله هنوز هم برای آرمین حل نشده از شما میخواهیم این مسئله رو حل کنید!

ورودی🔗

در تنها خط ورودی n که تعداد کل برش هاست به شما داده میشه. $1 \le n \le 100$

خروجی🔗

در یک خط ماکزیمم تعداد تیکه های کیک رو چاپ کنید.

مثال🔗

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

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

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

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

نون، پنیر، خیار، گوجه

رنگ بادکنک : پوست پیازی :دی
محدودیت زمان: ۲ ثانیه
محدودیت حافظه: ۵۰ مگابایت

میلاد می خواهد برای خودش لقمه ی نون ، پنیر ، خیار ، گوجه بگیرد برای این کار ابتدا نیّت میکند و بعد از آن یک نون سنگگ خاشخاشی به طول n بر میدارد و تمامی سطح آن را پنیر لیقوان میزند ، سپس به دلخواه از چپ به راستِ نون را یا گوجه میگذارد یا خیار تا تمامی طول نون دارای خیار و گوجه شود.(دقت کنید که در آخر در مجموع n خیار و گوجه روی نون گذاشته شده).

از آنجا که میلاد می خواهد لقمه اش به اندازه کافی خوشمزه شود ، هیچگاه ۳ تا گوجه و یا ۴ تا خیار را کنار هم نمیگذارد.

در همین حین که میلاد لقمه اش را درست می کند این سوال به ذهنش می رسد که به چند طریق می تواند خیار و گوجه ها را بچیند که لقمه اش به اندازه کافی خوشمزه شود.(دقت کنید که طول هر گوجه و هر خیار 1 واحد است)

ورودی🔗

در تنها خط ورودی n آمده است $1 \le n \le 18$

خروجی🔗

در تنها خط خروجی جواب خواسته شده را چاپ کنید.

مثال🔗

یک لقمه به اندازه کافی خوشمزه به طول ۶ : خیار ، خیار ، خیار ، گوجه ، گوجه ، خیار

یک لقمه بدمزه به طول ۶ : خیار ، گوجه ، خیار ، خیار ، خیار ، خیار

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

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

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

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

+ رنگ بادکنک : بنفش + محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۵۰ مگابایت ---------- یک روز گرم زمستانی!! دیگر برای پرهام آغاز شده و مثل باقی روز ها او کاری برای انجام دادن ندارد ، در نتیجه او برای سرگرم کردن خود پیش دوستانش میرود و از آنها ۲ عدد a , b می پرسد تا بازی خود را با این اعداد آغاز کند. هدف پرهام برابر کردن عدد a با عدد b با کمترین تعداد حرکت است.(پرهام فقط روی عدد a حرکت میزند !!) در هر حرکت پرهام یک عدد که مقسوم علیه مقدار فعلی a است را به آن اضافه می کند (به جز عدد ۱ و مقدار فعلی a) برای مثال کمترین تعداد حرکت برای رسیدن از ۴ به ۲۴ ، ۵ حرکت میشود . (دقت کنید که مقدار a بعد از هر حرکت عوض میشود) $$4 \rightarrow 6 \rightarrow 8 \rightarrow 12 \rightarrow 18 \rightarrow 24$$ حال پرهام از شما میخواهد که به ازای ۲ عدد a ,b کمترین تعداد حرکت برای برابر کردن عددa با عدد b را به دست آورید. # ورودی ورودی تنها شامل یک خط است که در آن دو عدد طبیعی $a$ و $b$ با فاصله از هم آمده است. $$4 \le a \le b \le 100\ 000$$ # خروجی در تنها خط خروجی در صورت وجود جواب کمترین مقدار آن را چاپ کنید و در صورتی که نمیتوان a را برابر b کرد عدد **۱-** را در خروجی چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 24 ``` ## خروجی نمونه ۱ ``` 5 ``` ## ورودی نمونه ۲ ``` 8748 83462 ``` ## خروجی نمونه ۲ ``` 10 ``` ## ورودی نمونه ۳ ``` 4 99991 ``` ## خروجی نمونه ۳ ``` -1 ```

پرهام بیکار

رنگ بادکنک : بنفش
محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۵۰ مگابایت

یک روز گرم زمستانی!! دیگر برای پرهام آغاز شده و مثل باقی روز ها او کاری برای انجام دادن ندارد ، در نتیجه او برای سرگرم کردن خود پیش دوستانش میرود و از آنها ۲ عدد a , b می پرسد تا بازی خود را با این اعداد آغاز کند.

هدف پرهام برابر کردن عدد a با عدد b با کمترین تعداد حرکت است.(پرهام فقط روی عدد a حرکت میزند !!)

در هر حرکت پرهام یک عدد که مقسوم علیه مقدار فعلی a است را به آن اضافه می کند (به جز عدد ۱ و مقدار فعلی a) برای مثال کمترین تعداد حرکت برای رسیدن از ۴ به ۲۴ ، ۵ حرکت میشود . (دقت کنید که مقدار a بعد از هر حرکت عوض میشود)

$4 \rightarrow 6 \rightarrow 8 \rightarrow 12 \rightarrow 18 \rightarrow 24$

حال پرهام از شما میخواهد که به ازای ۲ عدد a ,b کمترین تعداد حرکت برای برابر کردن عددa با عدد b را به دست آورید.

ورودی🔗

ورودی تنها شامل یک خط است که در آن دو عدد طبیعی $a$ و $b$ با فاصله از هم آمده است. $4 \le a \le b \le 100\ 000$

خروجی🔗

در تنها خط خروجی در صورت وجود جواب کمترین مقدار آن را چاپ کنید و در صورتی که نمیتوان a را برابر b کرد عدد ۱- را در خروجی چاپ کنید.

مثال🔗

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

4 24

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

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

8748 83462

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

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

4 99991

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

-1

+ رنگ بادکنک : قهوه ای + محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۵۰ مگابایت ---------- **این سوال دارای زیر مسئله است.** میلاد و پرهام یک روز تصمیم میگیرند که با هم مسابقه ی فوتبال بدهند. متاسفانه مشاور ورزشی میلاد نتوانسته گزارش کاملی از بازی آنها به دست بیاورد ولی نتیجه بازی را از اخبار سراسری دریافت کرده و متوجه شده که میلاد مسابقه را برده است. حال او میخواهد تعداد حالات ممکنی را بداند که میلاد در آنها بازی را با استرس برده و تعداد حالات ممکنی که میلاد بازی را بدون استرس برده. از آنجا که آقای مشاور اعتقاد عجیبی به این جمله دارد که "هر کسی را بهر کاری ساخته اند" این سوال را برای ما فرستاده تا بلکه به دست توانمند شما حل شود. **تعریف برد بدون استرس** : در این برد میلاد گل اول را می زند و تا آخر بازی میلاد حداقل یک گل از پرهام جلوتر است. **تعریف برد همراه با استرس** : در این نوع برد میلاد هیچگاه در جریان بازی از پرهام بیشتر گل نمی زند تا هنگامی که تعداد گل های پرهام برابر تعداد گل های نهایی اش شود. # ورودی در تنها خط ورودی به شما نتیجه ی نهایی بازی داده میشود(ابتدا تعداد گل های میلاد و سپس با یک خط تیره تعداد گل های پرهام) تعداد گل های هر فرد از 2000 بیشتر نیست. **زیر مسئله کوچک** : در این زیر مسئله تعداد کل گل های زده شده در بازی از 20 بیشتر نیست، این زیرمسئله دارای 40 نمره از کل امتیاز مسئله میباشد. # خروجی در تنها خط خروجی ابتدا تعداد حالات ممکن برد بدون استرس و سپس تعداد حالات ممکن برد با استرس را چاپ کنید .(از آنجا که ممکن است خروجی ها بزرگ باشند باقی مانده آنها را به $10^9 + 7$ چاپ کنید) # مثال ## ورودی نمونه ۱ ``` 3-2 ``` ## خروجی نمونه ۱ ``` 2 2 ``` **یک بازی بدون استرس برای نمونه ی ۱ ** : ابتدا میلاد ۲ گل بزند سپس پرهام یک گل بزند و بعد از آن به ترتیب میلاد و پرهام یک گل به ثمر برسانند. **یک بازی همراه با استرس برای نمونه ی ۱ ** : ابتدا پرهام ۲ گل به ثمر برساند و بعد از آن میلاد ۳ گل به پرهام بزند. ## ورودی نمونه ۲ ``` 10-5 ``` ## خروجی نمونه ۲ ``` 1001 42 ``` ## ورودی نمونه ۳ ``` 1000-500 ``` ## خروجی نمونه ۳ ``` 70047606 591137401 ```

مشاور علاف

رنگ بادکنک : قهوه ای
محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۵۰ مگابایت

این سوال دارای زیر مسئله است.

میلاد و پرهام یک روز تصمیم میگیرند که با هم مسابقه ی فوتبال بدهند.

متاسفانه مشاور ورزشی میلاد نتوانسته گزارش کاملی از بازی آنها به دست بیاورد ولی نتیجه بازی را از اخبار سراسری دریافت کرده و متوجه شده که میلاد مسابقه را برده است.

حال او میخواهد تعداد حالات ممکنی را بداند که میلاد در آنها بازی را با استرس برده و تعداد حالات ممکنی که میلاد بازی را بدون استرس برده.

از آنجا که آقای مشاور اعتقاد عجیبی به این جمله دارد که "هر کسی را بهر کاری ساخته اند" این سوال را برای ما فرستاده تا بلکه به دست توانمند شما حل شود.

تعریف برد بدون استرس :

در این برد میلاد گل اول را می زند و تا آخر بازی میلاد حداقل یک گل از پرهام جلوتر است.

تعریف برد همراه با استرس :

در این نوع برد میلاد هیچگاه در جریان بازی از پرهام بیشتر گل نمی زند تا هنگامی که تعداد گل های پرهام برابر تعداد گل های نهایی اش شود.

ورودی🔗

در تنها خط ورودی به شما نتیجه ی نهایی بازی داده میشود(ابتدا تعداد گل های میلاد و سپس با یک خط تیره تعداد گل های پرهام) تعداد گل های هر فرد از 2000 بیشتر نیست.

زیر مسئله کوچک : در این زیر مسئله تعداد کل گل های زده شده در بازی از 20 بیشتر نیست، این زیرمسئله دارای 40 نمره از کل امتیاز مسئله میباشد.

خروجی🔗

در تنها خط خروجی ابتدا تعداد حالات ممکن برد بدون استرس و سپس تعداد حالات ممکن برد با استرس را چاپ کنید .(از آنجا که ممکن است خروجی ها بزرگ باشند باقی مانده آنها را به $10^9 + 7$ چاپ کنید)

مثال🔗

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

3-2

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

2 2

*یک بازی بدون استرس برای نمونه ی ۱ * : ابتدا میلاد ۲ گل بزند سپس پرهام یک گل بزند و بعد از آن به ترتیب میلاد و پرهام یک گل به ثمر برسانند.

*یک بازی همراه با استرس برای نمونه ی ۱ * : ابتدا پرهام ۲ گل به ثمر برساند و بعد از آن میلاد ۳ گل به پرهام بزند.

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

10-5

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

1001 42

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

1000-500

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

70047606 591137401

+ رنگ بادکنک : آبی کمرنگ + محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- **این سوال دارای زیر مسئله است** بعد از مدت‌ها فشار دوستان، پرهام تصمیم می‌گیرد که لباس‌هایش را بشوید! برای همین با L لباس وارد خشکشویی می‌شود. در آنجا N ماشین لباس‌شویی و M ماشین خشک‌کن وجود دارد. هر ماشین لباس‌شویی سرعت متفاوتی دارد و i امین ماشین لباس‌شویی در (W(i دقیقه کار شستن را انجام می‌دهد. اما تمام ماشین‌های خشک‌کن کار خود را در D دقیقه انجام می‌دهند. پرهام می‌خواهد در کمترین زمان ممکن کار شستن و خشک‌کردن لباس‌هایش تمام شود. اما یک مشکل وجود دارد. هیچ دو لباسی هم‌رنگ نیستند و اگر با هم درون یک ماشین لباس‌شویی یا ماشین خشک‌کن قرار داده شوند، رنگ آن‌ها خراب می‌شود! پس هر لباس باید به تنهایی درون ماشین لباس‌شویی و یا خشک‌کن گذاشته شود. به پرهام بگویید کمترین زمان ممکن برای شسته شدن و خشک شدن لباس‌هایش چند دقیقه است؟ # ورودی ورودی با یک خط شامل چهار عدد L و N و M و D آغاز می‌شود. در خط بعدی N عدد داده می‌شود که عدد iام، (W(i است. $$1 \le L \le 1\ 000\ 000$$ $$1 \le N \le 100\ 000$$ $$1 \le M , D , W(i) \le 1\ 000\ 000\ 000$$ **زیر مسئله کوچک** : این زیر مسئله دارای ۲۰ نمره از ۱۰۰ نمره میباشد با فرضیات زیر $$ N \le 50 $$$$ L \le 100\ 000 $$ # خروجی در تنها خط خروجی یک عدد چاپ کنید که بیانگر کمترین زمان لازم برای شسته شدن و خشک شدن تمام لباس‌هاست. # مثال ## ورودی نمونه ۱ ``` 1 1 1 34 1200 ``` ## خروجی نمونه ۱ ``` 1234 ``` ## ورودی نمونه ۲ ``` 2 3 2 10 100 10 1 ``` ## خروجی نمونه ۲ ``` 12 ``` ## ورودی نمونه ۳ ``` 999 1 999 6 3 ``` ## خروجی نمونه ۳ ``` 3003 ```

سرانجام پرهام لباس‌هایش را می‌شوید!

رنگ بادکنک : آبی کمرنگ
محدودیت زمان: ۲ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

این سوال دارای زیر مسئله است

بعد از مدت‌ها فشار دوستان، پرهام تصمیم می‌گیرد که لباس‌هایش را بشوید! برای همین با L لباس وارد خشکشویی می‌شود. در آنجا N ماشین لباس‌شویی و M ماشین خشک‌کن وجود دارد. هر ماشین لباس‌شویی سرعت متفاوتی دارد و i امین ماشین لباس‌شویی در (W(i دقیقه کار شستن را انجام می‌دهد. اما تمام ماشین‌های خشک‌کن کار خود را در D دقیقه انجام می‌دهند.

پرهام می‌خواهد در کمترین زمان ممکن کار شستن و خشک‌کردن لباس‌هایش تمام شود. اما یک مشکل وجود دارد. هیچ دو لباسی هم‌رنگ نیستند و اگر با هم درون یک ماشین لباس‌شویی یا ماشین خشک‌کن قرار داده شوند، رنگ آن‌ها خراب می‌شود! پس هر لباس باید به تنهایی درون ماشین لباس‌شویی و یا خشک‌کن گذاشته شود.

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

ورودی🔗

ورودی با یک خط شامل چهار عدد L و N و M و D آغاز می‌شود. در خط بعدی N عدد داده می‌شود که عدد iام، (W(i است.

$1 \le L \le 1\ 000\ 000$

$1 \le N \le 100\ 000$

$1 \le M , D , W(i) \le 1\ 000\ 000\ 000$

زیر مسئله کوچک : این زیر مسئله دارای ۲۰ نمره از ۱۰۰ نمره میباشد با فرضیات زیر $N \le 50$ $L \le 100\ 000$

خروجی🔗

در تنها خط خروجی یک عدد چاپ کنید که بیانگر کمترین زمان لازم برای شسته شدن و خشک شدن تمام لباس‌هاست.

مثال🔗

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

1 1 1 34
1200

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

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

2 3 2 10
100 10 1

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

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

999 1 999 6
3

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

+ رنگ بادکنک : زرشکی + محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- **این سوال دارای زیر مسئله است** میلاد به تازگی موبایل Galaxy Note 4 را فروخته و با عیدی هایش یک گوشی خفن خریده است. این گوشی خفن یک ویژگی خفن دارد که AutoCompelete موقع تایپ است. اما گوشی آقا میلاد فقط موقعی AutoComplete میکند که مطمئن باشد حروفی که تا الان تایپ شده قرار است تبدیل به چه کلمه ای شود.(یعنی تنها یک گزینه برای AutoComplete موجود باشد) همچنین این گوشی فقط میتواند کلمه هایی را حدس بزند که قبلا به دیکشنری آن اضافه شده است. میلاد میخواهد n کلمه را به ترتیب در یک پیامک برای آرمین بفرستد . قبل از تایپ یک کلمه میلاد باید آن کلمه را به دیکشنری اضافه کند. سپس به ازای آن کلمه تا جایی تایپ میکند که یا AutoComplete انجام شود یا کلمه کامل تایپ شود. از آنجایی که میلاد خیلی خسته است از شما میخواهد کمترین تعداد حروف لازم برای نوشتن n کلمه (به ترتیب ورودی) را به او بگووید تا اگر این حروف زیاد تر از انتظار او شد بیخیال تایپ کردن شود و از قابلیت وویس فرستادن استفاده کند :| . توجه کنید کنید که شما نباید اضافه کردن به دیکشنری را جزو کاراکتر های تایپی حساب کنید . برای فهمیدن بیشتر به ورودی و خروجی نمونه و توضیح آن ها دقت کنید. # ورودی در خط اول n که تعداد کلمات است به شما داده می شود. $$0 \le n \le 100\ 000$$ در n خط بعدی در هر خط یک رشته که شامل حروف انگلیسی است به شما داده میشود که مجموع طول رشته ها از 1000000 بیشتر نیست. **زیرمسیله کوچک** : با فرض اینکه n و بیشینه طول یه کلمه بیشتر از 10 نباشد میتوانید ۲۰ نمره از کل امتیاز این سوال را بگیرید. # خروجی در یک خط حداقل تعداد کاراکتر های تایپی توسط میلاد راچاپ کنید. ## ورودی نمونه ۱ ``` 5 hi hello lol hills hill ``` ## خروجی نمونه ۱ ``` 11 ``` # توضیح نمونه ۱ اضافه شدن کلمه ی hi به دیکشنری --> تایپ کردن h --> اautocomplete اضافه شدن کلمه ی hello به دیکشنری --> تایپ کردن he --> اautocomplete اضافه شدن کلمه ی lol به دیکشنری --> تایپ کردن l --> اautocomplete اضافه شدن کلمه ی hills به دیکشنری --> تایپ کردن hil --> اautocomplete اضافه شدن کلمه ی hill به دیکشنری --> تایپ کردن hill ## ورودی نمونه ۲ ``` 5 a aa aaa aaaa aaaaa ``` ## خروجی نمونه ۲ ``` 15 ``` ## ورودی نمونه ۳ ``` 5 aaaaa aaaa aaa aa a ``` ## خروجی نمونه ۳ ``` 11 ```

تایپ کردن با اعمال شاقه !!

رنگ بادکنک : زرشکی
محدودیت زمان: ۲ ثانیه
محدودیت حافظه: ۵۱۲ مگابایت

این سوال دارای زیر مسئله است

میلاد به تازگی موبایل Galaxy Note 4 را فروخته و با عیدی هایش یک گوشی خفن خریده است.

این گوشی خفن یک ویژگی خفن دارد که AutoCompelete موقع تایپ است.

اما گوشی آقا میلاد فقط موقعی AutoComplete میکند که مطمئن باشد حروفی که تا الان تایپ شده قرار است تبدیل به چه کلمه ای شود.(یعنی تنها یک گزینه برای AutoComplete موجود باشد)

همچنین این گوشی فقط میتواند کلمه هایی را حدس بزند که قبلا به دیکشنری آن اضافه شده است.

میلاد میخواهد n کلمه را به ترتیب در یک پیامک برای آرمین بفرستد . قبل از تایپ یک کلمه میلاد باید آن کلمه را به دیکشنری اضافه کند. سپس به ازای آن کلمه تا جایی تایپ میکند که یا AutoComplete انجام شود یا کلمه کامل تایپ شود.

از آنجایی که میلاد خیلی خسته است از شما میخواهد کمترین تعداد حروف لازم برای نوشتن n کلمه (به ترتیب ورودی) را به او بگووید تا اگر این حروف زیاد تر از انتظار او شد بیخیال تایپ کردن شود و از قابلیت وویس فرستادن استفاده کند :| .

توجه کنید کنید که شما نباید اضافه کردن به دیکشنری را جزو کاراکتر های تایپی حساب کنید .

برای فهمیدن بیشتر به ورودی و خروجی نمونه و توضیح آن ها دقت کنید.

ورودی🔗

در خط اول n که تعداد کلمات است به شما داده می شود. $0 \le n \le 100\ 000$ در n خط بعدی در هر خط یک رشته که شامل حروف انگلیسی است به شما داده میشود که مجموع طول رشته ها از 1000000 بیشتر نیست.

زیرمسیله کوچک : با فرض اینکه n و بیشینه طول یه کلمه بیشتر از 10 نباشد میتوانید ۲۰ نمره از کل امتیاز این سوال را بگیرید.

خروجی🔗

در یک خط حداقل تعداد کاراکتر های تایپی توسط میلاد راچاپ کنید.

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

5
hi
hello
lol
hills
hill

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

توضیح نمونه ۱🔗

اضافه شدن کلمه ی hi به دیکشنری --> تایپ کردن h --> اautocomplete

اضافه شدن کلمه ی hello به دیکشنری --> تایپ کردن he --> اautocomplete

اضافه شدن کلمه ی lol به دیکشنری --> تایپ کردن l --> اautocomplete

اضافه شدن کلمه ی hills به دیکشنری --> تایپ کردن hil --> اautocomplete

اضافه شدن کلمه ی hill به دیکشنری --> تایپ کردن hill

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

5
a
aa
aaa
aaaa
aaaaa

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

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

5
aaaaa
aaaa
aaa
aa
a