← 返回题目列表

Codeforces · 1129/B

B. 错误答案

中文机器翻译题面 查看原题

考虑以下问题:给定一个包含 $$$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 2\,000$$$ 和 $$$|a_i| \leq 10^6$$$。

为了解决所描述的问题,爱丽丝很快想出了一个极快的贪婪算法并对其进行了编码。她的伪代码实现如下:

另外,正如你所看到的,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 2\,000$$$ 并且每个元素的绝对值不超过 $$$10^6$$$。如果不存在这样的顺序,则确定。

输入

第一行也是唯一一行包含一个整数 $$$k$$$ ($$$1 \leq k \leq 10^9$$$)。

输出

如果没有找到的序列,则打印“-1”。

否则,在第一行中,打印一个整数 $$$n$$$ ($$$1 \leq n \leq 2\,000$$$),表示序列中元素的数量。

然后,在第二行中,打印 $$$n$$$ 以空格分隔的整数:$$$a_0, a_1, \ldots, a_{n-1}$$$ ($$$|a_i| \leq 10^6$$$)。

示例

输入 #1

8

输出 #1

4
6 -8 7 -42

输入 #2

612

输出 #2

7
30 -12 -99 123 -2 245 -300

注意

第一个示例对应于问题陈述中给出的示例。

在第二个示例中,一个答案是 $$$n = 7$$$,其中 $$$a = [30, -12, -99, 123, -2, 245, -300]$$$,在这种情况下 find_answer(n, a) 返回 $$$1098$$$,而正确答案是 $$$1710$$$。