/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
X\leq Y\leq Z なる正整数の組 (X,Y,Z) が与えられます。
非負整数列の組 (S_1,S_2,S_3) であって、以下の条件をすべて満たすものを 1 つ出力してください。
- S_1,S_2,S_3 の長さはそれぞれ 1 以上 1000 以下
- S_1 の連続部分列であり、かつ S_2 の連続部分列であるもののうち、最長のものの長さが X
- S_1 の連続部分列であり、かつ S_3 の連続部分列であるもののうち、最長のものの長さが Y
- S_2 の連続部分列であり、かつ S_3 の連続部分列であるもののうち、最長のものの長さが Z
- 上 4 つの条件をすべて満たすもののうち、\max(\max(S_1),\max(S_2),\max(S_3)) が最小
本問題の制約下で、条件を満たす (S_1,S_2,S_3) は必ず存在することが証明できます。そのようなものが複数ある場合、どれを出力してもかまいません。
制約
- 1\leq X\leq Y\leq Z\leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
X Y Z
出力
3 行出力せよ。
1 行目には、S_1 を以下の形式で出力せよ。ただし、|S_1| で S_1 の長さを、S_{1,i} で S_1 の i 番目の要素を表す。
|S_1| S_{1,1} S_{1,2} \dots S_{1,|S_1|}
2 行目には S_2 を、3 行目には S_3 を S_1 と同様の形式で出力せよ。
解が複数ある場合、どれを出力してもかまわない。
入力例 1
4 5 5
出力例 1
10 1 1 0 0 1 0 1 0 1 1 8 1 1 0 1 0 0 1 1 11 1 0 0 0 1 1 0 1 0 1 0
S_1=(1,1,0,0,1,0,1,0,1,1),S_2=(1,1,0,1,0,0,1,1),S_3=(1,0,0,0,1,1,0,1,0,1,0) が条件を満たすことは以下のように確認できます。
- S_1,S_2,S_3 の長さはそれぞれ 10,8,11 であり、すべて 1 以上 1000 以下である。
- S_1 の連続部分列であり、かつ S_2 の連続部分列であるもののうち、最長のものは (1,0,0,1) または (1,0,1,0) であり、その長さは X=4 である。
- S_1 の連続部分列であり、かつ S_3 の連続部分列であるもののうち、最長のものは (1,0,1,0,1) または (0,1,0,1,0) であり、その長さは Y=5 である。
- S_2 の連続部分列であり、かつ S_3 の連続部分列であるもののうち、最長のものは (1,1,0,1,0) であり、その長さは Z=5 である。
- \max(\max(S_1),\max(S_2),\max(S_3))=1 であり、\max(\max(S_1),\max(S_2),\max(S_3))=0 として上 4 つの条件を満たすことはできないことが示せるため、これが最小である。
Score : 500 points
Problem Statement
You are given a triple of positive integers (X,Y,Z) such that X\leq Y\leq Z.
Output one triple of sequences of non-negative integers (S_1,S_2,S_3) that satisfies all of the following conditions:
- The lengths of S_1,S_2,S_3 are each between 1 and 1000, inclusive.
- The length of a longest sequence that is both a contiguous subsequence of S_1 and a contiguous subsequence of S_2 is X.
- The length of a longest sequence that is both a contiguous subsequence of S_1 and a contiguous subsequence of S_3 is Y.
- The length of a longest sequence that is both a contiguous subsequence of S_2 and a contiguous subsequence of S_3 is Z.
- \max(\max(S_1),\max(S_2),\max(S_3)) is minimized among all triples satisfying the above four conditions.
It can be proved that under the constraints of this problem, a triple (S_1,S_2,S_3) satisfying the conditions always exists. If there are multiple such triples, you may output any of them.
Constraints
- 1\leq X\leq Y\leq Z\leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
X Y Z
Output
Output three lines.
The first line should contain S_1 in the following format, where |S_1| denotes the length of S_1 and S_{1,i} denotes the i-th element of S_1:
|S_1| S_{1,1} S_{1,2} \dots S_{1,|S_1|}
The second line should contain S_2 and the third line should contain S_3, both in the same format as S_1.
If there are multiple solutions, you may output any of them.
Sample Input 1
4 5 5
Sample Output 1
10 1 1 0 0 1 0 1 0 1 1 8 1 1 0 1 0 0 1 1 11 1 0 0 0 1 1 0 1 0 1 0
It can be verified that S_1=(1,1,0,0,1,0,1,0,1,1),S_2=(1,1,0,1,0,0,1,1),S_3=(1,0,0,0,1,1,0,1,0,1,0) satisfies the conditions as follows:
- The lengths of S_1,S_2,S_3 are 10,8,11, respectively, all of which are between 1 and 1000, inclusive.
- The longest sequences that are both a contiguous subsequence of S_1 and a contiguous subsequence of S_2 are (1,0,0,1) and (1,0,1,0), with length X=4.
- The longest sequences that are both a contiguous subsequence of S_1 and a contiguous subsequence of S_3 are (1,0,1,0,1) and (0,1,0,1,0), with length Y=5.
- The longest sequence that is both a contiguous subsequence of S_2 and a contiguous subsequence of S_3 is (1,1,0,1,0), with length Z=5.
- \max(\max(S_1),\max(S_2),\max(S_3))=1, and it can be shown that it is impossible to satisfy the above four conditions with \max(\max(S_1),\max(S_2),\max(S_3))=0, so this is minimal.