No.3489 Making an Amidakuji
タグ : / 解いたユーザー数 42
作問者 : 👑
Problem Statement
You are given as input an integer $N$ greater than or equal to $2$ and a permutation $P$ of length $N$ consisting of positive integers less than or equal to $N$.
Determine whether there exists a vertically descending Amidakuji (ladder lottery) $A$ that satisfies all of the following conditions:
- $A$ has exactly $N$ vertical lines. (They are parallel to each other.)
- $A$ has at most $N^2$ horizontal lines. (They are perpendicular to the vertical lines, parallel to each other, and at pairwise distinct heights.)
- For every positive integer $i$ less than or equal to $N$, starting from the top of the $i$-th vertical line from the left of $A$ and following the lines downward according to the rules of Amidakuji, one reaches the bottom of the $P_i$-th vertical line from the left of $A$.
Here, $P_i$ denotes the $i$-th element of $P$.
Input
The input is given from Standard Input in $2$ lines in the following format:
- Line $1$ contains $N$.
- Line $2$ contains $P_i$ for each positive integer $i$ less than or equal to $N$, in increasing order of $i$, separated by single-byte spaces.
$N$ $P_1$ $\cdots$ $P_N$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $2 \leq N \leq 100$.
- $P$ is a permutation of length $N$ consisting of positive integers less than or equal to $N$.
Output
If no Amidakuji $A$ satisfying the conditions exists, print No.
If one exists, choose $1$ such $A$. Let $M$ be the number of horizontal lines of $A$, and for each positive integer $j$ less than or equal to $M$, define the positive integer $i_j$ less than $N$ so that the $j$-th horizontal line from the top of $A$ connects the $i_j$-th vertical line from the left and the $i_j + 1$-th vertical line from the left of $A$. Print in the following format:
- On line $1$, print
Yes. - On line $2$, print $M$.
- For each positive integer $j$ less than or equal to $M$, print $i_j$ on line $2 + j$.
Print a newline at the end.
Note that this is a special judge problem. There may be more than $1$ correct answer, but print only $1$ of them.
However, strictly follow the format described above. For example, the behavior of the judge is not guaranteed if there is extra whitespace.
Sample
Sample 1
Input
2 1 2
Output
Yes 0
An Amidakuji with $2$ vertical lines and $0$ horizontal lines satisfies the conditions. Other correct answers include
Yes 2 1 1
and so on. On the other hand, note that
Yes 6 1 1 1 1 1 1
is not correct. This example does not satisfy the condition that there are at most $N^2 = 4$ horizontal lines.
Sample 2
Input
2 2 1
Output
Yes 1 1
An Amidakuji with $2$ vertical lines and $1$ horizontal line, in which horizontal line number $1$ from the top connects vertical line number $1$ from the left and vertical line number $2$ from the left, satisfies the conditions.
Sample 3
Input
3 3 1 2
Output
Yes 2 1 2
The Amidakuji with $3$ vertical lines and $2$ horizontal lines obtained by setting
- Horizontal line number $1$ from the top connects vertical line number $1$ from the left and vertical line number $2$ from the left.
- Horizontal line number $2$ from the top connects vertical line number $2$ from the left and vertical line number $3$ from the left.
satisfies the conditions.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。