المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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

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

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

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

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

می‌دانیم تمساح‌ها این بازی را برای ‎$\Delta$‎ لحظه انجام می‌دهند. در پایان بازی میزان شادی هر تمساح شماره‎$i$ (یعنی ‎$H_i$‎) برابر با تعداد دفعاتی هست که ‎آیدین را شوت زده «از این رو مجموع میزان شادی همه برابر با ‎$\Delta-1$‎ است. چرا که نفر آخری که ‎آیدین‎ بهش می‌رسد، او رانمی‌شوتد و لذتی نمی‌برد!». آیدین می‌داند که تمساح‌ها خلق و خوی بسیار اجتماعی‌ای دارند، و از این رو شادی‌هایشان را در هم ضرب می‌کنند‎!‎ برای همین او دوست دارد بداندحاصل‌ضرب میزان شادی این ‎۸۱‎ تمساح پس از ‎$\Delta$‎ گام (که آن را ‎$M=\Pi_{i=1}^{81} H_i$‎‎ می‌نامیم) چند است؟ شما باقی‌مانده‌ی تقسیم ‎$M$‎ بر ‎$\Delta$‎ را حساب کرده و بنویسید.


ابزار صفحه