No.1242 高橋君とすごろく
タグ : / 解いたユーザー数 152
作問者 : 👑
first_vil
問題文
高橋君はサイコロを使ってすごろくをすることにしました。
このサイコロには $1,2,3,4,5,6$ の目があり、それぞれ等確率で出ます。
このすごろくには直線状に並んだ $N$ 個のマス目が存在し、左から順に $1$ から $N$ の番号がついています。
高橋君は最初はマス $1$ におり、以下の行動を繰り返してゴールであるマス $N$ を目指します。
- サイコロを振り、出た目の数を $x$ として以下のいずれかを選択する。
- マス $N$ の方向へ $x$ マス進む。
- 高橋君の超能力によりサイコロをひっくり返し、マス $N$ の方向へ $7-x$ マス進む。
$i$ 個目のゲームオーバーマスは マス $A_i$ であることがわかっています。
また、移動後に丁度ゲームオーバーマスに止まるとゲームオーバーしてしまいます。
高橋君が最適な戦略をとったとき、サイコロの出目に関わらず確実にゲームオーバーにならずにマス $N$ へたどり着けるかを判定してください。
$i$ 回目の行動における選択は $i+1$ 回目以降の行動におけるサイコロの出目がわからない状態で行う必要があることに注意してください。
入力
$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)$
出力
サイコロの出目に関わらず確実にゲームオーバーにならずにマス $N$ へたどり着ける場合はYesを、そうでない場合はNoを出力してください
最後に改行してください。
サンプル
サンプル1
入力
3 1 2
出力
Yes
最初に $1$ 以外の目が出た場合はゴールできます。 $1$ が出た場合は超能力により出目を $6$ にすればゴールできます。
サンプル2
入力
7 5 2 3 4 5 6
出力
No
最初に $6$ の目が出た場合はゴールできます。 最初に $1$ の目が出た場合も超能力を使えばゴールできます。 しかし、その他の目が出た場合、超能力を使ってもゲームオーバーしてしまいます。
サンプル3
入力
11 2 8 9
出力
Yes
サンプル4
入力
11 2 9 10
出力
No
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。