Codeforces Round 618 (Div. 1) |
---|
Закончено |
$$$n$$$ цистерн с водой стоят в ряд, $$$i$$$-я из них содержит $$$a_i$$$ литров воды. Цистерны пронумерованны от $$$1$$$ до $$$n$$$ слева направо.
Вы можете выполнить следующую операцию: выбрать некоторый подотрезок $$$[l, r]$$$ ($$$1\le l \le r \le n$$$), и перераспределить воду с цистерн $$$l, l+1, \dots, r$$$ между ними равномерно. Другими словами, заменить каждое из $$$a_l, a_{l+1}, \dots, a_r$$$ на $$$\frac{a_l + a_{l+1} + \dots + a_r}{r-l+1}$$$. К примеру, если для обьемов $$$[1, 3, 6, 7]$$$ вы выберете $$$l = 2, r = 3$$$, вы получите обьемы $$$[1, 4.5, 4.5, 7]$$$. Вы можете выполнять данную операцию любое количество раз.
Какую лексикографически минимальную последовательность обьемов воды вы можете получить?
Напомним:
Последовательность $$$a$$$ лексикографически меньше последовательности $$$b$$$ равной длины, если и только если выполняется следующее: в первой (слева) позиции, где $$$a$$$ и $$$b$$$ отличаются, в последовательности $$$a$$$ стоит меньший элемент, чем в $$$b$$$.
Первая строка содержит целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — количество цистерн с водой.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — обьемы воды в цистернах изначально, в литрах.
Из-за большого размера входных данных, не рекомендуется считывать их как doubles.
Выведите лексикографически минимальную последовательность, которую вы можете получить. В $$$i$$$-й строке выведите итоговый обьем воды в $$$i$$$-й цистерне.
Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка каждого $$$a_i$$$ не превосходит $$$10^{-9}$$$.
Формально, пусть ваш ответ равен $$$a_1, a_2, \dots, a_n$$$, а ответ жюри равен $$$b_1, b_2, \dots, b_n$$$. Ваш ответ будет зачтен, если и только если $$$\frac{|a_i - b_i|}{\max{(1, |b_i|)}} \le 10^{-9}$$$ для каждого $$$i$$$.
4 7 5 5 7
5.666666667 5.666666667 5.666666667 7.000000000
5 7 8 8 10 12
7.000000000 8.000000000 8.000000000 10.000000000 12.000000000
10 3 9 5 5 1 7 5 3 8 7
3.000000000 5.000000000 5.000000000 5.000000000 5.000000000 5.000000000 5.000000000 5.000000000 7.500000000 7.500000000
В первом примере, вы можете получить лексикографически минимальную последоательность, применив операцию к подотрезку $$$[1, 3]$$$.
Во втором примере, вы не можете получить меньшую лексикографически последовательность.
Название |
---|