خاله مهشید و عمه کیمیا که مسئول برگزاری مسابقات ** ۷ سنگ** غرب آسیا هستند ، بنا به دلایلی در اجرای این دوره از مسابقات ۷ سنگ دچار مشکل شدند و حسابی به تیپ و تاپ هم زدند. از آنجا که این ۲ عزیز علاقه خاصی به دعوا کردن دارند . تصمیم میگیرند که به نوبت بر سر هم بکوبند.
با شروع از مهشید(اول مهشید دعوا را آغاز میکند) ابتدا مهشید یکی بر سر کیمیا میکوبد ، سپس کیمیا ۲ ضربه به سر مهشید ، مهشید ۳ ضربه به سر کیمیا ، کیمیا ۴ ضربه بر سر مهشید و .... به همین ترتیب. متاسفانه اگر K ضربه متوالی(در یک حرکت) به سر یکی از این ۲ عزیز بخورد گریهاش میگیرد و میبازد. حال ما به شما K رو میدهیم و شما بازنده را به درستی پیش بینی کنید.
در تنها خط ورودی K به شما داده میشود.
در تنها خط خروجی در صورتی که در نهایت کیمیا بازنده میشود "kimia" و در صورتی که مهشید بازنده دعوا میشود عبارت "mahshid" را چاپ کنید.
یک حلزون خسته روی یک میلهی عمودی و دقیقا در ارتفاع صفر آن قرار دارد. این حلزون میخواهد به ارتفاع d از میله برسد بدین منظور او هر روز a کیلومتر !! به بالا میرود اما شب ها که میخوابد b کیلومتر به پایین میآید. حال حلزون ما میخواهد بداند اگر فردا و از ارتفاع صفر کار خودش را شروع کند اولین روزی که به ارتفاع d کیلومتر میرسد دقیقا چند روز بعد از شروع کارش است . [تضمین میشود که حلزون خسته قصه ما حتما میتواند به مقصد ش برسد]
در تنها خط ورودی به ترتیب ۳ عدد a , b , d به شما داده میشود.
در یک خط کمترین تعداد روز لازم برای رسیدن به ارتفاع d کیلومتر را چاپ کنید.
توضیح نمونه ۱ : حلزون میخواهد به ارتفاع ۴ برسد.
صبح روز اول ۲ کیلومتر بالا میرود و به ارتفاع ۲ ک.م میرسد اما همان شب ۱ ک.م پایین میآید و در انتهای روز در ارتفاع ۱ ک.م قرار میگیرد.
صبح روز دوم ۲ ک.م بالا میرود و به ارتفاع ۳ ک.م میرسد اما همان شب ۱ ک.م پایین میآید و در انتهای روز در ارتفاع ۲ قرار میگیرد.
صبح روز سوم ۲ ک.م بالا میرود و به ارتفاع ۴ میرسد.
در نتیجه اولین روزی که حلزون به ارتفاع ۴ میرسد روز سوم است.
کیمیا به تازگی در بانک خستگان استخدام به کار شده . از آنجا که اغلب کارمندان این بانک همیشه خسته اند ، دشوارترین کار بانک را به کیمیا سپرده اند. روزانه در بانک خستگان N درخواست برای تراکنش (به ترتیب) داده میشود که مقدار تراکنش i ام برابر [a[i است. وظیفه ی کیمیا این است که نگذارد مجموع تراکنش های یک روز از K بیشتر شود ، به همین منظور هنگامی که احساس می کند تراکنش بعدی باعث میشود که مجموع مقدار تراکنش ها از K بیشتر شود ، بلافاصله سیستم بانک را خاموش میکند . وظیفه ی شما به دست آووردن تعداد تراکنش های موفق است ؛ یا به زبانی ساده تر بیشترین عدد p ای را چاپ کنید که مجموع p عدد اول آرایهی a کمتر یا مساوی K باشد.
در خط اول ورودی ۲ عدد N , K به شما داده میشود که نمایانگر تعداد تراکنش ها و سقف تراکنش روزانه است. در خط دوم به شما N عدد داده میشود که عدد i ام نمایانگر مقدار تراکنش i ام([a[i) است.
در تنها خط خروجی تعداد تراکنش های موفق را چاپ کنید.
در برکهای n برگ نیلوفر آبی روی محور افقی مختصات قرار گرفته اند ، برگ i ام در فاصله ی [x[i از مبدا مختصات قرار دارد ، بابا قوری به جهیدن علاقه ی خاصی دارد و میتواند تا حداکثر به طول L در یک جهش بپرد(به چپ یا راست). *در آغاز کار بابا قوری روی برگی که فاصله اش تا مبدا [1]x هستش ، نشسته است *؛ او در هر مرحله به طولی دلخواه ( حداقل ۱ و حداکثر L ) میجهد و روی برگی دیگر فرود میآید (دقت کنید که بابا قوری نمیتواند به جایی بجهد که در آنجا برگ وجود نداشته باشد). از آنجا که بابا قوری داستان ما حیوان آینده نگری است قبل از آغاز جهیدن میخواهد بداند چه تعداد برگ وجود دارند که با یک سری از جهش ها میتوان به آن رسید.
در خط اول ورودی n , L داده میشود که به ترتیب نمایانگر تعداد برگ ها و بیشینه جهش باباقوری است. در خط دوم n عدد آمده که عدد iام نمایانگر فاصلهی برگ i ام از مبدا است (همان [x[i) تمامی [i[x ها متمایز اند.
در تنها خط خروجی تعداد برگ هایی را بگویید که با یک سری از جهش ها می توان به آن رسید.
مهشید ، جمشید و خوورشید برای رسیدن به مسابقهی ** " تِکواندوش " ** در پاتایا ، از هتل سوار اتوبوس شدند. اتوبوسهای پاتایا تنها دو ردیف صندلی دارند که هر ردیف دارای دقیقا ۱۰ صندلی است. فاصلهی صندلیهای متوالی در یک ردیف دقیقا یک متر است و فاصلهی صندلیهای مجاور در دو ردیف مجزا(صندلی مجاور چپ یا راست)، دو متر است. بعضی از صندلیها توسط آدمهای دیگر اِشغال هستند! آنها میخواهند بهگونهای روی صندلیها بنشینند که مجموع فاصلهی دو به دوی آنها کمینه شود! به آنها بگویید کمترین مجموع فاصلهی دو به دوی آنها چقدر است.
ورودی شامل ۲ خطِ ۱۰ کاراکتری است که هر کاراکتر نشان دهندهی یک صندلی داخل اتوبوس است. در صورت خالی بودن یک صندلی کاراکتر '-' و در صورت اشغال بودن آن کاراکتر 'X' گذاشته شده. تضمین میشود که حداقل ۳ صندلی داخل اتوبوس خالی است .
در تنها خط خروجی کمترین مجموع فاصلهی دو به دوی پرهام و میلاد و آرمین را چاپ کنید!(جواب شما باید تا حداقل ۹ رقم اعشار دقت داشته باشد!)
در مثال بالا حالت بهینه این است که هر ۳ نفر در یک ردیف و به صورت متوالی بشینند.
در نزدیکی خونه ی پرهام یک درخت دودویی پُر وجود دارد که هر از گاهی پرهام به وقت گذرانی در آن میپردازد . در نظریه گراف ها درختی را دودویی پُر گوییم که اولا ریشه دار باشد و ثانیا تمامی راس های آن دارای ۲ فرزند باشند به جز راس های سطح آخر که هیچ فرزندی ندارند .
درخت نزدیک خانه ی پرهام دارای ارتفاع H است (ارتفاع در درخت دودویی پُر فاصلهی یک برگ تا ریشه در نظر گرفته میشود) .
شهرداری برای این که ابراز وجود کند راس های درخت دودویی پُر را به گونه ای ابلهانه عددگذاری کرده به این صورت که ابتدا عدد x را برابر تعداد راس های درخت در نظر گرفته و سپس از سطح صفر (در هر سطح از چپ به راست ) شروع میکند و عدد x را به راس فعلی نسبت میدهد و سپس از x یکی میکاهد و هنگامی که سطح فعلی درخت کامل عدد گذاری شد سراغ سطح بعدی میرود و .... تا کل راس ها عدد گذاری شوند.
پرهام که امروز به پارک رفته بود ، درخت دودویی پُر را میبیند که به تازگی عدد گذاری شده . سپس فکری به سرش میزند .
او روی ریشه درخت می ایستد و در هر حرکت به یکی از ۲ راس سطح پایین تر راس فعلی (فرزند چپ یا راست میرود) .
پس از تعدادی حرکت پرهام میخواهد بدون نگاه کردن به عدد راسی که در آن ایستاده آن را حدس بزند در نتیجه در همان حال با ما تماس گرفت و این سوال را مطرح کرد تا بلکه کمک شما شامل حالش شود .
نمونه درخت دودویی به ارتفاع ۳ که راس هایش توسط شهرداری عدد گذاری شده !
در تنها خط ورودی ابتدا H (ارتفاع درخت دودویی پر) و سپس رشته ای ناتهی به طول حداکثر H ، شامل حرکت پرهام روی درخت (متشکل از L و R) آمده.(حرف i ام رشته L است اگر و فقط اگر پرهام در حرکت i ام خود به فرزند سمت چپ راس فعلی رفته باشد )
در تنها خط خروجی عدد راسی که پرهام روی آن قرار دارد را چاپ کنید.
توضیح این مثال در شکل بالا قابل فهم است.
توضیح این مثال در شکل بالا قابل فهم است.
آرمین به شهربازی رفته و با یک بازی عجیب روبهرو شده است. بازی از این قرار است که شرکتکننده باید با استفاده از n رقم اول در مبنای ده (0, 1, …, n-1)، یک عدد بسازد و به اندازهی عددی که ساخته کُپُن روغن نباتی دریافت میکند. اما این بازی کُپُن مفتی به کسی نمیدهد و به ازای هر بار استفاده از رقم i-1 ام شما باید[i]a تومان بپردازید. آرمین با C تومان پولی که در جیب دارد میخواهد در این بازی شرکت کند. بیشترین کُپُن روغن نباتی که آرمین میتواند در این بازی به دست آورد چقدر است؟
در اولین خط ورودی ، به ترتیب ۲ عدد n , C به شما داده میشود . در خط دوم ورودی ، n عدد آمده که عدد iام نمایانگر هزینهی هربار استفاده از رقم i-1 ام است.(همان [i]a)
در تنها خط خروجی بیشترین جایزهای که آرمین میتواند برنده شود را چاپ کنید.
*دقت کنید که عدد چاپشده نباید دارای صفر سمت چپ(صفر پشت عدد) باشد! *
در مثال بالا هزینه ی استفاده از رقم ۲ برابر ۸ ؛ هزینه ی استفاده از رقم ۱ برابر ۷ و هزینه ی استفاده از رقم صفر برابر ۶ است.
این سوال دارای زیر مسئله میباشد کیمیا که به تازگی در کلاس های شمشیر بازی ثبتنام کرده ، یکی از لازمه های یک شمشیر باز ماهر را امضا زدنِ با شمشیر میداند . به همین منظور ابتدا ۲ عدد A , B را انتخاب میکند و سپس به ازای تمامی مقادیر صحیح ** و **خطی به معادله ی روی یک کاغذ میکشد (این اتفاق در کمتر از ۱ نانو ثانیه میافتد) و پس از این که تمامی خطوط را با شمشیرش کشید ، به یک باره تمامی کاغذ به قطعه های حاصل از ضربات شمشیر تبدیل میشود. وظیفه ی شما شمردن این تکه هاست :) .
در تنها خط ورودی ۲ عدد A , B داده میشود. زیر مسئله کوچک : در ۱۰ نمره از ۱۰۰ نمره این سوال فرضیات زیر رعایت شده.
در تنها خط خروجی تعداد تکه های کاغذ بعد از ضربات مرگبار کیمیا را چاپ کنید.
شکل پس از ضربات برای نمونه ۲
این سوال دارای زیر مسئله میباشد
آقای هاشمی پس از آن که نتوانست مخارج خانواده خود را با کار در کتاب های درس اجتماعی دوره ابتدایی تامین کند به علم احتمالات روی آورد تا بتواند در مسابقات شانسی مختلف شرکت کند و پولی به جیب بزند. در همین راستا آقای هاشمی برای شرکت در یکی از بزرگترین مسابقات شانسی شرق آسیا برنامه ریزی کرده . نحوه ی بازی در این مسابقه به این صورت است که هر فردی که در مسابقه ثبتنام کرده همراه با دقیقا N سکه به جایگاه مسابقات میرود سپس تا هنگامی سکه ای براش باقی مانده تعدادی سکه را به انتخاب خود به داور مسابقات میدهد .(سکه ای که به داور داده شود دیگر از کف شرکت کننده رفته است)
سپس داور مسابقات این دسته سکه جدید را به هوا پرتاب میکند و پس از این که سکه ها روی زمین متوقف شدند ، تعداد سکه هایی(از دسته جدید) که شیر آمده را میشمارد و در صورتی که این تعداد از K کمتر نبود یک شمش طلا به فرد میدهد اینکار آنقدر ادامه پیدا میکند که هیچ سکه ای برای شرکت کننده نمانده باشد.(ممکن است یک فرد بیش از یک شمش ببرد). حتما تا الآن فهمیدهاید که هزینهی ورود به این مسابقات در واقع همان N سکه طلاست که به هیچ وجه قابل برگشت نیست و اگر بخواهی شانست را امتحان کنی (چه ببری چه ببازی) باید این N سکه را فدا کنی . آقای هاشمی قطعاً به کمک شما نیاز داره ؛ در نتیجه ایشان به شما N , K و احتمال شیر آمدن یک سکه (P) را میگوید و از شما میخواهد به او بگوید که اگر به صورت بهینه(optimal) به داور سکه بدهد امید ریاضی تعداد شمش هایی که میبرد چقدر است .
در تنها خط ورودی به ترتیب ۳ عدد N , K , P به شما داده میشود.
زیر مسئله کوچک : در ۳۰ نمره از ۱۰۰ نمره این سوال فرض زیر رعایت شده.
در تنها خط خروجی جواب سوال آقای هاشمی را (با دقتِ ۶ رقم اعشار) چاپ کنید.
توضیح نمونه ۱ : حالت یک دسته دوتایی: امید ریاضی تعداد شمش در این حالت برابر ۰.۷۵ میشود.
حالت دو دسته یکیای: امید ریاضی تعداد شمش در این حالت (۰.۵ + ۰.۵) برابر 1 میشود.
در نتیجه امید ریاضی بهینه برابر یک میشود.