← 返回题目列表

Codeforces · 280/E

E. 序列变换

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

你有一个非递减序列 x1, x2, ..., xn (1 ≤ x1 ≤ x2 ≤ ... ≤ xn ≤ q)。您还有两个整数 a 和 b (a ≤ b; a·(n - 1) < q)。

您的任务是将序列 x1, x2, ..., xn 转换为某个序列 y1, y2, ..., yn (1 ≤ yi ≤ q; a ≤ yi + 1 - yi ≤ b)。转换价格为以下总和:$$\sum_{i=1}^{n}(y_i - x_i)^2$$。您的任务是选择序列 y 来最小化所描述的转换价格。

输入

第一行包含四个整数 n、q、a、b (2 ≤ n ≤ 6000;1 ≤ q、a、b ≤ 109;a·(n - 1) < q;a ≤ b)。

第二行包含一个非递减整数序列 x1, x2, ..., xn (1 ≤ x1 ≤ x2 ≤ ... ≤ xn ≤ q)。

输出

在第一行中打印 n 个实数 — 所寻找的序列 y1, y2, ..., yn (1 ≤ yi ≤ q; a ≤ yi + 1 - yi ≤ b)。在第二行中打印最小转换价格,即 $$\sum_{i=1}^{n}(y_i - x_i)^2$$。

如果有多个最佳答案,您可以打印其中任何一个。

如果绝对或相对误差不超过 10 - 6,则答案将被视为正确。

示例

输入 #1

3 6 2 2
1 4 6

输出 #1

1.666667 3.666667 5.666667
0.666667

输入 #2

10 100000 8714 9344
3378 14705 17588 22672 32405 34309 37446 51327 81228 94982

输出 #2

1.000000 8715.000000 17429.000000 26143.000000 34857.000000 43571.000000 52285.000000 61629.000000 70973.000000 80317.000000
797708674.000000