問題一覧 > 通常問題

No.2666 Decreasing Modulo Nim

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

問題文

長さ $n$ の正整数列 $A=(A_1,A_2,\ldots,A_n)$ と正整数 $m$ が与えられます。また、非負整数 $x$ が $x = m - 1$ と初期化されています。

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

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

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

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

入力

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

$n$ $m$
$A_1$ $A_2$ $\cdots$ $A_n$
  • 入力は全て整数で与えられる
  • $1\leq n\leq 2\times 10 ^ 5$
  • $1\leq m\leq 10 ^ 9$
  • $1\leq A_i\leq 10 ^ 9$

出力

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

サンプル

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

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

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

  1. $A=(1,2,3),\ x=m-1=1$ に対して Alice が $(i,k)=(3,1)$ を選択して $A=(1,2,2),\ x=(1 \bmod 2)=1$ と更新する
  2. $A=(1,2,2),\ x=1$ に対して Bob が $(i,k)=(1,1)$ を選択して $A=(0,2,2),\ x=(1 \bmod 2)=1$ と更新する
  3. $A=(0,2,2),\ x=1$ に対して Alice が $(i,k)=(3,2)$ を選択して $A=(0,2,0),\ x=(2 \bmod 2)=0$ と更新する
  4. $A=(0,2,0),\ x=0$ に対して Bob が $(i,k)=(2,2)$ を選択して $A=(0,0,0),\ x=(2 \bmod 2)=0$ と更新する
  5. $A=(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もしくは右上の雲マークをクリックしてアカウントを作成してください。