← 返回题目列表

Codeforces · 1500/F

F. 橱柜跳跃

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

在克罗什曾经住过的房子里,他有$$$n$$$个橱柜排成一排,第$$$i$$$个橱柜的高度为$$$h_i$$$。克罗什最近搬家了,但他没能一起搬橱柜。现在他想购买 $$$n$$$ 个新橱柜,以便它们看起来尽可能与旧橱柜相似。

Krosh 不记得橱柜的确切高度,但对于每三个连续的橱柜,他会记住其中最高和最矮的橱柜之间的高度差。换句话说,如果橱柜的高度为 $$$h_1, h_2, \ldots, h_n$$$,那么 Krosh 会记住所有 $$$1 的值 $$$w_i = \max(h_{i}, h_{i + 1}, h_{i + 2}) - \min(h_{i}, h_{i + 1}, h_{i + 2})$$$ \leq i \leq n - 2$$$。

Krosh 想购买这样的 $$$n$$$ 橱柜,所有值 $$$w_i$$$ 保持不变。帮助他确定所需的橱柜高度,或者确定他记错了一些东西并且没有合适的高度顺序。

输入

第一行包含两个整数 $$$n$$$ 和 $$$C$$$ ($$$3 \leq n \leq 10^6$$$, $$$0 \leq C \leq 10^{12}$$$) - 橱柜的数量和可能的 $$$w_i$$$ 的限制。

第二行包含 $$$n - 2$$$ 整数 $$$w_1, w_2, \ldots, w_{n - 2}$$$ ($$$0 \leq w_i \leq C$$$) — 语句中定义的值。

输出

如果没有合适的 $$$n$$$ 橱柜序列,则打印“NO”。

否则在第一行打印“YES”,然后在第二行打印 $$$n$$$ 整数 $$$h'_1, h'_2, \ldots, h'_n$$$ ($$$0 \le h'_i \le 10^{18}$$$) — 要购买的橱柜的高度,从左到右。

我们可以证明,如果有一个解,那么也存在一个满足高度约束的解。

如果有多个答案,请打印其中一个。

示例

输入 #1

7 20
4 8 12 16 20

输出 #1

YES
4 8 8 16 20 4 0

输入 #2

11 10
5 7 2 3 4 5 2 1 8

输出 #2

YES
1 1 6 8 6 5 2 0 0 1 8

输入 #3

6 9
1 6 9 0

输出 #3

NO

注意

考虑第一个示例:

- $$$w_1 = \max(4, 8, 8) - \min(4, 8, 8) = 8 - 4 = 4$$$
- $$$w_2 = \max(8, 8, 16) - \min(8, 8, 16) = 16 - 8 = 8$$$
- $$$w_3 = \max(8, 16, 20) - \min(8, 16, 20) = 20 - 8 = 12$$$
- $$$w_4 = \max(16, 20, 4) - \min(16, 20, 4) = 20 - 4 = 16$$$
- $$$w_5 = \max(20, 4, 0) - \min(20, 4, 0) = 20 - 0 = 20$$$

还有其他可能的解决方案,例如以下:$$$0, 1, 4, 9, 16, 25, 36$$$。