No.2666 Decreasing Modulo Nim
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 69
作問者 :
suisen
/ テスター :
cureskol
ygussany
kaichou243
タグ : / 解いたユーザー数 69
作問者 :
suisen
/ テスター :
cureskol
ygussany
kaichou243
問題文最終更新日: 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)$ を表します。
以下にゲームの進行例を示します。なお、この例は両プレイヤーの最適な行動を表しているとは限りません。
- $A=(1,2,3),\ x=m-1=1$ に対して Alice が $(i,k)=(3,1)$ を選択して $A=(1,2,2),\ x=(1 \bmod 2)=1$ と更新する
- $A=(1,2,2),\ x=1$ に対して Bob が $(i,k)=(1,1)$ を選択して $A=(0,2,2),\ x=(1 \bmod 2)=1$ と更新する
- $A=(0,2,2),\ x=1$ に対して Alice が $(i,k)=(3,2)$ を選択して $A=(0,2,0),\ x=(2 \bmod 2)=0$ と更新する
- $A=(0,2,0),\ x=0$ に対して Bob が $(i,k)=(2,2)$ を選択して $A=(0,0,0),\ x=(2 \bmod 2)=0$ と更新する
- $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もしくは右上の雲マークをクリックしてアカウントを作成してください。