P6972: 测试用例
传统题
1.000s
时间限制
256MB
内存限制
1 提交
0 解决
【题目描述】
【题目描述】
Farmer John
的奶牛们决定为 Farmer Nhoj 农场的奶牛们举办一场编程竞赛。为了使问题尽可能有趣，他们花费了大量时间来构造具有挑战性的测试用例。特别是对于一个问题，「Haybales」，奶牛们需要你的帮助来设计具有挑战性的测试用例。这有关解决以下这个有些奇妙的问题：
有一个有序整数数组 x1≤x2≤⋯≤xN
（1≤N≤10
^5
），和一个整数 K
。你不知道这个数组以及 K
，但你知道对于每个索引 i
使得 xji≤xi+K 的最大索引 ji
。保证有 i≤ji 以及j1≤j2≤⋯≤jN≤N。
给定这些信息，Farmer John
的奶牛需要构造任意一个数组以及整数 K 与该信息一致。构造需要满足对于所有 i 有 0≤xi≤10^18
，并且 1≤K≤10
^18
。
可以证明这一定是可行的。请帮助 Farmer John
的奶牛们解决这一问题！
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 N
。第二行包含 j1,j2,…,jN
。
【
输出格式】
（输出至终端 /
标准输出）：
输出 K
，然后在下一行输出 x1,…,xN
。任何合法的输出均正确。
【
输入样例】
：
6
2 2 4 5 6 6
【
输出样例】
：
6
1
6
17
22
27
32
【样例说明】
输出样例为数组 a=[1,6,17,22,27,32]
以及 K=6。j1=2
被满足是由于 a2=6≤1+6=a1+K 而 a3=17>1+6=a1+K，从而 a2
是最大的不超过 a1+K 的元素。类似地，
1.j2=2
被满足是由于 a2=6≤6+6 而 a3=17>6+6
2.j3=4
被满足是由于 a4=22≤17+6
而 a5=27>17+6
3.j4=5
被满足是由于 a5=27≤22+6
而 a5=32>22+6
4.j5=6
被满足是由于 a6=32≤27+6
且 a6 是数组的最后一个元素
5.j6=6
被满足是由于 a6=32≤32+6
且 a6 是数组的最后一个元素
对于输入样例，这并不是唯一正确的输出。例如，你也可以输出数组 [1,2,4,5,6,7]
和 K=1。
【
测试点性质】
：
所有测试点的 50%
满足N≤5000。
其余测试点没有额外限制。