問題一覧 > 通常問題

No.2658 L-R Nim

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 18
作問者 : 👑 hamamu / テスター : 👑 Nachia てんぷら
お気に入りにしたユーザー ProblemId : 10560 / 自分の提出
問題文最終更新日: 2024-02-29 02:31:23
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 419 (順位表) の他の問題:

Problem Statement

There are $N$ piles of stones, and the $i$-th pile contains $A_i$ stones.
Alice and Bob play a game using these piles.

First, Bob chooses two integers $L,R$ $(1 \le L \le R \le N)$, keeps the $R-L+1$ piles from the $L$-th to the $R$-th, and removes all the other piles.
Then, using the remaining $R-L+1$ piles, they play Nim with Alice moving first to decide the winner.
The rules of Nim are as follows:

  • Starting from the first player, the players alternately perform the following operation
    • Operation: choose $1$ pile of stones and remove $1$ or more stones from it
  • The player who can no longer perform the operation loses, and the player who did not lose wins

Since Alice wants to win this game, she has decided to perform the following trick exactly once so that she can win no matter which $L,R$ Bob chooses.

  • Choose $1$ integer $i (1 \le i \le N)$ and perform one of the following two operations on the $i$-th pile
    • Add $x$ stones $(0 \le x \le K)$
    • Remove $x$ stones $(0 \le x \le \min(K,A_i-1))$

Determine whether there exists a way of performing the trick such that Alice is guaranteed to win.

Constraints

  • All inputs are integers
  • $1 \le N \le 50000$
  • $1 \le K \le 100$
  • $1 \le A_i \le 10^6$

Input

The input is given from standard input in the following format.
$N\ K$
$A_1\ A_2 \cdots A_N$

Output

Print Yes if such a way exists, and No otherwise.
Print a newline at the end.

Sample

Sample 1
Input
2 1
1 1
Output
Yes

If Alice adds $1$ stone to the $1$-st pile, then $A_1=2,A_2=1$. The $L,R$ that Bob can choose, and the numbers of stones in the piles used in the game in each case, are as follows.

  • When $L=1,R=1$: the numbers of stones in the piles are $(2)$
  • When $L=1,R=2$: the numbers of stones in the piles are $(2,1)$
  • When $L=2,R=2$: the numbers of stones in the piles are $(1)$
Alice can win in every case, so the answer is Yes.

Sample 2
Input
7 100
10 10 10 10 10 10 10
Output
No

No matter which pile Alice applies the trick to, Bob can choose $L,R$ so that two piles with $10$ stones each remain. After that, Bob can always make moves so that the two piles have the same number of stones, and he can win. Therefore, the answer is No.

Sample 3
Input
5 3
3 1 2 3 6
Output
No
Sample 4
Input
5 6
1 5 4 2 2
Output
No
Sample 5
Input
1 2
3
Output
Yes

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