2023-11-04 11:22:02
发布于：浙江
Farmer John 的奶牛们决定为 Farmer Nhoj 农场的奶牛们举办一场编程竞赛。为了使问题尽可能有趣，他们花费了大量时间来构造具有挑战性的测试用例。特别是对于一个问题，「Haybales」，奶牛们需要你的帮助来设计具有挑战性的测试用例。这有关解决以下这个有些奇妙的问题：
有一个有序整数数组 x1≤x2≤⋯≤xN
（1≤N≤105
），和一个整数 K
。你不知道这个数组以及 K
，但你知道对于每个索引 i
使得 xji≤xi+K
的最大索引 ji
。保证有 i≤ji
以及 j1≤j2≤⋯≤jN≤N
。
给定这些信息，Farmer John 的奶牛需要构造任意一个数组以及整数 K
与该信息一致。构造需要满足对于所有 i
有 0≤xi≤1018
，并且 1≤K≤1018
。
可以证明这一定是可行的。请帮助 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
的元素。类似地，
j2=2
被满足是由于 a2=6≤6+6
而 a3=17>6+6
j3=4
被满足是由于 a4=22≤17+6
而 a5=27>17+6
j4=5
被满足是由于 a5=27≤22+6
而 a5=32>22+6
j5=6
被满足是由于 a6=32≤27+6
且 a6
是数组的最后一个元素
j6=6
被满足是由于 a6=32≤32+6
且 a6
是数组的最后一个元素
对于输入样例，这并不是唯一正确的输出。例如，你也可以输出数组 [1,2,4,5,6,7]
和 K=1
。
测试点性质：
所有测试点的 50% 满足 N≤5000
。
其余测试点没有额外限制。
这里空空如也
有帮助，赞一个