المپدیا

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

ابزار کاربر

ابزار سایت


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

پلی بامبوئی بر روی رودخانه

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

با کمی جستجو ‎آیدین تعدادی چوب بامبوی استوانه‌ای شکل کنار رودخانه یافته‌است که می‌تواند با متصل کردن آن‌ها در امتداد یکدیگر یک میله‌ی چوب بلند ساخته و با قرار دادن چوب در وسط رودخانه و یک جهش بلند، از روی آن بپّرد‎!‎ نکته‌ی جالب در مورد چوب‌های بامبوی یافته شده این است که روی هر کدام از این چوب‌ها یکی از اعداد اوّل بزرگتر از ‎۷‎ و کوچکتر از ‎$\Delta$‎ نوشته شده و طول چوب ‎$x$ (چوبی که روی آن ‎$x$‎ نوشته شده) برابر با تعداد ارقام عدد ‎$x$‎ در مبنای ‎۱۰‎ است. دقت کنید که به ازای هر کدام از اعداد اوّل بزرگتر از ‎$7$‎ و کوچکتر از ‎$\Delta$‎ دقیقاً یک چوب از آن عدد وجود دارد.

برای این‌که شانس پریدن آیدین‎ از رودخانه بیشتر شود، او دوست دارد میله‌ی چوبی نهایی‌ش تا حد امکان درازتر باشد. اما مسئله این‌جاست که برای اتصال چوب‌های بامبو به یکدیگر باید قوانین زیر رعایت شوند:

  1. ‎‎ از آن‌جا که هیچ وسیله‌ی چسباندنی در دسترس نیست، ‎آیدین باید چوب‌ها(ی استوانه‌ای) را در هم فرو بکند.
  2. ‎ می‌دانیم چوب ‎$a$‎ در چوب ‎$b$‎ فرو می‌رود اگر مقدار عددی ‎$b$‎ بزرگ‌تر از مقدار ‎$a$‎ باشد.
  3. ‎ می‌دانیم چوب ‎$a$‎ در چوب ‎$b$‎ فرو می‌رود اگر رقم یکان ‎$b$‎ برابر با رقم سمت چپ ‎$a$‎ باشد.
  4. ‎ در صورتی که چوب ‎$a$‎ با دارا بودن شرایط فوق در چوب ‎$b$‎ فرو برود، رقم سمت راست ‎(یکان) $b$‎ که تکراری است دیگر در طول محاسبه نمی‌شود. به عبارت دیگر افزودن یک چوب با ‎$k$‎ رقم در انتهای یک رشته چوب (در صورت رعایت شروط فوق) تنها باعث می‌شود که طول نهایی ‎$k-1$‎ رقم ارزش یابد.

برای مثال با استفاده از چوب‌های ‎۱۳‎، ‎۳۱‎ و ‎۱۰۱‎ می‌توان رشته‌ی ‎$1~0~\underline{1}~\underline{3}~1$‎ به طول ‎۵‎ را ساخت.

اگر ‎$M$‎ برابر با طول طولانی‌ترین میله‌ی ساخته شده با استفاده از بهترین زیرمجموعه از چوب‌های داده شده باشد،باقی‌مانده‌ی تقسیم عدد ‎$M^3$‎ بر ‎$\Delta$‎ چند است؟


ابزار صفحه