CF280E Sequence Transformation

给定一个非递减序列 $x_1, x_2, ..., x_n$，其中 $1 \le x_1 \le x_2 \le ... \le x_n \le q$。你还有两个整数 $a$ 和 $b$，满足 $a \le b$ 且 $a \cdot (n-1) < q$。 你的任务是将序列 $x_1, x_2, ..., x_n$ 转换为序列 $y_1, y_2, ..., y_n$，满足 $1 \le y_i \le q$ 且 $a \le y_{i+1} - y_i \le b$。该变换的代价为下式的和：。你的目标是选择一种 $y$ 的方案，使变换代价最小。

第一行包含四个整数 $n, q, a, b$，满足 $2 \le n \le 6000$，$1 \le q, a, b \le 10^9$，$a \cdot (n-1) < q$，$a \le b$。 第二行包含一个非递减的整数序列 $x_1, x_2, ..., x_n$，满足 $1 \le x_1 \le x_2 \le ... \le x_n \le q$。

第一行输出 $n$ 个实数，即寻找到的序列 $y_1, y_2, ..., y_n$，满足 $1 \le y_i \le q$，$a \le y_{i+1} - y_i \le b$。第二行输出最小的变换代价，即 。 如果有多组最优解，可以任意输出其中一组。 当你的答案的绝对误差或相对误差不超过 $10^{-6}$ 时，将被视为正确。

由 ChatGPT 5 翻译