E. Дарааллыг хувиргах

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Танд үл буурах $x_{1}, x_{2}, ..., x_{n}$ $(1 ≤ x_{1} ≤ x_{2} ≤ ... ≤ x_{n} ≤ q)$ дараалал, мөн $a$, $b$ $(a ≤ b; a \cdot (n - 1) < q)$ бүхэл тоонууд өгөгджээ.

Таны даалгавар бол $x_{1}, x_{2}, ..., x_{n}$ дарааллыг ямар нэг $y_{1}, y_{2}, ..., y_{n}$ $(1 ≤ y_{i} ≤ q; a ≤ y_{i + 1} - y_{i} ≤ b)$ дараалал руу хувиргах юм. Хувиргалтын зардлыг $\sum\limits_{i=1}^n (y_i - x_i)^2$ нийлбэрээр тодорхойлно. Дээр тодорхойлсон хувиргалтын зардал хамгийн бага байхаар $y$ дарааллыг сонгоно уу.

Оролт

Эхний мөрөнд $n, q, a, b$ $(2 ≤ n ≤ 6000; 1 ≤ q, a, b ≤ 10^{9}; a \cdot (n - 1) < q; a ≤ b)$ дөрвөн бүхэл тоо байна.

Хоёр дахь мөр нь үл буурах $x_{1}, x_{2}, ..., x_{n}$ $(1 ≤ x_{1} ≤ x_{2} ≤ ... ≤ x_{n} ≤ q)$ бүхэл тоон дарааллыг агуулна.

Гаралт

Эхний мөрөнд $n$ ширхэг бодит тоог хэвлэнэ. Энэ нь хайж буй $y_{1}, y_{2}, ..., y_{n}$ $(1 ≤ y_{i} ≤ q; a ≤ y_{i + 1} - y_{i} ≤ b)$ дараалал.

Хоёр дахь мөрөнд $\sum\limits_{i=1}^n (y_i - x_i)^2$ хамгийн бага байх хувиргалтын үнийг хэвлэнэ.

Олон оновчтой шийд байгаа бол тэдгээрийн аль нэгийг хэвлэнэ үү. Абсолют буюу харьцангуй алдаа нь $10^{ - 6}$-с хэтрэхгүй бол хариуг зөв гэж үзнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
3 6 2 2
1 4 6
Гаралт
1.666667 3.666667 5.666667 
0.666667
Оролт
10 100000 8714 9344
3378 14705 17588 22672 32405 34309 37446 51327 81228 94982
Гаралт
1.000000 8715.000000 17429.000000 26143.000000 34857.000000 43571.000000 52285.000000 61629.000000 70973.000000 80317.000000 
797708674.000000
Сэтгэгдлүүдийг ачааллаж байна...