Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
以下の条件を全て満たす長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が存在するか判定し、存在するならば一つ構築してください。
- \sum_{i=1}^{N} \frac{1}{A_i} = 1
- A の要素は全て相異なる。
- 1 \le A_i \le 10^9(1 \le i \le N)
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \le T \le 500
- 1 \le N \le 500
入力
入力は以下の形式で標準入力から与えられる。
T \mathrm{case}_1 \mathrm{case}_2 \vdots \mathrm{case}_T
ここで、\mathrm{case}_i とは i 個目のテストケースである。各テストケースは以下の形式で与えられる。
N
出力
それぞれのケースについて、条件を満たす正整数列 A=(A_1,A_2,\dots,A_N) が存在しないならば No
を出力せよ。存在するならば、以下の形式で出力せよ。
Yes A_1 A_2 \dots A_N
条件を満たす解が複数存在する場合、どれを出力しても正解とみなされる。
入力例 1
2 3 5
出力例 1
Yes 2 3 6 Yes 3 4 5 6 20
1 個目のテストケースでは、N=3 です。
A=(2,3,6) は、\frac{1}{2} + \frac{1}{3} + \frac{1}{6} = 1 かつ他の条件も全て満たすため正当です。
2 個目のテストケースでは、N=5 です。
A=(3,4,5,6,20) は、\frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{20} = 1 かつ他の条件も全て満たすため正当です。
例えば、A=(5,5,5,5,5) は、1,3 個目の条件を満たしていますが同じ要素が存在するため不適であることに注意してください。
Score : 600 points
Problem Statement
Determine whether there is a length-N sequence of positive integers A=(A_1,A_2,\dots,A_N) that satisfies all of the following conditions, and if it exists, construct one.
- \sum_{i=1}^{N} \frac{1}{A_i} = 1
- All elements of A are distinct.
- 1 \le A_i \le 10^9(1 \le i \le N)
You are given T test cases. Find the answer for each of them.
Constraints
- 1 \le T \le 500
- 1 \le N \le 500
Input
The input is given from Standard Input in the following format:
T \mathrm{case}_1 \mathrm{case}_2 \vdots \mathrm{case}_T
Here, \mathrm{case}_i is the i-th test case. Each test case is given in the following format:
N
Output
For each case, if there is not a sequence of positive integers A=(A_1,A_2,\dots,A_N) that satisfies the conditions, print No
. If there is, print one in the following format:
Yes A_1 A_2 \dots A_N
If there are multiple valid solutions, any of them will be accepted.
Sample Input 1
2 3 5
Sample Output 1
Yes 2 3 6 Yes 3 4 5 6 20
In the first test case, N=3.
A=(2,3,6) is valid because \frac{1}{2} + \frac{1}{3} + \frac{1}{6} = 1 and it satisfies all other conditions.
In the second test case, N=5.
A=(3,4,5,6,20) is valid because \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{20} = 1 and it satisfies all other conditions.
Note that, for example, A=(5,5,5,5,5) satisfies the first and third conditions, but it is invalid because it contains duplicated elements.