Tests for Haybales

题目描述

Farmer John 的奶牛决定为 Farmer Nhoj 的农场奶牛举办一场编程竞赛。为了让题目尽可能有趣，她们花了很多时间设计刁钻的输入数据。对于其中一道题目“Haybales”，奶牛需要你帮助构造具有挑战性的输入。

这需要解决下面这个有点耐人寻味的问题：

给定一个已排序的整数数组 $x_1 \leq x_2 \leq \dotsb \leq x_N$（$1 \leq N \leq 10^5$），以及一个整数 $K$。你并不知道数组的具体数值或 $K$ 的值，但你知道对每个下标 $i$，最大的下标 $j_i$ 满足 $x_{j_i} \leq x_i + K$。保证 $i\le j_i$ 且 $j_1\le j_2\le \cdots \le j_N\le N$。

给定这些信息，Farmer John 的奶牛需要构造任意一个数组以及某个整数 $K$，使其与这些信息一致。构造需要满足对所有 $i$ 都有 $0 \leq x_i \leq 10^{18}$，并且 $1 \leq K \leq 10^{18}$。

可以证明这总是可行的。请帮助 Farmer John 的奶牛解决这个问题！

输入格式

第一行输入 $N$。 下一行输入 $j_1,j_2,\ldots,j_N$。

输出格式

输出 $K$，然后在接下来的各行分别输出 $x_1,\ldots,x_N$。任何合法的输出都会被接受。

6
2 2 4 5 6 6

6
1
6
17
22
27
32

提示

样例输出对应数组 $a = [1, 6, 17, 22, 27, 32]$ 且 $K = 6$。 $j_1 = 2$ 成立，因为 $a_2 = 6 \leq 1 + 6 = a_1 + K$，但 $a_3 = 17 > 1 + 6 = a_1 + K$，所以 $a_2$ 是不超过 $a_1$ 的最大元素。类似地， $j_2 = 2$ 成立，因为 $a_2 = 6 \leq 6 + 6$ 但 $a_3 = 17 > 6 + 6$ $j_3 = 4$ 成立，因为 $a_4 = 22 \leq 17 + 6$ 但 $a_5 = 27 > 17 + 6$ $j_4 = 5$ 成立 因为 $a_5 = 27 \leq 22 + 6$ 但 $a_5 = 32 > 22 + 6$ $j_5 = 6$ 成立，因为 $a_6 = 32 \leq 27 + 6$ 且 $a_6$ 是数组的最后一个元素 $j_6 = 6$ 成立，因为 $a_6 = 32 \leq 32 + 6$ 且 $a_6$ 是数组的最后一个元素 这并不是样例输入的唯一正确输出。例如，你也可以输出数组 $[1, 2, 4, 5, 6, 7]$ 且 $K = 1$。 SCORING: 对于 50% 的输入，$N\le 5000$ 对于剩余输入，没有额外限制。 题目贡献者：Danny Mittal

标签: USACO|2022|Gold

来源

USACO|2022|Gold