CF1129B Wrong Answer

考虑如下问题：给定一个包含 $n$ 个整数的数组 $a$（下标从 $0$ 到 $n-1$），求 $$ \max\limits_{0 \leq l \leq r \leq n-1} \sum\limits_{l \leq i \leq r} (r-l+1) \cdot a_i $$ 在本题中，$1 \leq n \leq 2000$，且 $|a_i| \leq 10^6$。 为了解决上述问题，Alice 很快想出了一个极快的贪心算法并进行了编码。她的伪代码实现如下： ``` function find_answer(n, a) # 假设 n 是 1 到 2000 之间的整数 # 假设 a 是一个包含 n 个整数的列表：a[0], a[1], ..., a[n-1] res = 0 cur = 0 k = -1 for i = 0 to i = n-1 cur = cur + a[i] if cur < 0 cur = 0 k = i res = max(res, (i-k)*cur) return res ``` 然而，正如你所见，Alice 的想法并不完全正确。例如，假设 $n = 4$ 且 $a = [6, -8, 7, -42]$，则 find\_answer(n, a) 会返回 $7$，但正确答案是 $3 \cdot (6-8+7) = 15$。 你告诉 Alice 她的解法是错误的，但她并不相信。 给定一个整数 $k$，你需要构造一个长度为 $n$ 的整数序列 $a$，使得正确答案与 Alice 算法的输出恰好相差 $k$。注意，$n$ 和序列内容由你选择，但必须满足上述约束：$1 \leq n \leq 2000$，且每个元素的绝对值不超过 $10^6$。如果不存在这样的序列，请输出相应信息。

第一行包含一个整数 $k$（$1 \leq k \leq 10^9$）。

如果不存在满足条件的序列，输出 “-1”。 否则，第一行输出一个整数 $n$（$1 \leq n \leq 2000$），表示序列的长度。 第二行输出 $n$ 个用空格分隔的整数 $a_0, a_1, \ldots, a_{n-1}$（$|a_i| \leq 10^6$）。

第一个样例对应题目描述中的例子。 第二个样例中，一种可行解为 $n = 7$，$a = [30, -12, -99, 123, -2, 245, -300]$，此时 find\_answer(n, a) 返回 $1098$，而正确答案为 $1710$。 由 ChatGPT 4.1 翻译