問題一覧 > 通常問題

No.1242 Takahashi and Sugoroku

レベル : / AI推定難易度 : 1825 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 156
作問者 : 👑 tute7627 / テスター : first_vil
お気に入りにしたユーザー ProblemId : 4583 / 自分の提出
問題文最終更新日: 2020-10-03 00:26:46
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 268 (順位表) の他の問題:

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$.
    If the move would go past square $N$, he stops on square $N$ instead.
Now, $K$ of the squares on this board are game-over squares.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。