2 تا سوال خوب

به نام اول آموزگار             که اول درسش عشق بود

سلام ملت چطورین، خوبین؟ ای بابا همچنان که همتون زنده‌اید! خوب چه خبرا؟ چه میکنید؟ خوشید؟ سلامتید؟ منم هی، بد نیستم، همچنان غرق الافی!

- متاسفانه - وبلاگمون داره پیش میره به سمت علمی شدن که البته خدارا شکر هنوز با این نویسندگان شازی که داره جای نگرانی وجود نداره، برای همین واسه اینکه لااقل از این افشین کم نیارم گفتم بیام 2 تا سوال بدم، البته اینا مال بعضی از امتحان‌های ceoi بوده که روشون الگوریتم BTM2 اجرا شده. برای همین یه دفعه ممکنه راه حل‌هایی آسون‌تر از اون چیزی که تو ذهنمه داشته باشن و بعبارتی سوال سوت بشه. اما در هر صورت سوال‌های خوبین و جدا اونقدر قشنگ هستند که کاملا پتانسیلشو دارن شبیهشون توی مرحله دوم بیاد. در مورد اینکه حلشون رو بذاریم یا نه هنوز بحثش نشده، ولی احتمالا حلشون رو خواهم گذاشت. در مورد اینکه بچه‌ها حل کنند و واسمون میل بزنن تا ما تصحیحشون کنیم هم هنوز تصمیمی گرفته نشده. ا راستی یادم رفته بود ممکنه بعضی از افراد کوته‌فکر -که امیدوارم ما از این بازدیدکننده‌ها نداشته باشیم- ندونن BTM2 چیه. محض اطلاعشون بگم BTM2 مخفف "بچپونش تو مرحله 2" هست. که به شخصه معتقدم تعداد(شاید اندکی) از سوال‌های مرحله 2 و بسیاری از سوالهای مرحله 3 توسط همین الگوریتم BTM2 ویا BTM2++ = BTM3 ساخته شدن. در هر صورت این هم سوال‌ها:

1) n عدد طبیعی روی یک خط چیده شده‌اند. با نام‌های a1 تا an. حالا ما یک حرکت مجاز داریم و آن اینست که یک i بین 1 تا کمتر از n در نظر بگیریم و ai و a i+1 را حذف کرده به جاش ai - ai+1 رو میذاریم یعنی میشه n-1 عدد. حالا هی این کار رو تکرار میکنیم تا بشه 1 عدد. مثلا یک نمونه برای n=4 اینگونه عمل میکنه:

1 12 4 9          --2-->         1 8 9         --2-->         1 -1         --1-->       2

حالا فرض کنید در حالت خاصی از سوال داشته باشیم ai=2^i یعنی اعداد اولیمون (الزامی برای رعایت این شرط در ادامه‌ی مراحل وجود ندارد) 2 و 4 و 8 و 16 و ... است. سوال اینه که ما در آخر که فقط یک عدد می ماند، چند حالت مختلف برای آن عدد وجود دارد؟(در حالت کلی سوال اینه که حداکثر چند عدد مختلف وجود دارد به ازای هر اعداد ابتدایی)

2) n پله با شماره‌های 1 تا n جلوی دروازه‌ی شهر الموت قرار دارد.(دروازه در پله‌ی n ام است) تعدادی متناهی سرباز روی این پله‌ها ایستاده‌اند(در پله‌ی iام ai سرباز). این سرباز‌ها که مال چنگیزخان هستند، میخوان بریزن و الموت رو تصرف کنند. شهردار الموت که آدم صلح طلبی(بی بخاری) هست، واسه‌ی اینکه کشتار زیادی نشه میاد پیشنهاد یه بازی میده و چنگیزخان هم که میبینه بازی شازی هست، قبول میکنه. بازی اینجوریه که هر مرحله چنگیزخان همه‌ی سربازهاش رو به دو دسته (نه الزاما مساوی و نه الزاما ناتهی) تقسیم میکنه، شهردار یکی از دسته‌ها رو انتخاب میکنه و اون دسته بر میگردن مغلستان واسه دوره‌ی طلا(که درحقیقت دودر میشن)، اما اون دسته‌ی باقیمونده هرکدوم یک پله میان بالا. و بازی همینجور ادامه پیدا میکنه. حالا اگه حداقل یک سرباز برسه به دروازه‌ی الموت(پله‌ی nام) شهردار، الموت رو تسلیم میکنه، اما اگر همه‌ی سربازها برگشتن... خوب معلومه دیگه چنگیزخان از دنیا سوت میشه...

نکته اینجان که شهردار الموت خیلی باهوشه و اگه بتونه چنگیزخان رو شکست بده، شکستش میده. اما از بدشانسی چنگیزخان هم یکی از بروبچ المپیاد کامپیوتری اون زمان رو که دوروبره الموت الاف بوده گرفته و در نتیجه چگیزخان هم بهترین بازیش رو میکنه. و خوب چون میدونیم الموت تصرف شده، حالا سوال اینه که شرط اگر و فقط اگر برای اینکه چنگیزخان برده چیه؟(مسلما بر اساس ai ها)

البته توجه کنید که وقتی اون بنده خدای الاف رو میگیرن به هیچوجه حاضر به همکاری نمیشه(عرق ملی) اما چنگیزخان نامرد با وعده‌ی یه لبتاپ اونو فریب میده و تازه بعد از فتح الموت بهش لبتاپ که نمیده هیچ، اونو میکشه و بعدها وقتی که میخوان چنگیزخان رو بکشن، با لباس اون بیچاره خودش رو میزنه جای رئیس کمیته‌ی کامپیوتر و فرار میکنه.

بطور مثال اگر توی پله‌ی n-1ام 1 نفر و توی پله‌ی n-2ام 2 نفر ایستاده باشن، اونوقت چنگیزخان افراد پله‌ی n-2ام رو میکنه یه دسته و اون یکی سرباز رو هم میکنه یه دسته. حالا شهردار مجبوره اون دسته‌ی نفر توی پله‌ی n-1ام رو حذف کنه و در مرحله‌ی بعدی چنگیزخان 2 نفر در پله‌ی n-1ام خواهد داشت، که با تقسیم اونها به 2 دسته خواهد برد.

 

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

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

یا حق