م.م.م

۶۰ گانگستر دور یک میز دایره‌ای نشسته‌اند و بازی متل متل موتوله را نجام می‌دهند. بازی «متل متل موتوله (یا مختصرا م.م.م) با شروع از $x$» به این صورت است که:

ابتدا گانگستر $x$ام، سرش را روی میز می‌گذارد و می‌خوابد. سپس، $x$امین گانگستر بیدار بعد از $x$، می‌خوابد (او را $x_2$ می‌نامیم). سپس $x_2$ امین گانگستر بیدار بعد از $x_2$ می‌خوابد و … . یعنی در مرحله‌ی $i$ اگر گانگستر با شماره $p_i$ بخوابد، در مرحله بعد با شروع از اولین گانگستر بیدار بعد از $p_i$، به اندازه‌ی $p_i$ نفر بیدار می‌شماریم و جلو می‌رویم. برنده‌ی این بازی، اگر اولین خوابنده $k_1$ باشد، $w_{k_1}$‌ است.

برای مثال اگر $x=1$ باشد، ابتدا گانگستر شماره‌ ۱، بعد ۲، بعد ۴، بعد ۸ و … می‌خوابند.

مقدار $T=w_1\times w_2 \times w_3 \times … \times w_{59} \times w_{60}$ را در نظر بگیرید. باقی‌مانده تقسیم $T$ بر $\Delta$ چند است؟

‎
 
#include <iostream>
using namespace std;
 
const int n = 60;
const int delta = 90907;
 
int findWinner(int start) {
  bool a[n+1];
  for (int i=1; i<=n; i++) a[i] = true;
 
  int x = start; a[x] = false;
  int alive = n-1;
  for (; alive != 1; ) {
    int jump = x;
    for (int i=1; i<=jump; i++)
      do {
        x++; if (x == n+1) x = 1;
      } while (!a[x]);
    a[x] = false; alive--;
  }
 
  for (int i=1; i<=n; i++)
    if (a[i])
      return i;
  return -1;
}
 
int main() {
  int t = 1;
  for (int start=1; start<=n; start++)
    t = (t*findWinner(start)) % delta;
  cout << (t) << endl;
 
  return 0;
}

• سوال بعد
• سوال قبل