Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

شوت-یه-ضرب تمساحی

به محض این‌که آیدین در رودخانه افتاد، ‎۸۱‎ تمساح سر از آب بیرون آوردند‎!‎ این ‎۸۱‎ تمساح در ‎۹‎ سطر و در هر سطر ‎۹‎ تمساح قرار گرفته بودند یک جدول ‎(9×9)‎. در ابتدای کار تمساحی که در سطر اول و ستون اول قرار گرفته بود با پوزه‌اش ‎آیدین‎ را بالا نگه داشت و همه بقیه خندیدند‎!‎ آن‌ها خوش‌حال بودند که امروز ناهار غذای چرب و چیلی‌ای دارند. در راستای شادی بخشیدن مضاعف به این ضیافت، تمساح‌ها تصمیم گرفتند بازی ‎»‎شوت-یه-ضرب تمساحی‎«‎ را با استفاده از ‎آیدین (به‌جای توپ‎(!‎ بازی کنند.

در این بازی در هر لحظه توپ (در اینجا ‎آیدین)‎ روی پوزه‌ی یکی از تمساح‌ها است و او باید پس از دریافت ‎آیدین‎، بر حسب تعداد دفعاتی که تا پیش از این ‎آیدین‎ را گرفته بود، او را به یکی از ‎۴‎ تمساح مجاورش در جهت‌های اصلی بدهد. فرض می‌کنیم سطر بالای سطر یکم، سطر نهم است. همین طور ستون های ‎۱‎ و ‎۹‎ هم به هم متصلند.

به بیان دقیق‌تر اگر تمساح ‎i‎ تا پیش از لحظه‌ی دریافت ‎آیدین (بدون احتساب همان دفعه) کلاً ‎Hi‎ بار او را گرفته باشد و باقی‌مانده‌ی ‎Hi‎ در تقسیم بر ‎۴‎ برابر با ‎r‎ باشد، در این صورت او باید ‎آیدین را … ‎

  • به تمساح بالایی‌اش بدهد، اگر ‎r‎ برابر با صفر باشد. (اگر در سطر اوّل بود به سطر آخر می‌رود‎.‎)
  • ‎ به تمساح سمت راستی‌اش بدهد، اگر ‎r‎ برابر با یک باشد. (اگر در ستون آخر بود به ستون اوّل می‌رود‎(.‎
  • ‎‎ به تمساح پایینی‌اش بدهد، اگر ‎r‎ برابر با دو باشد. (اگر در سطر آخر بود به سطر اوّل می‌رود‎.‎)
  • ‎ به تمساح سمت چپی‌اش بدهد، اگر ‎r‎ برابر با سه باشد. (اگر در ستون اوّل بود به ستون آخر می‌رود‎(.‎

برای مثال در لحظه شماره ‎۱ آیدین روی تمساح ‎(1,1)‎ است. سپس به‌خانه‌ی ‎(9,1) (سطر ‎۹‎، ستون ‎۱) می رود. سپس در لحظه سوم به خانه‌ی ‎(8,1)‎ رفته و …

می‌دانیم تمساح‌ها این بازی را برای ‎Δ‎ لحظه انجام می‌دهند. در پایان بازی میزان شادی هر تمساح شماره‎i (یعنی ‎Hi‎) برابر با تعداد دفعاتی هست که ‎آیدین را شوت زده «از این رو مجموع میزان شادی همه برابر با ‎Δ1‎ است. چرا که نفر آخری که ‎آیدین‎ بهش می‌رسد، او رانمی‌شوتد و لذتی نمی‌برد!». آیدین می‌داند که تمساح‌ها خلق و خوی بسیار اجتماعی‌ای دارند، و از این رو شادی‌هایشان را در هم ضرب می‌کنند‎!‎ برای همین او دوست دارد بداندحاصل‌ضرب میزان شادی این ‎۸۱‎ تمساح پس از ‎Δ‎ گام (که آن را ‎M=Π81i=1Hi‎‎ می‌نامیم) چند است؟ شما باقی‌مانده‌ی تقسیم ‎M‎ بر ‎Δ‎ را حساب کرده و بنویسید.

پاسخ‌ ارائه شده در این سوال با فرض Δ=28813 محاسبه شده است.

پاسخ

6907


ابزار صفحه