No.2658 L-R Nim
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)$
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
hamamu
Nachia
てんぷら