Problem H
Chair Game
Consider a game with $n$ players and $n$ chairs. The chairs will be arranged in a circle, and each player will sit on a chair. There is also a bell which will ring some number of times during the game. Each chair has an integer between $1$ and $n$: the number of steps the player who sits on that chair must move clockwise when the bell rings. A chair arrangement is valid if each chair will have exactly one player after the bell rings. Your task is to find a valid chair arrangement or state that there is no such arrangement.
Input
The first line has an integer $t$: the number of tests. There are at most $1\, 000$ tests. After this, each test consists of two lines. The first line has an integer $n$, the number of chairs. There are at most $100$ chairs. The second line has integers $s_1,s_2,\dots ,s_ n$: the numbers on the chairs. For all $i$ we have $1 \leq s_ i \leq n$.
Output
For each test, first print YES if there is a valid chair arrangement and NO otherwise. If the answer is YES, also print a possible arrangement clockwise. If there are several valid arrangements, you can print any of them.
Scoring
Group |
Points |
Constraints |
1 |
8 |
$1 \leq n \leq 8$. |
2 |
5 |
$s_ i \neq s_ j$ ef $i \neq j$, that is to say all the $s_ i$ are different within each case. |
3 |
4 |
$1 \leq s_ i \leq 2$. |
4 |
7 |
$1 \leq s_ i \leq 3$. |
5 |
12 |
$1 \leq s_ i \leq 4$. |
6 |
15 |
$1 \leq s_ i \leq 5$. |
7 |
20 |
$1 \leq n \leq 16$. |
8 |
29 |
No further constraints. |
Sample Input 1 | Sample Output 1 |
---|---|
3 4 1 1 1 1 4 1 1 1 2 5 4 1 2 1 2 |
YES 1 1 1 1 NO YES 2 4 1 1 2 |