+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۰۲۴ مگابایت ---------- دانشگاه تهران یکی از بزرگترین دانشگاه‌های دنیاست و دارای $m$ درب می‌باشد‌‌! در یک روز سرد بهاری $n$ نفر از دانشجویان دانشگاه تهران می‌خواهند وارد دانشگاه شوند و چون خیلی به بزرگتر‌هایشان احترام می‌گذارند،‌ به ترتیب سن از بزرگ به کوچک وارد دانشگاه می‌شوند. از آن جایی که آن‌ها خیلی انسان‌های عدالت‌طلبی هستند، وقتی نوبتشان می‌شود، از دربی وارد می‌شوند که تاکنون کمترین تعداد دانشجو از آن درب وارد شده است‌ (برای اینکه عدالت بین نگهبان‌ها رعایت شود). اگر چند درب با ویژگی گفته شده وجود داشت، یکی از درب‌ها را به صورت تصادفی انتخاب می کنند و از آن وارد می‌شوند. سپیده یکی از نگهبان‌های تنبل دانشگاه است که مسئول درب شماره یک می باشد. وی به خاطر این حجم بی‌سابقه از ورود کلافه شده است و می‌خواهد بداند که حداکثر چند دانشجو ممکن است از درب شماره‌ی یک وارد شوند. از آن‌جایی که شما بسیار مهربان و دلسوز هستید، به سپیده کمک کنید تا جواب مورد نظرش را به دست بیاورد. (برای اینکه سپیده خیلی خوش‌حال شود، کوچکترین عدد ممکن را خروجی دهید) # ورودی ورودی تنها شامل یک خط است که در آن دو عدد طبیعی $n$ و $m$ با فاصله از هم آمده است. $$1 \le n, m \le 1\ 000$$ # خروجی در تنها سطر خروجی پاسخ مسئله را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 9 3 ``` ## خروجی نمونه ۱ ``` 3 ``` ## ورودی نمونه ۲ ``` 7 4 ``` ## خروجی نمونه ۲ ``` 2 ``` ابتدا نفر اول یکی از درب‌ها را به صورت تصادفی انتخاب می‌کند. سپس نفر دوم یکی از سه درب باقی‌مانده را به صورت تصادفی انتخاب می‌کند. سپس نفر سوم یکی از درب‌های انتخاب نشده را به صورت تصادفی انتخاب می‌کند و نفر چهارم نیز از دربی داخل می‌شود که تاکنون هیچ کس از آن داخل نشده است. حال از همه‌ی درب‌ها دقیقا یک نفر وارد شده است. اکنون نفر پنجم یکی از درب‌ها را به صورت تصادفی انتخاب می‌کند و پس از آن، نفر ششم یکی از سه درب باقی‌مانده را تصادفا انتخاب می‌کند. حال نفر هفتم نیز یکی از دو دربی را که تاکنون دقیقا یک بار ورود از آن‌ها صورت گرفته است را انتخاب می‌کند. در نهایت از سه درب دو بار ورود و از درب چهارم یک بار ورود انجام شده است. از آن‌جایی که انتخاب افراد تصادفی بوده است ممکن است درب شماره‌ی یک نیز جزو آن سه درب باشد و در نتیجه پاسخ برابر دو می باشد.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۰۲۴ مگابایت ---------- از آن‌جایی که دانشجویان دانشگاه تهران خیلی با هم دوست هستند و برای دوستانشان هم ارزش زیادی قائلند، پس از ورود منتظر می‌شوند تا بقیه‌ی دوستانشان هم از درب وارد شوند**!** دانشجو‌‌ها به ترتیب از درب وارد می‌شوند و هر کسی پس از ورود، با ترتیب بر‌عکس ورودی به افراد حاضر در جمع سلام می‌کند (ابتدا نفر آخری که وارد شده، سپس نفر یکی مانده به آخری که وارد شده، ... و در نهایت نفر اولی که وارد دانشگاه شده است). جالب است بدانید که بچه‌های دانشگاه تهران اعتقادی به جواب سلام ندارند. چون افراد دانشگاه تهران زیاد درس می‌خوانند، روابط اجتماعی ضعیفی دارند و فقط سلام و خداحافظی بلدند. به همین دلیل، پس از اینکه همه‌ی افراد وارد شدند، دانشجوها با همان ترتیبی که آمده بودند، شروع به رفتن می‌کنند. ولی فراموش نکنیم که دانشجوهای دانشگاه تهران خیلی با‌ادب هستند و هیچ‌گاه بدون خداحافظی از بقیه، جمع را ترک نمی‌کنند. هر کسی که می‌خواهد برود، ابتدا از تمام بچه‌ها خداحافظی می‌کند و سپس می‌رود. منتها چون سرش از حجم بالای سلام‌ها درد گرفته است، فقط می‌گوید خداحافظ بچه‌ها. پس از آن، بقیه‌ی بچه ها به ترتیب ورودشان از او خداحافظی می‌کنند و سپس نفر مورد نظر خواهد رفت. مسئولین دانشگاه تهران خیلی به فکر دانشجوهایشان هستند و به همین خاطر می‌خواهند تمام گفت‌و‌گو‌های بین دانشجویان را دقیق مورد بررسی قرار دهند. از آن‌جایی که مسئولین سرشان خیلیییییییی شلوغ است، به آن‌ها کمک کنید و این گفت‌و‌گو‌ها را برایشان چاپ کنید. # ورودی در سطر اول ورودی عدد $n$ آمده است. در سطر دوم $n$ رشته آمده است که رشته‌ی $i$ ام، نام نفر $i$ ام می‌باشد. $$1 \le n \le 50$$ طول اسم هر نفر کمتر مساوی ده می‌باشد. # خروجی در خروجی، همه‌ی جملاتی که در گفت‌و‌گوی دانشجوها به کار برده شده است را به ترتیب چاپ کنید. هر جمله را به این صورت چاپ کنید که ابتدا اسم دانشجو و سپس جمله‌ای که گفته است چاپ شده باشد. # مثال ## ورودی نمونه ۱ ``` 4 ali hana jafar tizi ``` ## خروجی نمونه ۱ ``` hana: salam ali! jafar: salam hana! jafar: salam ali! tizi: salam jafar! tizi: salam hana! tizi: salam ali! ali: khodafez bacheha! hana: khodafez ali! jafar: khodafez ali! tizi: khodafez ali! hana: khodafez bacheha! jafar: khodafez hana! tizi: khodafez hana! jafar: khodafez bacheha! tizi: khodafez jafar! tizi: khodafez bacheha! ``` ## ورودی نمونه ۲ ``` 1 mikaeel ``` ## خروجی نمونه ۲ ``` mikaeel: khodafez bacheha! ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۰۲۴ مگابایت ---------- دانشگاه تهران یکی از بهترین سلف‌های دنیا را دارد و کیفیت غذای آن فوق‌العاده است**!** میکائیل مسئول سلف دانشگاه تهران است و بسیار انسان منظمی است. همچنین او به عدد چهار علاقه‌ی زیادی دارد (این علاقه ریشه در اعتقاد شدید او به علم ژنتیک دارد). به همین جهت، سیستم پخش غذا در دانشگاه تهران به این صورت است که غذاها به صورت چهار تا چهار تا بسته‌بندی می‌شوند. سپس در هر نوبت، یک گروه حداکثر چهار نفره داخل صف می‌شوند و میکائیل یکی از بسته‌ها را باز می‌کند. سپس به هر کدام از افراد داخل صف دقیقا یک غذا می‌دهد و برای حفظ عدالت بقیه‌ی غذاهای آن بسته را خودش می‌خورد. از آن‌جایی که در دانشگاه تهران میزان فشار بر روی دانشجوهای مختلف خیلی متفاوت است، بعضی از افراد یک غذا، بعضی دیگر دو غذا،‌ و حتی بعضی‌ها به علت فشار بسیار زیاد سه غذا می‌خواهند. تعداد غذاهایی که نفر $i$ ام می‌خواهد را $a_i$ می‌نامیم. دانشگاه تهران مسئولین بسیار مهربانی دارد و به هر کس هر تعداد غذا که بخواهد، داده می‌شود ولی خب بودجه‌ی آن‌ها محدود است و می‌خواهند تا جایی که می‌توانند در تهیه‌ی غذاها صرفه‌جویی بکنند. حال آن‌ها از شما کمک خواسته‌اند و می خواهند بدانند که میکائیل حداقل چند بسته غذا باید تهیه کند. به آن ها کمک کنید تا ورشکست نشوند!!! # ورودی در سطر اول ورودی عدد $n$ آمده است. در سطر دوم $n$ عدد آمده است که عدد $i$ ام $a_i$ می باشد. $$1 \le n \le 5\ 000$$ $$1 \le a_i \le 3$$ # خروجی در تنها سطر خروجی کمترین تعداد بسته‌ی غذا که میکائیل باید تهیه کند را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 1 1 1 1 ``` ## خروجی نمونه ۱ ``` 1 ``` در یک مرحله، همه‌ی چهار نفر داخل صف قرار می گیرند و به هر کدام از آن ها دقیقا یک غذا داده می‌شود و همه به خواسته‌ی خود می‌رسند. ## ورودی نمونه ۲ ``` 3 1 1 2 ``` ## خروجی نمونه ۲ ``` 2 ``` در مرحله‌ی اول هر سه نفر داخل صف قرار می‌گیرند و به هر کدام از آن‌ها یک غذا داده می‌شود و یک غذا را نیز خود میکائیل می‌خورد. ولی چون نفر سوم دو غذا می‌خواهد، یک بار دیگر هم در صف قرار می‌گیرد و برای بار دوم غذا دریافت می‌کند و سه غذای باقی‌مانده از بسته‌ی دوم را نیز خود میکائیل نوش‌جان می‌کند!

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۰۲۴ مگابایت ---------- امید یکی از دانشجویان جدید دانشگاه تهران است که به مقدار نامتناهی خسته است**!** یک بار که امید سر کلاس ریاضی ۲ نشسته بود، استاد متوجه خستگی بیش از حد او شد و برای اینکه امید را از این حال در بیاورد (غافل از اینکه توان انجامش را ندارد)، تصمیم گرفت یک بازی برای او اختراع کند. استاد در حیاط دانشگاه یک رشته به نام $s$ به طول $n$ متشکل از ارقام ۰ تا ۹ نوشت و امید را روی $s_1$ قرار داد(منظور از $s_i$ رقم $i$ ام رشته می باشد). سپس به او گفت که باید تعدادی حرکت انجام دهد تا روی $s_n$ قرار گیرد. وقتی امید فهمید که در هر حرکت حداکثر می‌تواند یک واحد جا‌به‌جا شود‌ (از رقم $i$ ام می‌تواند به رقم $i + 1$ ام یا رقم $i - 1$ ام در صورت وجود برود) اشک در چشمانش حلقه زد و نزدیک بود گریه‌اش بگیرد که استاد مهربان، دلش به حال او سوخت و گفت باشه باشه! اگر $s_i$ = $s_j$ باشد هم می‌توانی با یک حرکت از $i$ به $j$ بروی. امید که از این قابلیت جدید خیلی خوشش آمده بود، خودش را جمع‌و‌جور کرد و گفت من می‌تونم! ولی بنده‌خدا هنوز هم خیلی خسته است و از شما کمک خواسته تا با چاپ کردن کمترین تعداد حرکت لازم بهش دلگرمی بدید. # ورودی در سطر اول ورودی عدد $n$ آمده است. در سطر دوم نیز یک رشته به طول $n$ متشکل از ارقام ۰ تا ۹ آمده است. $$1 \le n \le 100\ 000$$ # خروجی در تنها سطر خروجی کمترین تعداد حرکات لازم برای رسیدن امید از $s_1$ به $s_n$ را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 5 01234 ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 5 92391 ``` ## خروجی نمونه ۲ ``` 2 ```

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۱۰۲۴ مگابایت ---------- تیزی یکی از بزرگترین قاچاقچی های پفک در خاور میانه است که فارغ التحصیل دانشگاه تهران است و به همین دلیل ارق زیادی به این دانشگاه و دانشجوهایش دارد**!!!** به تازگی $n$ محموله پفک به دست تیزی رسیده است. محموله $i$ ام $a_i$ تن جرم دارد. می دانیم جرم محموله ها کمتر مساوی ده تن می باشد وگرنه هنگام عبور از مرز لو می روند! بچه های دانشگاه تهران چند وقتی است که عصرانه درست و حسابی نمی خورند و به همین جهت تیزی می خواهد کل محموله هایی که اکنون دارد را برای آن ها بفرستد. تیزی تعداد خیلی زیادی دوست راننده کامیون دارد (این قدر زیاد که قابل شمردن نیستند). هر کدام از راننده ها برای حمل پفک به دانشگاه تهران یک میلیارد و دویست پول می گیرند ولی چون تیزی با آن ها رفیق است، روی حساب دوستی یه میلیارد از تیزی می گیرند (مقدار پولی که راننده ها می گیرند،‌ ربطی به جرم بارشان ندارد). هر کدام از کامیون ها حداکثر می توانند ۲۰ تن پفک را جا به جا کنند. تیزی برای جابه جایی پفک ها، به هر راننده تعدادی از محموله‌هایش را به طور کامل می دهد (هیچ محموله ای را تکه تکه نمی کند). ولی به دلیل افزایش امنیت مرزها، وضع اقتصادی تیزی خیلی خوب نیست. به همین جهت او از شما کمک خواسته و می خواهد تا جای ممکن هزینه‌ی کمتری پرداخت کند. هر چه قدر بیشتر تیزی را خوش‌حال کنید، نمره بیشتری دریافت می کنید! **توجه کنید که نیازی نیست شما بهترین جواب را به دست آورید؛ با خروجی دادن جواب‌های نسبتا خوب هم می‌توانید بخش زیادی از نمره‌ی سوال را دریافت کنید.** # ورودی در سطر اول ورودی عدد $n$ آمده است. در سطر دوم $n$ عدد آمده است که عدد $i$ ام $a_i$ می باشد. $$1 \le n \le 100\ 000$$ $$1 \le a_i \le 10$$ # خروجی در سطر اول خروجی عدد $k$ آمده است که نشان دهنده تعداد راننده ها برای انتقال محموله ها می باشد. در سطر دوم، $n$ عدد آمده است که عدد $i$ ام نشان دهنده ی این است که محموله $i$ ام توسط راننده ی چندم حمل می شود. دقت کنید که هر کدام از راننده ها توانایی حمل حداکثر ۲۰ تن پفک را دارند. توجه داشته باشید که هر چه $k$ کمتر باشد، نمره‌ی بهتری دریافت می کنید. # مثال ## ورودی نمونه ۱ ``` 5 6 7 10 7 10 ``` ## خروجی نمونه ۱ ``` 2 1 1 2 1 2 ``` ## ورودی نمونه ۲ ``` 5 8 8 8 8 8 ``` ## خروجی نمونه ۲ ``` 3 1 1 2 2 3 ```