+ رنگ بادکنک: نارنجی + محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۵۰ مگابایت ---------- خاله مهشید و عمه کیمیا که مسئول برگزاری مسابقات ** ۷ سنگ** غرب آسیا هستند ، بنا به دلایلی در اجرای این دوره از مسابقات **۷ سنگ** دچار مشکل شدند و حسابی به تیپ و تاپ هم زدند. از آنجا که این ۲ عزیز علاقه خاصی به دعوا کردن دارند . تصمیم می‌گیرند که به نوبت بر سر هم بکوبند. با شروع از مهشید(اول مهشید دعوا را آغاز می‌کند) ابتدا مهشید یکی بر سر کیمیا می‌کوبد ، سپس کیمیا ۲ ضربه به سر مهشید ، مهشید ۳ ضربه به سر کیمیا ، کیمیا ۴ ضربه بر سر مهشید و .... به همین ترتیب. متاسفانه اگر K ضربه متوالی(در یک حرکت) به سر یکی از این ۲ عزیز بخورد گریه‌اش می‌گیرد و می‌بازد. حال ما به شما K رو می‌دهیم و شما بازنده را به درستی پیش بینی کنید. # ورودی در تنها خط ورودی K به شما داده می‌شود. $$1 \le K \le 100$$ # خروجی در تنها خط خروجی در صورتی که در نهایت کیمیا بازنده می‌شود **"kimia"** و در صورتی که مهشید بازنده دعوا می‌شود عبارت **"mahshid"** را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 1 ``` ## خروجی نمونه ۱ ``` kimia ``` ## ورودی نمونه ۲ ``` 74 ``` ## خروجی نمونه ۲ ``` mahshid ```

+ رنگ بادکنک: سفید + محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۵۰ مگابایت ---------- یک حلزون خسته روی یک میله‌ی عمودی و دقیقا در ارتفاع صفر آن قرار دارد. این حلزون می‌خواهد به ارتفاع d از میله برسد بدین منظور او هر روز a کیلومتر !! به بالا می‌رود اما شب ها که می‌خوابد b کیلومتر به پایین می‌آید. حال حلزون ما می‌خواهد بداند اگر فردا و از ارتفاع صفر کار خودش را شروع کند اولین روزی که به ارتفاع d کیلومتر می‌رسد دقیقا چند روز بعد از شروع کارش است . [تضمین میشود که حلزون خسته قصه ما حتما میتواند به مقصد ش برسد] # ورودی در تنها خط ورودی به ترتیب ۳ عدد a , b , d به شما داده می‌شود. $$1 \le b < a \le 100\ 000$$ $$1 \le d \le 100\ 000$$ # خروجی در یک خط کمترین تعداد روز لازم برای رسیدن به ارتفاع d کیلومتر را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 1 4 ``` ## خروجی نمونه ۱ ``` 3 ``` **توضیح نمونه ۱ :** حلزون می‌خواهد به ارتفاع ۴ برسد. صبح روز اول ۲ کیلومتر بالا می‌رود و به ارتفاع ۲ ک.م می‌رسد اما همان شب ۱ ک.م پایین می‌آید و در انتهای روز در ارتفاع ۱ ک.م قرار می‌گیرد. صبح روز دوم ۲ ک.م بالا می‌رود و به ارتفاع ۳ ک.م می‌رسد اما همان شب ۱ ک.م پایین می‌آید و در انتهای روز در ارتفاع ۲ قرار می‌گیرد. صبح روز سوم ۲ ک.م بالا می‌رود و به ارتفاع ۴ می‌رسد. در نتیجه اولین روزی که حلزون به ارتفاع ۴ می‌رسد روز سوم است. ## ورودی نمونه ۲ ``` 5 1 6 ``` ## خروجی نمونه ۲ ``` 2 ```

+ رنگ بادکنک : زرد + محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۵۰ مگابایت ---------- کیمیا به تازگی در **بانک خستگان** استخدام به کار شده . از آنجا که اغلب کارمندان این بانک همیشه خسته اند ، دشوار‌ترین کار بانک را به کیمیا سپرده اند. روزانه در **بانک خستگان** N درخواست برای تراکنش (به ترتیب) داده می‌شود که *مقدار* تراکنش i ام برابر [a[i است. وظیفه ی کیمیا این است که نگذارد مجموع تراکنش های یک روز از K بیشتر شود ، به همین منظور هنگامی که احساس می کند تراکنش بعدی باعث می‌شود که مجموع *مقدار* تراکنش ها از K بیشتر شود ، بلافاصله سیستم بانک را خاموش می‌کند . وظیفه ی شما به دست آووردن تعداد تراکنش های موفق است ؛ یا به زبانی ساده تر **بیشترین** عدد p ای را چاپ کنید که مجموع p عدد اول آرایه‌ی a کمتر یا مساوی K باشد. # ورودی در خط اول ورودی ۲ عدد N , K به شما داده می‌شود که نمایانگر تعداد تراکنش ها و سقف تراکنش روزانه است. $$0 \le N \le 1\ 000$$ $$0 \le K \le 1\ 000\ 000$$ در خط دوم به شما N عدد داده میشود که عدد i ام نمایانگر *مقدار* تراکنش i ام([a[i) است. $$0 \le a[i] \le 1\ 000$$ # خروجی در تنها خط خروجی تعداد تراکنش های موفق را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 7 1 2 1 3 4 ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 5 6 1 2 1 3 4 ``` ## خروجی نمونه ۲ ``` 3 ``` ## ورودی نمونه ۳ ``` 5 16 1 2 1 3 4 ``` ## خروجی نمونه ۳ ``` 5 ```

+ رنگ بادکنک: صورتی + محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۵۰ مگابایت ---------- در برکه‌ای n برگ نیلوفر آبی روی محور افقی مختصات قرار گرفته اند ، برگ i ام در فاصله ی [x[i از مبدا مختصات قرار دارد ، بابا قوری به جهیدن علاقه ی خاصی دارد و می‌تواند تا حداکثر به طول L در یک جهش بپرد(به چپ یا راست). **در آغاز کار بابا قوری روی برگی که فاصله اش تا مبدا [1]x هستش ، نشسته است **؛ او در هر مرحله به طولی دلخواه ( حداقل ۱ و حداکثر L ) می‌جهد و روی برگی دیگر فرود می‌آید (دقت کنید که بابا قوری نمی‌تواند به جایی بجهد که در آنجا برگ وجود نداشته باشد). از آنجا که بابا قوری داستان ما حیوان آینده نگری است قبل از آغاز جهیدن می‌خواهد بداند چه تعداد برگ وجود دارند که با یک سری از جهش ها می‌توان به آن رسید. # ورودی در خط اول ورودی n , L داده می‌شود که به ترتیب نمایانگر تعداد برگ ها و بیشینه جهش باباقوری است. $$1 \le n \le 50$$ $$1 \le L \le 1\ 000$$ در خط دوم n عدد آمده که عدد i‌ام نمایانگر فاصله‌ی برگ i ام از مبدا است (همان [x[i) $$1 \le x[i] \le 1\ 000$$ **تمامی [i[x ها متمایز اند.** # خروجی در تنها خط خروجی تعداد برگ هایی را بگویید که با یک سری از جهش ها می توان به آن رسید. # مثال ## ورودی نمونه ۱ ``` 5 1 4 7 1 3 5 ``` ## خروجی نمونه ۱ ``` 3 ``` ## ورودی نمونه ۲ ``` 5 2 100 101 103 105 107 ``` ## خروجی نمونه ۲ ``` 5 ```

+ رنگ بادکنک: بنفش + محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۰۰ مگابایت ---------- مهشید ، جمشید و خوورشید برای رسیدن به مسابقه‌ی ** " تِک‌وان‌دوش " ** در پاتایا ، از هتل سوار اتوبوس شدند. اتوبوس‌های پاتایا تنها دو ردیف صندلی دارند که هر ردیف دارای دقیقا ۱۰ صندلی است. فاصله‌ی صندلی‌های متوالی در یک ردیف دقیقا یک متر است و فاصله‌ی صندلی‌های مجاور در دو ردیف مجزا(صندلی مجاور چپ یا راست)، دو متر است. بعضی از صندلی‌ها توسط آدم‌های دیگر اِشغال هستند! آن‌ها می‌خواهند به‌گونه‌ای روی صندلی‌ها بنشینند که **مجموع فاصله‌ی دو به دوی** آن‌ها کمینه شود! به آن‌ها بگویید کمترین مجموع فاصله‌ی دو به دوی آن‌ها چقدر است. # ورودی ورودی شامل ۲ خطِ ۱۰ کاراکتری است که هر کاراکتر نشان دهنده‌ی یک صندلی داخل اتوبوس است. در صورت خالی بودن یک صندلی کاراکتر **'-'** و در صورت اشغال بودن آن کاراکتر **'X'** گذاشته شده. **تضمین می‌شود که حداقل ۳ صندلی داخل اتوبوس خالی است .** # خروجی در تنها خط خروجی کمترین مجموع فاصله‌ی دو به دوی پرهام و میلاد و آرمین را چاپ کنید!**(جواب شما باید تا حداقل ۹ رقم اعشار دقت داشته باشد!)** # مثال ## ورودی نمونه ۱ ``` ---------- ---------- ``` ## خروجی نمونه ۱ ``` 4.0000000000 ``` در مثال بالا حالت بهینه این است که هر ۳ نفر در یک ردیف و به صورت متوالی بشینند. ## ورودی نمونه ۲ ``` XXXXXXXXXX -XX-XX-XX- ``` ## خروجی نمونه ۲ ``` 12.0000000000 ``` ## ورودی نمونه ۳ ``` XXX-X-XX-X XXX-X-XX-X ``` ## خروجی نمونه ۳ ``` 6.8284271247 ```

+ رنگ بادکنک: قهوه ای + محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۵۰ مگابایت ---------- در نزدیکی خونه ی پرهام یک درخت دودویی پُر وجود دارد که هر از گاهی پرهام به وقت گذرانی در آن میپردازد . در نظریه گراف ها درختی را دودویی پُر گوییم که اولا ریشه دار باشد و ثانیا تمامی راس های آن دارای ۲ فرزند باشند به جز راس های سطح آخر که هیچ فرزندی ندارند . درخت نزدیک خانه ی پرهام دارای ارتفاع H است (ارتفاع در درخت دودویی پُر فاصله‌ی یک برگ تا ریشه در نظر گرفته میشود) . شهرداری برای این که ابراز وجود کند راس های درخت دودویی پُر را به گونه ای ابلهانه عددگذاری کرده به این صورت که ابتدا عدد x را برابر تعداد راس های درخت در نظر گرفته و سپس از سطح صفر (در هر سطح از چپ به راست ) شروع میکند و عدد x را به راس فعلی نسبت می‌دهد و سپس از x یکی می‌کاهد و هنگامی که سطح فعلی درخت کامل عدد گذاری شد سراغ سطح بعدی میرود و .... تا کل راس ها عدد گذاری شوند. پرهام که امروز به پارک رفته بود ، درخت دودویی پُر را می‌بیند که به تازگی عدد گذاری شده . سپس فکری به سرش میزند . او روی ریشه درخت می ایستد و در هر حرکت به یکی از ۲ راس سطح پایین تر راس فعلی (فرزند چپ یا راست می‌رود) . پس از تعدادی حرکت پرهام میخواهد بدون نگاه کردن به عدد راسی که در آن ایستاده آن را حدس بزند در نتیجه در همان حال با ما تماس گرفت و این سوال را مطرح کرد تا بلکه کمک شما شامل حالش شود .  نمونه درخت دودویی به ارتفاع ۳ که راس هایش توسط شهرداری عدد گذاری شده ! # ورودی در تنها خط ورودی ابتدا H (ارتفاع درخت دودویی پر) و سپس رشته ای ناتهی به طول حداکثر H ، شامل حرکت پرهام روی درخت (متشکل از L و R) آمده.(حرف i ام رشته L است اگر و فقط اگر پرهام در حرکت i ام خود به فرزند سمت چپ راس فعلی رفته باشد ) $$1 \le H \le 30$$ # خروجی در تنها خط خروجی عدد راسی که پرهام روی آن قرار دارد را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 LR ``` ## خروجی نمونه ۱ ``` 11 ``` **توضیح این مثال در شکل بالا قابل فهم است.** ## ورودی نمونه ۲ ``` 3 RRL ``` ## خروجی نمونه ۲ ``` 2 ``` **توضیح این مثال در شکل بالا قابل فهم است.** ## ورودی نمونه ۳ ``` 2 L ``` ## خروجی نمونه ۳ ``` 6 ```

+ رنگ بادکنک : آبی + محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آرمین به شهربازی رفته و با یک بازی عجیب روبه‌رو شده است. بازی از این قرار است که شرکت‌کننده باید با استفاده از n رقم اول در مبنای ده (0, 1, …, n-1)، یک عدد بسازد و به اندازه‌ی عددی که ساخته کُپُن روغن نباتی دریافت می‌کند. اما این بازی کُپُن مفتی به کسی نمی‌دهد و به ازای هر بار استفاده از رقم i-1 ام شما باید[i]a تومان بپردازید. آرمین با C تومان پولی که در جیب دارد می‌خواهد در این بازی شرکت کند. بیشترین کُپُن روغن نباتی که آرمین می‌تواند در این بازی به دست آورد چقدر است؟ # ورودی در اولین خط ورودی ، به ترتیب ۲ عدد n , C به شما داده می‌شود . $$1 \le n \le 10$$ $$1 \le C \le 1\ 000$$ در خط دوم ورودی ، n عدد آمده که عدد iام نمایانگر هزینه‌ی هربار استفاده از رقم i-1 ام است.(همان [i]a) $$1 \le a[i] \le 50$$ # خروجی در تنها خط خروجی بیشترین جایزه‌ای که آرمین می‌تواند برنده شود را چاپ کنید. **دقت کنید که عدد چاپ‌شده نباید دارای صفر سمت چپ(صفر پشت عدد) باشد! ** # مثال ## ورودی نمونه ۱ ``` 3 21 6 7 8 ``` ## خروجی نمونه ۱ ``` 210 ``` در مثال بالا هزینه ی استفاده از رقم ۲ برابر ۸ ؛ هزینه ی استفاده از رقم ۱ برابر ۷ و هزینه ی استفاده از رقم صفر برابر ۶ است. ## ورودی نمونه ۲ ``` 3 30 5 23 24 ``` ## خروجی نمونه ۲ ``` 20 ``` ## ورودی نمونه ۳ ``` 10 5 1 1 1 1 1 1 1 1 1 1 ``` ## خروجی نمونه ۳ ``` 99999 ```

+ رنگ بادکنک: زرشکی + محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۵۰ مگابایت ---------- **این سوال دارای زیر مسئله می‌باشد** کیمیا که به تازگی در کلاس های شمشیر **بازی** ثبت‌نام کرده ، یکی از لازمه های یک شمشیر باز ماهر را امضا زدنِ با شمشیر می‌داند . به همین منظور ابتدا ۲ عدد A , B را انتخاب می‌کند و سپس به ازای تمامی مقادیر صحیح ** $0 \le a < A$ و $0 \le b < B$ **خطی به معادله ی $y = ax + b$ روی یک کاغذ می‌کشد (این اتفاق در کمتر از ۱ نانو ثانیه می‌افتد) و پس از این که تمامی خطوط را با شمشیرش کشید ، به یک باره تمامی کاغذ به قطعه های حاصل از ضربات شمشیر تبدیل می‌شود. وظیفه ی شما شمردن این تکه هاست :) . # ورودی در تنها خط ورودی ۲ عدد ‌A , B داده می‌شود. $$1 \le A , B \le 1200$$ **زیر مسئله کوچک :** در ۱۰ نمره از ۱۰۰ نمره این سوال فرضیات زیر رعایت شده. $$1 \le A , B \le 3$$ # خروجی در تنها خط خروجی تعداد تکه های کاغذ بعد از ضربات مرگبار کیمیا را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 1 1 ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 2 2 ``` ## خروجی نمونه ۲ ``` 9 ``` شکل پس از ضربات برای نمونه ۲ 

+ رنگ بادکنک: سبز + محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- **این سوال دارای زیر مسئله می‌باشد** آقای هاشمی پس از آن که نتوانست مخارج خانواده خود را با کار در کتاب های درس اجتماعی دوره ابتدایی تامین کند به علم احتمالات روی آورد تا بتواند در مسابقات شانسی مختلف شرکت کند و پولی به جیب بزند. در همین راستا آقای هاشمی برای شرکت در یکی از بزرگترین مسابقات شانسی **شرق آسیا** برنامه ریزی کرده . نحوه ی بازی در این مسابقه به این صورت است که هر فردی که در مسابقه ثبت‌نام کرده همراه با دقیقا N سکه به جایگاه مسابقات می‌رود سپس تا هنگامی سکه ای براش باقی مانده تعدادی سکه را به انتخاب خود به داور مسابقات می‌دهد .(سکه ای که به داور داده شود دیگر از کف شرکت کننده رفته است) سپس داور مسابقات این دسته سکه جدید را به هوا پرتاب می‌کند و پس از این که سکه ها روی زمین متوقف شدند ، تعداد سکه هایی(از دسته جدید) که شیر آمده را می‌شمارد و در صورتی که این تعداد از K کمتر نبود یک شمش طلا به فرد می‌دهد اینکار آن‌قدر ادامه پیدا می‌کند که هیچ سکه ای برای شرکت کننده نمانده باشد.(ممکن است یک فرد بیش از یک شمش ببرد). حتما تا الآن فهمیده‌اید که هزینه‌ی ورود به این مسابقات در واقع همان N سکه طلاست که به هیچ وجه قابل برگشت نیست و اگر بخواهی شانست را امتحان کنی (چه ببری چه ببازی) باید این N سکه را فدا کنی . آقای هاشمی **قطعاً** به کمک شما نیاز داره ؛ در نتیجه ایشان به شما N , K و احتمال شیر آمدن یک سکه **(P)** را می‌گوید و از شما می‌خواهد به او بگوید که اگر به صورت بهینه(optimal) به داور سکه بدهد امید ریاضی تعداد شمش هایی که می‌برد چقدر است . # ورودی در تنها خط ورودی به ترتیب ۳ عدد N , K , P به شما داده می‌شود. $$1 \le N , K \le 3000$$ $$0 \le P \le 1$$ **زیر مسئله کوچک :** در ۳۰ نمره از ۱۰۰ نمره این سوال فرض زیر رعایت شده. $$1 \le N \le 10$$ # خروجی در تنها خط خروجی جواب سوال آقای هاشمی را (با دقتِ ۶ رقم اعشار) چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 1 0.5 ``` ## خروجی نمونه ۱ ``` 1.000000000 ``` **توضیح نمونه ۱ :** حالت یک دسته دوتایی: امید ریاضی تعداد شمش در این حالت برابر ۰.۷۵ می‌شود. حالت دو دسته یکی‌ای: امید ریاضی تعداد شمش در این حالت (۰.۵ + ۰.۵) برابر 1 می‌شود. در نتیجه امید ریاضی بهینه برابر یک می‌شود. ## ورودی نمونه ۲ ``` 10 5 0.9 ``` ## خروجی نمونه ۲ ``` 1.180980000 ``` ## ورودی نمونه ۳ ``` 3000 50 0.123 ``` ## خروجی نمونه ۳ ``` 5.712907306 ```