المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی سوم:دوره‌ی ۲۱:سوال ۸

مجلس سنای تمساح‌ها

آیدین کاری کرد که رستم برنده بشود و رستم خان هم با افتخار جلوی بقیه دست‌هاش رو بالا برد و این پیروزی رو به همه تمساح‌های لوطی‌منش و جوانمرد، تقدیم کرد و یه دور هم بعدش دور بقیه تمساح‌ها ‎«دور افتخار‎» زد‎!‎ بعد که سرش خلوت شد، پیش ‎آیدین اومد و گفت ‎«ببین مهندس جان، شُما که کارتون خیلی درسته، بیا یه مردونگی کن یه مشکل دیگه از ما رو هم حل کن‎.» آیدین‎ که چاره‌ی دیگری نداشت، گفت: ‎«جانم، بگو گلم».‎

رستم گفت ‎«ببین ما زیر آب جمعاً ‎۱۳۹۰‎ تا تمساح هستیم. هر تمساح یه شماره شناسایی منحصربفرد داره که بین ‎۱‎ تا ‎۱۳۹۰‎ هست. این تمساح‌های ما یه عادت بدی که دارن اینه که اگه دوتاشون با شماره ‎$A$‎ و ‎$B$‎ بین‌شون این رابطه برقرار باشه که ‎$A=B\times 2^K$ (برای یک ‎$K$‎ی صحیح و ناصفر دلخواه)، در اون صورت حتماً اینا با هم دعوا می‌کنن‎!‎ مثلاً همین پریروز تمساح ‎۱۷‎ زد نصف پوزه‌ی تسماح ‎۶۸‎ رو با لگد صاف کرد؛ یا هفته پیش تمساح شماره ‎۱۱۰‎ دم تسماح شماره‌ی ‎۴۴۰‎ رو، وقتی یارو خواب بود، به لنگر یه قایق موتوری بست‎!‎

از اون‌ور هم، حساب کن که ما می‌خوایم یه مجلس سنای تمساح‌ها تشکیل بدیم که توش تعداد زیادی از تمساح‌ها رو بیاریم. اما خب می‌خوایم که اولاً هیچ دو تمساحی از تمساح‌های مجلس‌مون با هم دعوا نداشته باشند، ثانیاً تعداد تمساح‌های مجلس بیشینه باشه».‎

‎آیدین گفت ‎«دست گلتون درد نکنه!». رستم گفت ‎«حالا اینش رو یه جوری حل کردیم. نکته مهم اینه که می‌خوایم بدونیم ما به چند روش می‌تونیم زیرمجموعه‌ی بشینه‌ی مجلسی از اینا رو انتخاب کنیم؟ قضیه هم اینه که می‌خوایم هر ماه مجلس رو عوض کنیم و می‌خوایم ببینیم تا چند ماه می‌تونیم نوآوری و خلاقیت داشته باشیم و ترکیب غیرتکراری بدیم؟‎»

به ‎آیدین کمک کنید تا این بار هم به رستم کمک کند. اگر ‎$M$‎ تعداد زیرمجموعه‌های تمساح‌ها باشد که دو شرط مجلسی (دعوا نداشتن هیچ دوتایی‌شون و بیشینه بودن) را ارضا می‌کند، باقی‌مانده‌ی تقسیم ‎$M$‎ بر ‎$\Delta$‎ چند است؟


ابزار صفحه