No.2658 L-R Nim
タグ : / 解いたユーザー数 19
作問者 :
hamamu
/ テスター :
👑 
Nachia
てんぷら
問題文
石の山が $N$ 個あり、 $i$ 番目の山には石が $A_i$ 個あります。
これらの山を使ってAliceとBobがゲームをします。
まずBobが2つの整数 $L,R$ $(1 \le L \le R \le N)$ を選び、
$L$ 番目から $R$ 番目までの $R-L+1$ 個の山を残してそれ以外の山を取り除きます。
その後、残った $R-L+1$ 個の山を使い、Aliceを先手としてNimで勝敗を決めます。
Nimのルールは以下のとおりです：
-
先手から順に交互に以下の操作を行う
- 操作：石の山を $1$ つ選び、そこから $1$ 個以上の石を取り除く
- 操作を行えなくなった方が負け、負けなかった方が勝ち
Aliceはこのゲームに勝ちたいので、Bobがどのような $L,R$ を選んでも勝てるように 以下の細工を一度だけすることにしました。
- 整数 $i (1 \le i \le N)$ を $1$ つ選び、$i$ 番目の山に以下の二つの操作のいずれかを行う
- 石を $x$ 個加える $(0 \le x \le K)$
- 石を $x$ 個取り除く $(0 \le x \le \min(K,A_i-1))$
Aliceが必ず勝てる細工の仕方が存在するか判定してください。
制約
- 入力はすべて整数
- $1 \le N \le 50000$
- $1 \le K \le 100$
- $1 \le A_i \le 10^6$
入力
以下の形式で標準入力から与えられます。$N\ K$ $A_1\ A_2 \cdots A_N$
出力
存在する場合はYesを、
そうでない場合はNoを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
2 1 1 1
出力
Yes
Aliceが $1$ 番目の山に石を $1$ 個追加すると $A_1=2,A_2=1$ になります。 Bobが選択する $L,R$ と、そのときにゲームで使う山の石の個数は以下のとおりです。
- $L=1,R=1$ のとき・・・山の石の個数 $(2)$
- $L=1,R=2$ のとき・・・山の石の個数 $(2,1)$
- $L=2,R=2$ のとき・・・山の石の個数 $(1)$
Yesです。
サンプル2
入力
7 100 10 10 10 10 10 10 10
出力
No
Aliceがどの山に細工しても、
Bobは石の個数 $10$ の二つの山が残るよう $L,R$ を選択することができます。
以降Bobは常に二つの山の石の個数が同じになるよう操作することができ、
勝つことができます。よって答はNoです。
サンプル3
入力
5 3 3 1 2 3 6
出力
No
サンプル4
入力
5 6 1 5 4 2 2
出力
No
サンプル5
入力
1 2 3
出力
Yes
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。