print2155. Приблизительно

printПриблизительно

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Однажды королевский шпион Цилритш решил отправить королю послание. Он закодировал его в виде неубывающей последовательности вещественных чисел, записал на куске кожи единорога и отправил почтовым голубем. К сожалению, голубь оказался поражен стрелой злого орка и упал в болото. Слуги короля нашли послание, но оно оказалось испорчено водой и прочитать его оказалось непросто.
В результате расшифровки с применением всех известных в королевстве колдовских заклинаний удалось получить лишь последовательность целых чисел `a_1,\ a_2,\ …,\ a_n`. Тогда король повелел найти наиболее похожую на данную неубывающую последовательность вещественных чисел `b_1,\ b_2,\ …,\ b_n`. Посовещавшись, придворные мудрецы решили найти такую последовательность, чтобы величина
`s\ =\ sum_{i=1}^n\ (a_i-b_i)^2`
была как можно меньше.
Помогите им найти такую последовательность.
Первая строка входного файла содержит `n` – длину полученной последовательности. Вторая строка содержит `n` целых чисел: `a_1,\ a_2,\ …,\ a_n` (`1\ ≤\ n\ ≤\ 200\ 000`, `1\ ≤\ a_i\ ≤\ 10^6`).
Выведите `n` чисел: самую похожую на заданную во входном файле неубывающую последовательность. Если решений несколько, выведите любое. В вашем ответе величина `s` должна иметь либо абсолютную, либо относительную погрешность не больше `10^{-9}`. Это означает, что если ваш ответ `a`, а правильный ответ `b`, величина `{|a-b|}/{max(b,\ 1)}` не должна превышать `10^{-9}`.

Пример ввода 1

5
5 4 3 2 1

Пример вывода 1

3 3 3 3 3

Пример ввода 2

9
3 2 1 8 6 4 9 7 5

Пример вывода 2

2.0 2.0 2.0 6.0 6.0 6.0 7.0 7.0 7.0
Источник: neerc.ifmo.ru/school
loading