Good Bye 2023 |
---|
Закончено |
У Маши и Оли скоро важная командная олимпиада. В честь этого Маша, для разминки, предложила сыграть Оле в следующую игру:
Есть массив $$$a$$$ размера $$$n$$$. Первой ходит Маша, игроки ходят по-очереди. Каждый ход описывается следующей последовательностью действий:
$$$\bullet$$$ Если размер массива равен $$$1$$$ — игра завершается.
$$$\bullet$$$ Игрок, который сейчас ходит, выбирает два различных индекса $$$i$$$, $$$j$$$ ($$$1 \le i, j \le |a|$$$), и проделывает следующую операцию — удаляет $$$a_i$$$ и $$$a_j$$$ из массива и добавляет в массив число равное $$$\lfloor \frac{a_i + a_j}{2} \rfloor \cdot 2$$$. Иными словами, сначала делит сумму чисел $$$a_i$$$, $$$a_j$$$ на $$$2$$$ с округлением вниз, после чего результат умножает на $$$2$$$.
Маша стремится максимизировать итоговое число, Оля же — минимизировать.
Маша и Оля решили сыграть на каждом непустом префиксе первоначального массива $$$a$$$, и попросили вас об одной помощи.
Для каждого $$$k = 1, 2, \ldots, n$$$ ответьте на следующий вопрос. Пусть в игре присутствуют только первые $$$k$$$ элементов массива $$$a$$$, соответственно с индексами $$$1, 2, \ldots, k$$$. Какое число тогда останется при оптимальной игре обоих игроков?
Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — размер массива.
Во второй строке содержится $$$n$$$ целых чисел $$$a_1,a_2, \ldots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — массив, на котором играют Маша и Оля.
Гарантируется, что сумма $$$n$$$ по всем входным данным не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите $$$n$$$ целых чисел. $$$k$$$-е из этих чисел должно быть равно числу, которое останется в конце при оптимальной игре обоих, на массиве, состоящем из первых $$$k$$$ элементов массива $$$a$$$.
413166 3 7 2 5 433 10 1157 13 11 19 1
31 6 8 16 18 22 26 3 12 24 7 20 30 48 50
В третьем наборе входных данных для префикса длины $$$1$$$ ответ $$$3$$$. Для префикса длины $$$2$$$ у Маши есть один вариант для хода, поэтому ответ $$$12$$$. Для префикса длины $$$3$$$ у Маши есть три возможных хода: она выбирает $$$3$$$ и $$$10$$$, тогда число в конце $$$22$$$, $$$3$$$ и $$$11$$$, тогда число в конце $$$24$$$, $$$10$$$ и $$$11$$$, тогда число в конце $$$22$$$, значит Маша выберет $$$3$$$ и $$$11$$$ и получит $$$24$$$.
Название |
---|