問題一覧 > 通常問題

No.1242 高橋君とすごろく

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 124
作問者 : tute7627tute7627 / テスター : ir_1st_vilir_1st_vil
17 ProblemId : 4583 / 出題時の順位表
問題文最終更新日: 2020-10-03 00:26:46

問題文

高橋君はサイコロを使ってすごろくをすることにしました。
このサイコロには $1,2,3,4,5,6$ の目があり、それぞれ等確率で出ます。
このすごろくには直線状に並んだ $N$ 個のマス目が存在し、左から順に $1$ から $N$ の番号がついています。
高橋君は最初はマス $1$ におり、以下の行動を繰り返してゴールであるマス $N$ を目指します。

  • サイコロを振り、出た目の数を $x$ として以下のいずれかを選択する。
    • マス $N$ の方向へ $x$ マス進む。
    • 高橋君の超能力によりサイコロをひっくり返し、マス $N$ の方向へ $7-x$ マス進む。
    なお、マス $N$ を超えるような場合は代わりにマス $N$ に止まります。
ところで、このすごろくのマスの内 $K$ 個のマスはゲームオーバーマスとなっています。
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。