No.1242 Takahashi and Sugoroku
Problem Statement
Takahashi has decided to play sugoroku using a die.
This die has faces $1,2,3,4,5,6$, each of which comes up with equal probability.
This sugoroku board has $N$ squares arranged in a line, numbered from $1$ to $N$ from left to right.
Takahashi starts on square $1$ and repeats the following action, aiming for the goal, square $N$.
- He rolls the die. Letting $x$ be the number rolled, he chooses one of the following.
- Advance $x$ squares in the direction of square $N$.
- Flip the die over using his psychic powers and advance $7-x$ squares in the direction of square $N$.
It is known that the $i$-th game-over square is square $A_i$.
If he stops exactly on a game-over square after a move, the game is over.
Determine whether, when Takahashi follows an optimal strategy, he can reach square $N$ with certainty without the game being over, regardless of the die rolls.
Note that the choice in the $i$-th action must be made without knowing the die rolls in the $i+1$-th and later actions.
Input
$N \ K$ $A_1 \ A_2 \dots A_K $
- $3 \le N \le 10^{18}$
- $1 \le K \le 100$
- $2 \le A_i \le N-1$
- $A_i < A_{i+1} \ (1 \le i \le K-1)$
Output
Print Yes if he can reach square $N$ with certainty without the game being over, regardless of the die rolls, and No otherwise.
Print a newline at the end.
Sample
Sample 1
Input
3 1 2
Output
Yes
If the first roll is anything other than $1$, he can reach the goal. If $1$ is rolled, he can reach the goal by turning the roll into $6$ with his psychic powers.
Sample 2
Input
7 5 2 3 4 5 6
Output
No
If the first roll is $6$, he can reach the goal. If the first roll is $1$, he can also reach the goal by using his psychic powers. However, for any other roll, the game is over even if he uses his psychic powers.
Sample 3
Input
11 2 8 9
Output
Yes
Sample 4
Input
11 2 9 10
Output
No
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
tute7627