题目背景
孩子们眼中的希望 是什么形状
是否醒来有面包当早餐 再喝碗热汤
农夫被烧毁土地跟村庄 终于拿起枪
她却慢慢习惯放弃了抵抗
孩子们眼中的希望 是什么形状
是否院子有秋千可以荡 口袋里有糖
刺刀的光被仇恨所擦亮 在远方野蛮
而她却微笑着不知道慌张
——《止战之殇》
题目描述
有 n 个因为战争而历尽苦难的孩子,他们想要终止野蛮的战争。他们每人要选定一个整数作为自己的 天真值,第 i 个孩子的 天真值 为 ai,天真值 可以为负数。然后他们每次会选择两个孩子 x,y 一起进行一次值为正整数 k 的 祈祷,直到每人都进行了 n−1 次 祈祷。一次由两个 天真值 分别为 ax 和 ay 的孩子一起进行一次值为 k 的 祈祷 能够产生两个值分别为 ax+k 和 ay+k 的 殇歌。显然进行完所有 祈祷 后会产生 n(n−1) 个 殇歌。如果这些 殇歌 的值 恰好 为 1 到 n(n−1) 的正整数 各一个,那么整个过程为一次 止战之殇,可以终止血腥的战争。现在孩子们想要知道他们怎样选择自己的 天真值 和每次 祈祷 的值才能制造出 止战之殇,由于他们还太小,所以就请你帮助他们。
题意简述
给定 n,构造一个长度为 n 的整数列 a1,a2,…,an 与 2n(n−1) 个三元组 xi,yi,ki(xi=yi,ki∈Z+),使得 ∀i∈{1,2,…,n},∑j=12n(n−1)([xj==i]+[yj==i])=n−1 且 {axi+ki:i=1,2,…,2n(n−1)}∪{ayi+ki:i=1,2,…,2n(n−1)}={1,2,…,n(n−1)}。
输入格式
一行 3 个整数 n,op1,op2。
如果 op1=1,那么必须满足每一对 1≤x<y≤n 的 x,y 必须 恰好 一起进行一次 祈祷;否则没有特殊限制。
如果 op2=1,那么 天真值 必须为非负数;否则没有特殊限制。
输出格式
如果有解,第一行输出 n;否则输出 −1。
如果有解,第二行输出 n 个非负整数表示编号为 1 到 n 的孩子分别的 天真值,接下来 2n(n−1) 行每行输出第 i 次 祈祷 选定的 x,y,k。
输入输出样例
1 0 0
1
1
2 0 0
2
0 -1
1 2 2
3 0 1
-1
4 1 1
4
5 2 0 3
1 3 7
1 4 1
2 4 7
2 1 6
4 3 2
3 2 1
说明/提示
样例解释
对于第一组样例,最后没有生成任何 殇歌,满足要求。
对于第二组样例,0+2=2,−1+2=1,恰好为 1 到 2 各一个。
对于第三组样例,可以发现没有满足条件的方法。
对于第四组样例,有
5+7=12,0+7=7,5+1=6,3+1=4,2+7=9,3+7=10,
2+6=8,5+6=11,3+2=5,0+2=2,0+1=1,2+1=3,
恰好为 1 到 12 各一个。
数据范围
本题共有 20 个数据点,每个数据点 5 分,各个数据点的数据范围与限制如下。
Testdata No. |
n≤ |
op1 |
op2 |
特殊限制 |
1∼4 |
300 |
0 |
1 |
n 为偶数 |
5∼10 |
n 为奇数 |
11∼17 |
3×103 |
1 |
无 |
18∼20 |
7 |
0 |
对于 100% 的数据,1≤n≤3×103,op1,op2∈{0,1}。
提示
本题提供 Special Judge 源码 和 checker.exe
,使用方法为:
命令行在目标文件夹输入指令:
checker.exe input.txt output.txt output.txt
其中 input.txt
是输入数据文件,output.txt
是程序运行结果文件。观察评判结果即可。
Accepted.
表示答案正确。
Misjudgment of the existence of the answer.
表示有解性判断不正确。
Negative ai.
表示 ai 为负数(op2=1 时)。
Invalid (x,y,k) No.i.
表示 xi 或 yi 不在 [1,n] 中或 xi=yi 或 ki 不为正整数。
Invalid sum No.i.
表示 axi+ki 或 ayi+ki 不在 [1,n(n−1)] 中。
Sum No.i already appeared.
表示 axi+ki 或 ayi+ki 已经出现过。
(x,y) No.i already appeared.
表示 (xi,yi) 已经出现过(op1=1 时)。
请务必保证输出格式正确,否则 Special Judge 可能会返回 Unkown Error 等不可预估的结果。