سعید و علی هر روز در مدرسه خوراکی­‌هایشان را با هم قسمت می­‌کنند. یک روز سعید ظرفی پر از بادام از کیفش در می‌­آورد تا آنها را با علی قسمت کند. او قبلاً از روی بیکاری (!) تعداد همه‌ی بادام‌­ها را شمرده است. سعید ظرف بادام‌ها را باز می‌کند و اول خودش تعدادی بادام بر می‌دارد و بعد علی هم تعدادی بادام را در مشتش می‌گیرد که بخورد. سعید می‌داند که کلاً چه تعدادی بادام تلخ در میان همه‌ی بادام‌ها وجود دارد. او تا رسیدن به خانه همه‌ی بادام‌هایش را می‌خورد و تعداد بادام‌های تلخ خودش را هم می‌شمرد. حال او می‌خواهد بداند که حداقل و حداکثر چه تعدادی از بادام‌های علی تلخ است. شما باید با گرفتن تعداد کل بادام‌ها، سهم سعید و سهم علی، تعداد کل بادام‌های تلخ، و نیز تعداد بادام‌های تلخ سعید، حداقل و حداکثر تعداد بادام‌های تلخ علی را حدس بزنید. ## **ورودی** در خط اول عدد $N$ می‌آید که تعداد کل بادام‌ها است. سپس در خط بعدی تعداد بادام‌های سعید ($m1$) و در خط بعد تعداد بادام‌های علی ($m2$) می‌آید (بدیهی است که $m1+m2<=N$). در خط چهارم هم تعداد کل بادام‌های تلخ ($t$) آمده و در خط آخر تعداد بادام‌های تلخ سعید ($t1$) آمده است. همه‌ی اعداد ورودی، اعداد صحیح بین 1 تا 1000 هستند. ## **خروجی** دو عددِ زیرِ هم (در دو خط) که **به ترتیب** بیانگر حداقل و حداکثر تعداد بادام‌های تلخ سهم علی هستند. ### **ورودی نمونه** ``` 170 70 80 60 20 ``` ### **خروجی نمونه** ``` 20 40 ```

یک رودخانه در هر ثانیه n متر مکعب آب وارد مخزن یک سد می‌کند. با ورود هر 1000 متر مکعب آب به مخزن سد، ارتفاع مخزن یک متر بالا می‌رود. درون سد، دریچه‌هایی در ارتفاع‌های مختلف وجود دارند که هر کدام از آنها، در صورتی که ارتفاع آب مخزن سد، بیش‌تر از ارتفاع دریچه باشد، در هر ثانیه یک لیتر آب را از خود عبور داده و از مخزن سد خارج می‌کنند. شما باید با ورودی گرفتن میزان آب ورودی به مخزن سد و ارتفاع دریچه‌های موجود در سد، مشخص کنید چند ثانیه طول می‌کشد تا ارتفاع آب مخزن سد (که در ابتدا خالی است) به 100 متر برسد. ## **ورودی** در خط اول عدد صحیح $n$ آمده‌است که میزان آب ورودی سد در هر ثانیه است. در خط بعدی عدد صحیح ($0<m<100001$) که تعداد دریچه‌های سد را مشخص می‌کند. در $m$ خط بعدی در هر خط یک عدد صحیح مثبت کوچکتر از 101 آمده که ارتفاع یک دریچه را مشخص می‌کند. این اعداد به‌گونه‌ای هستند که ارتفاع آب مخزن سد حتماً بالاخره از 100 متر عبور خواهد کرد. ## **خروجی** یک عدد صحیح که حداقل تعداد ثانیه‌هایی است که باید صبر کنیم تا ارتفاع آب مخزن سد حداقل به 100 متر برسد. ### **ورودی نمونه** ``` 2 1 50 ``` ### **خروجی نمونه** ``` 75000 ```

قطاری به عرض $w$ و تعدادی قطعه‌ی چوبی مستطیلی‌شکل داریم. می‌خواهیم با قطعات چوبی پلی درست کنیم که قطار بتواند از آن عبور کند، با این شرط که اگر در امتداد پل در هر نقطه‌ای، یک برش عرضی بزنیم، عرض آن کمتر از $w$ نباشد و در ضمن آن برش، تنها از یک قطعه چوب ساخته شده باشد. دو قطعه‌ی چوبی را می‌توان از طرف یکی از اضلاع هر یک از آنها در کنار یک‌دیگر قرار داده و به هم چسباند. طول بلندترین پلی را که می‌توان با این قطعات ساخت پیدا کنید (هر یک از قطعات چوبی را می‌توان در ساخت پل استفاده نکرد). ## **ورودی** در خط اول عدد صحیح مثبت $n$ آمده‌ است ($n<1001$) که تعداد قطعات چوبی مستطیلی را مشخص می‌کند. در خط بعد عدد صحیح مثبت $w$ می‌آید که معرف عرض قطار است. در $2n$ خط بعدی، ابعاد قطعه‌ها (هر کدام در دو خط) به صورت اعداد صحیح خواهد آمد. ## **خروجی** یک عدد صحیح که طول بزرگ‌ترین پلی است که با این قطعات می‌توان ساخت. ### **ورودی نمونه‌ی 1** ``` 3 10 5 21 17 12 10 10 ``` ### **خروجی نمونه‌ی 1** ``` 32 ``` ### **ورودی نمونه‌ی 2** ``` 5 4 3 3 2 3 5 6 4 4 4 1 ``` ### **خروجی نمونه‌ی 2** ``` 11 ```

ماشین تحریرهای قدیمی را شما یادتان نیست. کسی که می‌خواست با آنها تایپ کند بیچاره بود، چون ماشین تحریر تقریباً هیچ‌کدام از امکاناتی را که امروز نرم‌افزارهای حروف‌چینی دارند نداشت و فقط وقتی دکمه‌اش را می‌زدید شکل ثابتی از یک حرف را روی صفحه‌ی کاغذ حک می‌کرد! از جمله امکاناتی که نداشت، تراز کردن متن بود، جوری که اول و آخر سطرها در یک راستا قرار بگیرند. این کار را باید خود ماشین‌نویس انجام می‌داد و حساب می‌کرد که چقدر فاصله باید بین کلمات قرار بدهد (یا چقدر کلمات را بکشد) تا متن تراز شود. فرض کنید برای کمک به یک ماشین‌نویس خسته، قرار است برنامه‌ای بنویسید که تعدادی کلمه از او بپرسد و با فرض این که هر یک از کلمات قرار است در یک سطر روی کاغذ ماشین تحریر نوشته شود، چاپ کند (نه روی کاغذ!) که در آن سطر بین هر دو حرف، **چند** فاصله باید قرار بگیرد. می‌خواهیم فاصله‌های بین حروف هر سطر یکنواخت و مساوی باشند، یعنی بین دو حرف فاصله‌ی بیش‌تر و بین دو تای دیگر در همان سطر فاصله‌ی کم‌تری نباشد. فرض کنید کلمات فقط و فقط از حروف انگلیسی کوچک تشکیل شده باشند. ## **ورودی** در خط اول $n$ تعداد کلمات آمده و در $n$ خط بعدی، در هر خط یک کلمه می‌آید. ## **خروجی** در $n$ خط تعداد فاصله‌های بین هر دو حرف کلمه‌ی مندرج در آن سطر می‌آید. ### **ورودی نمونه** ``` ketab gol toop boz ``` ### **خروجی نمونه** ``` 2 5 3 5 ```

در مدرسه‌ی حلی صفر، $n$ دانش‌آموز با شماره‌های 1 تا $n$ به صورت ساعت‌گرد دور یک میزِ گرد نشسته‌اند و می‌خواهند بازی «اتل متل توتوله» را بازی کنند. بازی به این شکل است که در هر مرحله، اگر شمارش از نفر شماره a شروع شد، ساعت‌گرد می‌شماریم و a-اُمین نفر را حذف می‌کنیم و در مرحله‌ی بعد از نفر بعدیِ فرد حذف شده شمارش را آغاز می‌کنیم. بازی به همین شکل ادامه پیدا می‌کند تا تنها یک نفر باقی بماند که آن فرد برنده‌ی بازی است. برنامه‌ای بنویسید که $n$ (تعداد افراد شرکت‌کننده در بازی) و $m$ (شماره‌ی شخصی که بازی از او شروع می‌شود) را بگیرد و شماره‌ی برنده‌ی بازی را چاپ کند. ## **ورودی** در خط اول تعداد افراد شرکت‌کننده در بازی و در خط دوم شماره‌ی شخصی که بازی از او شروع می‌شود ## **خروجی** شماره‌ی برنده‌ی بازی ### **ورودی نمونه** ``` 5 3 ``` ### **خروجی نمونه** ``` 4 ``` #### **توضیح ورودی و خروجی نمونه** از نفر شماره‌ی 3 شروع می‌کنیم و 3تا می‌شماریم. پس نفر 5 حذف می‌شود. سپس از نفر شماره‌ی 1 شروع می‌کنیم و خودِ 1 حذف می‌شود. سپس از نفر شماره‌ی 2 شروع می‌کنیم و 2تا می‌شماریم، پس نفر 3 حذف می‌شود. در مرحله‌ی آخر از نفر شماره‌ی 4 شروع می‌کنیم و 4تا می‌شماریم. پس نفر 2 حذف می‌شود. بنابراین نفر شماره‌ی 4 برنده‌ی بازی خواهد بود.

علیرضا که تصمیم دارد از این به بعد همیشه نمازهایش را اول وقت بخواند کمی در این زمینه وسواس پیدا کرده، جوری که دائم به ساعت نگاه می‌کند و در ذهنش محاسبه می‌کند که دقیقاً چقدر تا اذان باقی مانده است. اما این محاسبه معمولاً سخت و وقت‌گیر است! برای کمک به او برنامه‌ای بنویسید که دو رشته به صورت ثانیه:دقیقه:ساعت ورودی بگیرد که اولی زمان فعلی و دومی زمان اذان است، و در قالب ثانیه:دقیقه:ساعت چاپ کند که چقدر تا اذان باقی مانده است. ## **ورودی** دو رشته‌ی هشت‌حرفی (در دو خط جداگانه) به صورت ثانیه:دقیقه:ساعت که حتماً دومی زمانی دیرتر از اولی است. ## **خروجی** یک رشته‌ی هشت‌حرفی به صورت ثانیه:دقیقه:ساعت ### **ورودی نمونه‌ی 1** ``` 18:00:34 19:40:37 ``` ### **خروجی نمونه‌ی 1** ``` 01:40:03 ``` ### **ورودی نمونه‌ی 2** ``` 09:05:01 20:04:27 ``` ### **خروجی نمونه‌ی 2** ``` 10:59:26 ```

علی و آرش پس از ناکامی در برنامه‌نویسی، تصمیم گرفتند این کار را کنار بگذارند. آنها پس از جست‌وجوی بسیار شغلی ساده‌تر از نگهبانی یک پارکینگ طبقاتی پیدا نکردند! هر روز صبح ساعت 6، علی درب پارکینگ را باز می‌کند. او هر ساعت یک پیامک به آرش (که در جای دیگری مشغول کار است) می‌زند و با نوشتن دو عدد به او اطلاع می‌دهد در یک ساعت گذشته چند خودرو وارد پارکینگ و چند خودرو خارج شده‌اند. پس از 18 ساعت، در ساعت 12 شب علی آخرین پیامک را نیز می‌فرستد. در این زمان آرش وظیفه دارد تعدادی «جرثقیل خودروبر» به پارکینگ بفرستد تا خودروهای باقی مانده در پارکینگ را خارج کنند، ولی خودش حوصله‌ی محاسبه‌ی تعداد جرثقیل‌های مورد نیاز را ندارد. بنابراین به فکر نوشتن یک برنامه می‌افتد (که آن را هم طبیعتاً خودش بلد نیست!) تا از روی پیامک‌ها تعداد خودروهای باقی مانده در پارکینگ را محاسبه کند. ## **ورودی** 36 عدد صحیح در خطوط جداگانه که به ترتیب نشان‌دهنده‌ی تعداد خودروهای واردشده در ساعت اول، تعداد خودروهای خارج‌شده در ساعت اول، تعداد خودروهای واردشده در ساعت دوم، تعداد خودروهای خارج‌شده در ساعت دوم و ... است. ## **خروجی** یک عدد صحیح که نشان‌دهنده‌ی تعداد خودروهای باقی‌مانده در پارکینگ است.

هزارپایی می‌شناسیم که n جفت پا دارد. سایز دو پای هرجفت یکسان است، ولی سایز جفت‌ها با هم برابر نیست. m جفت کفش هم داریم، با سایزهای متفاوت. می‌خواهیم کفش‌ها را پای هزارپا کنیم، جوری که اولاً پایش بروند (اگر کوچک‌تر باشند نمی‌روند)، ثانیاً مجموع اختلاف سایز کفش با پاها کمینه شود. # ورودی در خط اول $n$ تعداد پاها، و در خط دوم $m$ تعداد کفش‌ها می‌آید ($m\geq n$). سپس در $n$ خط بعدی سایز پاها به صورت اعدادی طبیعی می‌آیند. نهایتاً در $m$ خط آخر هم سایز کفش‌ها به صورت اعدادی طبیعی خواهند آمد. # خروجی در $n$ خط سایز کفش‌هایی که پای هزارپا می‌کنیم (ترتیب پاها همان است که در ورودی آمده بود). اگر جوابی وجود نداشت، خروجی باید NO ANSWER باشد. ## ورودی نمونه‌ی ۱ ``` 4 5 2 4 6 8 1 3 5 7 9 ``` ## خروجی نمونه‌ی ۱ ``` 3 5 7 9 ``` ## ورودی نمونه‌ی ۲ ``` 5 8 9 3 5 7 1 2 1 5 5 9 10 12 10 ``` ## خروجی نمونه‌ی ۲ ``` 10 5 5 9 1 ``` ## ورودی نمونه‌ی ۳ ``` 2 2 2 3 3 1 ``` ## خروجی نمونه‌ی ۳ ``` NO ANSWER ```

در مسابقات اتومبیل‌رانی فرمول یک، هر دوری که با یک لاستیک دور پیست زده می‌شود باعث کاهش کیفیت لاستیک و در نتیجه افزایش زمان دورهای بعدی ماشین می‌شود. بنابراین بعد از این که راننده‌ها با یک لاستیک تعدادی دور زدند، افزایش زمان دورهایشان به قدری می‌شود که می‌ارزد زمانی را صرف تعویض لاستیک کنند، ولی دورهای بعد از تعویض لاستیک‌شان سریع‌تر برانند. فرض کنید یک راننده با یک لاستیک نو یک دور را در t ثانیه می‌زند و هر دوری که با یک لاستیک می‌زند کاهش کیفیت لاستیک به اندازه‌ای است که دور بعدی 1 ثانیه بیش‌تر طول می‌کشد. هم‌چنین تعویض لاستیک p ثانیه طول می‌کشد. اگر تعداد دورهای مسابقه r دور باشد، بهتر است راننده در طول مسابقه چندبار لاستیک‌هایش را تعویض کند؟ # ورودی اعداد طبیعی $t$ و $p$ و $r$ به ترتیب در سه خط می‌آیند. # خروجی یک عدد که نشان‌دهنده‌های تعداد تعویض‌ بهینه‌ی لاستیک‌هاست. ## ورودی نمونه‌ی ۱ ``` 10 4 20 ``` ## خروجی نمونه‌ی ۱ ``` 6 ``` ## ورودی نمونه‌ی ۲ ``` 120 20 57 ``` ## خروجی نمونه‌ی ۲ ``` 8 ``` ## ورودی نمونه‌ی ۳ ``` 100 50 10 ``` ## خروجی نمونه‌ی ۳ ``` 0 ```

تعدادی ساعت شنی داریم که زمان خالی شدن هرکدام مشخص است. می‌دانیم با استفاده‌ی پشت سر هم یا هم‌زمان از دو ساعت شنی می‌توانیم زمان‌های جدیدی نیز اندازه بگیریم. به طور مثال اگر دو ساعت شنی ۳ و ۲ دقیقه‌ای داشته باشیم، با استفاده‌ی پشت سر هم و هم‌زمان آنها می‌توانیم زمان‌های ۵ و ۱ دقیقه را اندازه‌گیری کنیم. می‌خواهیم کوچک‌ترین زمانی را به دست بیاوریم که با استفاده از **حداکثر دو تا** از ساعت‌های شنی موجود نتوانیم آن را اندازه‌گیری کنیم. دقت کنید که تنها یک بار می‌توان از ساعت‌ها استفاده کرد. # ورودی ابتدا تعداد ساعت‌های شنی به صورت عدد طبیعی $n$ می‌آید. در $n$ خط بعدی، در هر خط یک عدد طبیعی می‌آید که زمان قابل اندازه‌گیری توسط یکی از ساعت‌های شنی را مشخص می‌کند. # خروجی یک عدد طبیعی که نشان‌دهنده‌ی کوچک‌ترین زمانی است که با یک بار استفاده از حداکثر دو تا از ساعت‌های شنی نتوان آن را اندازه‌گیری کرد. ## ورودی نمونه‌ی ۱ ``` 4 6 10 2 3 ``` ## خروجی نمونه‌ی ۱ ``` 11 ``` ## ورودی نمونه‌ی ۲ ``` 5 1 2 3 5 5 ``` ## خروجی نمونه‌ی ۲ ``` 9 ``` ## ورودی نمونه‌ی ۳ ``` 3 2 1 3 ``` ## خروجی نمونه‌ی ۳ ``` 6 ```

روش رمزگذاری‌ای اختراع کرده‌ایم که بر اساس «جبر رشته‌ای» است. در جبر رشته‌ای، فقط دو عملگر جمع و تفریق داریم. عملگر جمع، دو رشته را کنار هم می‌چسباند، و عملگر تفریق اولین رخ‌داد یک رشته را از رشته‌ی دیگر حذف می‌کند (اگر هیچ موردی از رشته‌ی اول در رشته‌ی دوم پیدا نشد، عملگر تفریق کاری انجام نمی‌دهد). جبر رشته‌ای از چپ به راست و بدون اولویت عمل می‌کند. روش رمزگذاری ما به این شکل است که پیام رمزشده یک عبارت با جبر رشته‌ای است و پیام اصلی با حساب کردن حاصل این عبارت به دست می‌آید. # ورودی یک رشته‌ شامل حروف کوچک الفبای انگلیسی و کاراکترهای + و - که پیام رمزشده‌ی ماست. # خروجی یک رشته که پیام اصلی (رمزگشایی‌شده) خواهد بود. ## ورودی نمونه‌ ``` abd-db+hty-t ``` ## خروجی نمونه‌ ``` abdhy ```

در مجلس یک کشور که n نماینده دارد، هر یک از نمایندگان به حزبی تعلق دارند. طبق قانون اساسی، دولت در صورتی می‌تواند تشکیل شود که یک حزب یا ائتلافی از چند حزب، اکثریت (بیش از نصف) نمایندگان مجلس را در اختیار داشته باشند. در این میان، ائتلافی «شکننده» است که اکثریت دارد، اما با خروج **حداقل یکی** از احزاب از آن ائتلاف (یعنی خروج همه‌ی نمایندگان آن حزب از ائتلاف)، از اکثریت می‌افتد. از آن‌جا که ائتلاف‌های شکننده، خطرناک و بی‌ثبات‌اند می‌خواهیم بدانیم چند ائتلاف شکننده‌ی ممکن در مجلس این کشور قابل تشکیل است. بدیهی است که هر ائتلاف حداقل از دو حزب تشکیل می‌شود. # ورودی ابتدا عدد طبیعی $m$ می‌آید که تعداد احزابی را که در مجلس نماینده دارند نشان می‌دهد. در $m$ خط بعدی، تعداد نماینده‌ی عضو هر حزب خواهد آمد. # خروجی تعداد ائتلاف‌های شکننده‌ی ممکن به صورت یک عدد صحیح نامنفی ## ورودی نمونه‌ی ۱ ``` 3 20 5 15 ``` ## خروجی نمونه‌ی ۱ ``` 3 ``` ## ورودی نمونه‌ی ۲ ``` 2 10 5 ``` ## خروجی نمونه‌ی ۲ ``` 1 ```

صبح برای آماده شدن پیراهنی پوشیده‌ایم که $n+1$ دکمه دارد. اول از همه دکمه‌ی اول و آخرش را می‌بندیم. از آن‌جایی که خیلی عجله داریم، همین‌طوری از خانه بیرون می‌رویم و بین راه بقیه‌ی دکمه‌ها را می‌بندیم. هر طولی از پیراهن (بین دو دکمه) که دکمه‌هایش بسته نشده باشند، در هر دقیقه «زشتی»‌ای ایجاد می‌کنند که برابر است با توان دوم آن طول منهای یک. یعنی اول کار زشتی پیراهن $n^2-1$ (مثلاً اگر ۱۱تا دکمه داشته باشیم و فقط اولی و آخری بسته باشند، زشتی این بازه می‌شود ۹۹ در هر دقیقه). ما در هر دقیقه می‌توانیم یک دکمه را ببندیم. می‌خواهیم به ترتیبی دکمه‌ها را ببندیم که **مجموعِ** زشتیِ نمای پیراهنمان تا وقتی که همه‌ی دکمه‌ها بسته شوند کم‌ترین مقدار ممکن باشد. # ورودی عدد طبیعی $n<1000$ (که یکی کم‌تر از تعداد دکمه‌هاست). # خروجی یک عدد طبیعی که حداقل مجموع زشتی ممکن است. ## ورودی نمونه ``` 6 ``` ## خروجی نمونه ``` 71 ```

در مسابقات وزنه‌برداری، شرکت‌‌کنندگان هم در یک‌ضرب (بالا بردن بی‌توقف وزنه تا بالای سر) و هم در دوضرب (بالا بردن وزنه تا روی سینه و سپس بالا بردن آن تا بالای سر) وزنه‌ها را بلند می‌کنند. وزنه‌برداران در یک‌ضرب و دوضرب جداگانه رتبه‌بندی می‌شوند (بر اساس میزان وزنی که توانسته‌اند بلند کنند) و رتبه‌بندی نهایی آنها نیز بر اساس مجموع میزان وزنی است که در یک‌ضرب و دوضرب بالای سر برده‌اند. یک وزنه‌بردار اخیراً در پنج مسابقه‌ی مختلف شرکت کرده و در یک‌ضرب و دوضرب هر کدام رتبه‌هایی به دست آورده. او ادعایی در مورد رتبه‌بندی نهایی‌اش دارد. می‌خواهیم بدانیم ادعای او درست است یا نه. # ورودی ۵ سری عدد، که در خطوط جداگانه می‌آیند و در هر سری به ترتیب ابتدا تعداد کل شرکت‌کنندگان در مسابقه ($n$)، سپس رتبه‌ی وزنه‌بردار در یک‌ضرب ($r1$)، بعد رتبه‌ی وزنه‌بردار در دوضرب ($r2$) و نهایتاً رتبه‌ی نهایی ادعایی او ($rc$) به صورت اعدادی طبیعی می‌آید. # خروجی ۵ خط که در هر خط بسته به ادعای راست یا دروغ وزنه‌بردار به ترتیب حرف R یا حرف D (حروف بزرگ) می‌آید. ## ورودی نمونه ``` 9 8 8 4 5 1 2 1 11 3 5 1 4 4 4 3 6 1 2 4 ``` ## خروجی نمونه ``` D R R D D ```