No.1219 Mancala Combo
タグ : / 解いたユーザー数 248
作問者 :
anagohirame
/ テスター :
Kiri8128
Problem Statement
We play a game using cells and stones.
There are $N+1$ cells arranged in a row, numbered from $0$ to $N$.
Cell $i\,\,(1\le i\le N)$ contains $A_i$ stones. Cell $0$ contains no stones.
In this game, you may repeatedly perform the following operation. When no operation can be performed, the game ends.
- Choose one integer $i\,\,(1\le i\le N)$ such that cell $i$ contains exactly $i$ stones. Remove all stones from cell $i$, and add one stone to each of cells $0$ through $i-1$ ($i$ cells in total).
Input
$N$ $A_1\ A_2\ \cdots \ A_N$
- All input values are integers.
- $1\le N\le 2\times 10^5$
- $0\le A_i\le i\ \ (1\le i\le N)$
- At least one of the $A_i$ is positive.
Output
Print Yes on one line if it is possible to move all the stones to cell $0$ by performing the operations appropriately, and No otherwise.
Sample
Sample 1
Input
3 0 1 3
Output
Yes
For example, all the stones can be moved to cell $0$ by operating as follows.
- Choose cell 3. The numbers of stones on cells 0, 1, 2, 3 become $(1, 1, 2, 0)$, in this order.
- Choose cell 1. The numbers of stones on cells 0, 1, 2, 3 become $(2, 0, 2, 0)$, in this order.
- Choose cell 2. The numbers of stones on cells 0, 1, 2, 3 become $(3, 1, 0, 0)$, in this order.
- Choose cell 1. The numbers of stones on cells 0, 1, 2, 3 become $(4, 0, 0, 0)$, in this order.
Sample 2
Input
3 1 2 3
Output
No
Sample 3
Input
6 1 1 3 0 0 0
Output
Yes
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。