/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
N 頂点の完全グラフ G の辺に正整数の番号を付ける方法のうち、以下の条件を満たすものを「良い完全グラフ」と言うことにします。
- N 個の頂点を全てちょうど 1 回ずつ通るパスのうち、通った辺の番号を通った順に並べた数列が広義単調増加になるものが存在しない。
「良い完全グラフ」が存在するか判定し、存在する場合は「辺に付ける正整数の番号の最大値」が最小になるものを 1 個構築してください。
制約
- 2 \le N \le 20
入力
入力は以下の形式で標準入力から与えられる。
N
出力
「良い完全グラフ」が存在しない場合、No と出力せよ。
「良い完全グラフ」が存在する場合、以下のように出力せよ。ここで、a_{i,j} は頂点 i と頂点 j を結ぶ無向辺に付けられる番号とする。
Yes
a_{1,2} a_{1,3} a_{1,4} \dots a_{1,N}
a_{2,3} a_{2,4} \dots a_{2,N}
\vdots
a_{N-1,N}
条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。
入力例 1
5
出力例 1
Yes 2 1 4 4 4 3 1 1 3 2
例えば頂点 2,5,1,4,3 の順に通るパスの場合、通った辺の番号を通った順に並べた数列は (1,4,4,1) となるため、広義単調増加ではありません。
他にも通った辺の番号を通った順に並べた数列が広義単調増加となるパスが存在しないため、このグラフは条件を満たします。
また、N=5 の場合「辺に付ける正整数の番号の最大値」を 3 以下にすることはできないため、この出力は正当です。
入力例 2
2
出力例 2
No
Score : 800 points
Problem Statement
Among the ways to label the edges of a complete graph G with N vertices with positive integers, a graph satisfying the following condition is called a "good complete graph".
- There exists no path that visits all N vertices exactly once and whose sequence of edge labels, in the order the edges are traversed, is non-decreasing.
Determine whether a good complete graph exists. If it exists, construct one that minimizes the maximum label assigned to an edge.
Constraints
- 2 \leq N \leq 20
Input
The input is given from Standard Input in the following format:
N
Output
If a good complete graph does not exist, print No.
If it exists, print one as follows. Let a_{i,j} be the label assigned to the undirected edge connecting vertices i and j.
Yes
a_{1,2} a_{1,3} a_{1,4} \dots a_{1,N}
a_{2,3} a_{2,4} \dots a_{2,N}
\vdots
a_{N-1,N}
If multiple solutions exist, you may print any of them.
Sample Input 1
5
Sample Output 1
Yes 2 1 4 4 4 3 1 1 3 2
For example, consider the path that visits vertices in the order 2, 5, 1, 4, 3. The sequence of edge labels traversed is (1, 4, 4, 1), which is not non-decreasing.
Moreover, there is no path whose sequence of edge labels is non-decreasing, so this graph satisfies the condition.
Also, when N=5, it is impossible to assign labels so that the maximum label assigned to an edge is 3 or less, so this output is valid.
Sample Input 2
2
Sample Output 2
No