No.2518 Adjacent Larger
タグ : / 解いたユーザー数 111
作問者 :
MasKoaTS
fky_
Problem Statement
You are given a positive integer $N$ and a sequence of non-negative integers $A = (A_1, \dots, A_N)$ of length $N$.
Determine whether there exists a permutation $P$ of length $N$, obtained by rearranging $(1, \dots, N)$, that satisfies the following condition.
- For every integer $i$ satisfying $1 \leq i \leq N$, the following holds.
- The number of elements among $P_{i - 1}, P_{i + 1}$ that are greater than $P_i$ is $A_i$.
Here, $P_0$ refers to $P_N$, and $P_{N + 1}$ refers to $P_1$.
You are given $T$ test cases; solve each of them.
Constraints
Input
The input is given from standard input. The first line contains the number of test cases $T$.
$T$
Then, each test case is given in the following format.
$N$ $A_1$ $\dots$ $A_N$
Output
For each test case, print Yes if a permutation $P$ satisfying the condition exists, and No otherwise.
Sample
Sample 1
Input
3 4 2 0 1 1 4 2 2 0 0 7 1 1 1 1 1 1 1
Output
Yes No No
There are 3 test cases.
For the first test case, for example, $P = (1, 4, 3, 2)$ satisfies the condition in the problem statement. This can be verified as follows:
- Among $P_0 = 2, P_2 = 4$, the number of elements greater than $P_1 = 1$ is $2$.
- Among $P_1 = 1, P_3 = 3$, the number of elements greater than $P_2 = 4$ is $0$.
- Among $P_2 = 4, P_4 = 2$, the number of elements greater than $P_3 = 3$ is $1$.
- Among $P_3 = 3, P_5 = 1$, the number of elements greater than $P_4 = 2$ is $1$.
Since a $P$ satisfying the condition exists, the answer is Yes.
For the second and third test cases, no $P$ satisfying the condition exists. Therefore, the answer is No.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。