310976: CF1916C. Training Before the Olympiad
Description
Masha and Olya have an important team olympiad coming up soon. In honor of this, Masha, for warm-up, suggested playing a game with Olya:
There is an array $a$ of size $n$. Masha goes first, and the players take turns. Each move is described by the following sequence of actions:
$\bullet$ If the size of the array is $1$, the game ends.
$\bullet$ The player who is currently playing chooses two different indices $i$, $j$ ($1 \le i, j \le |a|$), and performs the following operation — removes $a_i$ and $a_j$ from the array and adds to the array a number equal to $\lfloor \frac{a_i + a_j}{2} \rfloor \cdot 2$. In other words, first divides the sum of the numbers $a_i$, $a_j$ by $2$ rounding down, and then multiplies the result by $2$.
Masha aims to maximize the final number, while Olya aims to minimize it.
Masha and Olya decided to play on each non-empty prefix of the initial array $a$, and asked for your help.
For each $k = 1, 2, \ldots, n$, answer the following question. Let only the first $k$ elements of the array $a$ be present in the game, with indices $1, 2, \ldots, k$ respectively. What number will remain at the end with optimal play by both players?
InputThe first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the size of the array.
The second line contains $n$ integers $a_1,a_2, \ldots,a_n$ ($1 \leq a_i \leq 10^9$) — the array on which Masha and Olya play.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
OutputFor each test case, output $n$ integers. The $k$-th of these numbers should be equal to the number that will remain at the end with optimal play by both players, on the array consisting of the first $k$ elements of the array $a$.
ExampleInput4 1 31 6 6 3 7 2 5 4 3 3 10 11 5 7 13 11 19 1Output
31 6 8 16 18 22 26 3 12 24 7 20 30 48 50Note
In the third test case, for a prefix of length $1$, the answer is $3$. For a prefix of length $2$, Masha has only one move, so the answer is $12$. For a prefix of length $3$, Masha has three possible moves: she chooses $3$ and $10$, then the final number is $22$, $3$ and $11$, then the final number is $24$, $10$ and $11$, then the final number is $22$, so Masha will choose $3$ and $11$ and get $24$.
Output
玛莎和奥尔加即将参加一场重要的团队奥林匹克比赛。为了热身，玛莎提议和奥尔加玩一个游戏。游戏规则如下：
- 有一个长度为n的数组a。
- 玛莎先手，轮流进行。
- 每轮操作如下：
- 如果数组长度为1，游戏结束。
- 当前玩家选择两个不同的下标i和j（1≤i,j≤|a|），然后执行以下操作：从数组中移除a_i和a_j，并向数组中添加一个数，该数为 ⌊(a_i + a_j)/2⌋ * 2。换句话说，就是先将a_i和a_j的和除以2并向下取整，然后将结果乘以2。
- 玛莎的目标是最大化最终的结果，而奥尔加的目标是最小化结果。
玛莎和奥尔加决定在数组a的每个非空前缀上进行游戏，并请求你的帮助。
对于每个k=1,2,…,n，回答以下问题：仅考虑数组a的前k个元素，下标分别为1,2,…,k。在双方都进行最优游戏的情况下，最终会剩下什么数？
输入数据格式：
- 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
- 每个测试用例的第一行包含一个整数n（1≤n≤10^5）——数组的大小。
- 第二行包含n个整数a_1,a_2,…,a_n（1≤a_i≤10^9）——玛莎和奥尔加游戏的数组。
- 保证所有测试用例的n之和不超过10^5。
输出数据格式：
- 对于每个测试用例，输出n个整数。第k个数表示仅考虑数组a的前k个元素时，在双方都进行最优游戏的情况下，最终会剩下的数。
示例：
输入：
```
4
1
31
6
6 3 7 2 5 4
3
3 10 11
5
7 13 11 19 1
```
输出：
```
31
6 8 16 18 22 26
3 12 24
7 20 30 48 50
```题目大意： 玛莎和奥尔加即将参加一场重要的团队奥林匹克比赛。为了热身，玛莎提议和奥尔加玩一个游戏。游戏规则如下： - 有一个长度为n的数组a。 - 玛莎先手，轮流进行。 - 每轮操作如下： - 如果数组长度为1，游戏结束。 - 当前玩家选择两个不同的下标i和j（1≤i,j≤|a|），然后执行以下操作：从数组中移除a_i和a_j，并向数组中添加一个数，该数为 ⌊(a_i + a_j)/2⌋ * 2。换句话说，就是先将a_i和a_j的和除以2并向下取整，然后将结果乘以2。 - 玛莎的目标是最大化最终的结果，而奥尔加的目标是最小化结果。 玛莎和奥尔加决定在数组a的每个非空前缀上进行游戏，并请求你的帮助。 对于每个k=1,2,…,n，回答以下问题：仅考虑数组a的前k个元素，下标分别为1,2,…,k。在双方都进行最优游戏的情况下，最终会剩下什么数？ 输入数据格式： - 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 - 每个测试用例的第一行包含一个整数n（1≤n≤10^5）——数组的大小。 - 第二行包含n个整数a_1,a_2,…,a_n（1≤a_i≤10^9）——玛莎和奥尔加游戏的数组。 - 保证所有测试用例的n之和不超过10^5。 输出数据格式： - 对于每个测试用例，输出n个整数。第k个数表示仅考虑数组a的前k个元素时，在双方都进行最优游戏的情况下，最终会剩下的数。 示例： 输入： ``` 4 1 31 6 6 3 7 2 5 4 3 3 10 11 5 7 13 11 19 1 ``` 输出： ``` 31 6 8 16 18 22 26 3 12 24 7 20 30 48 50 ```