問題一覧 > 通常問題

No.1219 Mancala Combo

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 240
作問者 : anagohirameanagohirame / テスター : Kiri8128Kiri8128
36 ProblemId : 4513 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-29 14:20:44

問題文

マスと石を使ったゲームをします。
一列に並んだ $N+1$ 個のマスがあり，$0$ から $N$ までの番号が付けられています。 マス $i\,\,(1\le i\le N)$ には $A_i$ 個の石が置かれています。マス $0$ には石が置かれていません。
このゲームでは，以下の操作を繰り返し行うことが出来ます。操作が行えなくなった場合，そこでゲームは終了です。

  • 整数 $i\,\,(1\le i\le N)$ のうち，マス $i$ に石がちょうど $i$ 個あるものを1つ選ぶ。 マス $i$ から石をすべて取り除き，マス $0$ からマス $i-1$ （計 $i$ マス）に石を1つずつ追加する。
適切に操作を行うことによって，全ての石をマス $0$ へと移すことができるでしょうか？

入力

$N$
$A_1\ A_2\ \cdots \ A_N$

  • 入力はすべて整数
  • $1\le N\le 2\times 10^5$
  • $0\le A_i\le i\ \ (1\le i\le N)$
  • $A_i$ のうちいずれかは正である

出力

適切に操作を行うことによって全ての石をマス $0$ へと移すことができるならばYes，できないならばNoと1行に出力してください。

サンプル

サンプル1
入力
3
0 1 3
出力
Yes

たとえば以下のように操作することで，石をすべてマス $0$ に移動することができます。

  • マス3を選ぶ。マス0, 1, 2, 3上にある石の数は順に $(1, 1, 2, 0)$ になる。
  • マス1を選ぶ。マス0, 1, 2, 3上にある石の数は順に $(2, 0, 2, 0)$ になる。
  • マス2を選ぶ。マス0, 1, 2, 3上にある石の数は順に $(3, 1, 0, 0)$ になる。
  • マス1を選ぶ。マス0, 1, 2, 3上にある石の数は順に $(4, 0, 0, 0)$ になる。

サンプル2
入力
3
1 2 3
出力
No

サンプル3
入力
6
1 1 3 0 0 0
出力
Yes

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。