問題一覧 > 通常問題

No.2666 Decreasing Modulo Nim

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 69
作問者 : suisen / テスター : cureskol 👑 ygussany kaichou243
17 ProblemId : 10495 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-02-29 19:05:41

問題文

長さ nn の正整数列 A=(A1,A2,…,An)A=(A_1,A_2,\ldots,A_n) と正整数 mm が与えられます。また、非負整数 xx が x=m−1x = m - 1 と初期化されています。

Alice と Bob がこの数列を用いてゲームをします。Alice を先手として、Alice と Bob が交互に次の操作を行います。

  • 1≤k≤Ai1\leq k\leq A_i および (k mod m)≤x(k\bmod m) \leq x を満たす整数組 (i,k)(i,k) を選択して Ai←Ai−k, x←(k mod m)A_i\gets A_i-k,\ x\gets (k\bmod m) と更新する。ここで a mod ba\bmod b は aa を bb で割ったあまりを表す。

操作を行えなくなったプレイヤーを負けとし、負けなかった方のプレイヤーを勝ちとします。

両者が勝ちを目指して最適な行動を取ると仮定した場合、どちらが勝つか判定してください。

入力

入力は以下の形式で標準入力から与えられる。

nn mm
A1A_1 A2A_2 ⋯\cdots AnA_n
  • 入力は全て整数で与えられる
  • 1≤n≤2×1051\leq n\leq 2\times 10 ^ 5
  • 1≤m≤1091\leq m\leq 10 ^ 9
  • 1≤Ai≤1091\leq A_i\leq 10 ^ 9

出力

Alice が勝つ場合は Alice を、Bob が勝つ場合は Bob を 11 行に出力して改行してください。

サンプル

サンプル1
入力
3 2
1 2 3
出力
Bob

この入力は n=3, m=2, A=(1,2,3)n=3,\ m=2,\ A=(1,2,3) を表します。

以下にゲームの進行例を示します。なお、この例は両プレイヤーの最適な行動を表しているとは限りません。

  1. A=(1,2,3), x=m−1=1A=(1,2,3),\ x=m-1=1 に対して Alice が (i,k)=(3,1)(i,k)=(3,1) を選択して A=(1,2,2), x=(1 mod 2)=1A=(1,2,2),\ x=(1 \bmod 2)=1 と更新する
  2. A=(1,2,2), x=1A=(1,2,2),\ x=1 に対して Bob が (i,k)=(1,1)(i,k)=(1,1) を選択して A=(0,2,2), x=(1 mod 2)=1A=(0,2,2),\ x=(1 \bmod 2)=1 と更新する
  3. A=(0,2,2), x=1A=(0,2,2),\ x=1 に対して Alice が (i,k)=(3,2)(i,k)=(3,2) を選択して A=(0,2,0), x=(2 mod 2)=0A=(0,2,0),\ x=(2 \bmod 2)=0 と更新する
  4. A=(0,2,0), x=0A=(0,2,0),\ x=0 に対して Bob が (i,k)=(2,2)(i,k)=(2,2) を選択して A=(0,0,0), x=(2 mod 2)=0A=(0,0,0),\ x=(2 \bmod 2)=0 と更新する
  5. A=(0,0,0), x=0A=(0,0,0),\ x=0 に対して Alice は操作を行うことができないので、この場合の勝者は Bob となる

Alice がどのような操作を行っても、Bob は Bob が勝つように操作できることを証明できます。従って、このケースに対して両者が最適に行動した場合に勝つのは Bob です。

サンプル2
入力
4 10
1 2 3 4
出力
Alice
サンプル3
入力
10 5
7 4 10 15 9 4 1 13 5 6
出力
Alice

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。