Codeforces Global Round 10 |
---|
Закончено |
Омкар стоит у подножия горы Селеста. Вершина находится в $$$n$$$ метрах от него, и он может видеть всю гору до вершины, поэтому для каждого $$$1 \leq j \leq n$$$ он знает, что высота горы в точке в $$$j$$$ метрах от него равна $$$h_j$$$. Известно, что для всех $$$j$$$ удовлетворяющих $$$1 \leq j \leq n - 1$$$, $$$h_j < h_{j + 1}$$$ (то есть высоты строго возрастают).
Внезапно происходит оползень! Пока происходит оползень, происходит следующее: каждую минуту, если $$$h_j + 2 \leq h_{j + 1}$$$, то один квадратный метр грязи будет скользить с позиции $$$j + 1$$$ в позицию $$$j$$$, так что $$$h_{j + 1}$$$ уменьшается на $$$1$$$, а $$$h_j$$$ увеличивается на $$$1$$$. Эти изменения происходят одновременно, так, например, если $$$h_j + 2 \leq h_{j + 1}$$$ и $$$h_{j + 1} + 2 \leq h_{j + 2}$$$ для какого-то $$$j$$$, то $$$h_j$$$ будет увеличено на $$$1$$$, $$$h_{j + 2}$$$ будет уменьшено на $$$1$$$, а $$$h_{j + 1}$$$ будет увеличено и уменьшено на $$$1$$$, что означает, что на самом деле $$$h_{j + 1}$$$ в течение этой минуты не изменится.
Оползень заканчивается, когда не будет такого $$$j$$$, что $$$h_j + 2 \leq h_{j + 1}$$$. Помогите Омкару выяснить, каковы будут значения $$$h_1, \dots, h_n$$$ после окончания оползня. Можно доказать, что при заданных ограничениях оползень всегда заканчивается через некоторое число минут.
Обратите внимание, что из-за большого количества входных данных, рекомендуется, чтобы ваш код использовал быстрый ввод.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^6$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$h_1, h_2, \dots, h_n$$$ удовлетворяющих $$$0 \leq h_1 < h_2 < \dots < h_n \leq 10^{12}$$$ — высоты.
Выведите $$$n$$$ целых чисел, где $$$j$$$-е число — это значение $$$h_j$$$ после остановки оползня.
4 2 6 7 8
5 5 6 7
Первоначально гора имеет высоты $$$2, 6, 7, 8$$$.
В первую минуту у нас есть $$$2 + 2 \leq 6$$$, таким образом $$$2$$$ увеличивается до $$$3$$$, а $$$6$$$ уменьшается до $$$5$$$, оставляя $$$3, 5, 7, 8$$$.
Во вторую минуту у нас есть $$$3 + 2 \leq 5$$$ и $$$5 + 2 \leq 7$$$, таким образом $$$3$$$ увеличивается до $$$4$$$, $$$5$$$ остается без изменений, а $$$7$$$ уменьшается до $$$6$$$, оставляя $$$4, 5, 6, 8$$$.
На третьей минуте у нас есть $$$6 + 2 \leq 8$$$, так что $$$6$$$ увеличивается до $$$7$$$, а $$$8$$$ уменьшается до $$$7$$$, оставляя $$$4, 5, 7, 7$$$.
На четвертой минуте у нас есть $$$5 + 2 \leq 7$$$, таким образом $$$5$$$ увеличивается до $$$6$$$, а $$$7$$$ уменьшается до $$$6$$$, оставляя $$$4, 6, 6, 7$$$.
На пятой минуте у нас есть $$$4 + 2 \leq 6$$$, поэтому $$$4$$$ увеличивается до $$$5$$$, а $$$6$$$ уменьшается до $$$5$$$, оставляя $$$5, 5, 6, 7$$$.
На шестой минуте ничего больше не может измениться, поэтому оползень останавливается, и наш ответ — $$$5, 5, 6, 7$$$.
Название |
---|