Training Before the Olympiad (Codeforces 1916C)
Tags: Greedy, games

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?

Input: The 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$$$.

Output: For 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$$$.

Note: 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$$$.

Sample Inputs:
4
1
31
6
6 3 7 2 5 4
3
3 10 11
5
7 13 11 19 1

Sample Outputs:
31 
6 8 16 18 22 26 
3 12 24 
7 20 30 48 50

Solution (Python):
import sys
''

def read(func=int):
    return func(sys.stdin.readline().strip())

def read_array(func=int):
    return list(map(func, read(str).split()))

def binary_search(arr, x):
    """"""
    (i, j) = (0, len(arr) - 1)
    ans = -1
    while i <= j:
        mid = i + (j - i) // 2
        xmd = arr[mid]
        if xmd <= x:
            ans = mid
            i = mid + 1
        else:
            j = mid - 1
    return ans

def gcd(a, b):
    """"""
    if not b:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    """"""
    return a / gcd(a, b) * b

def solve():
    n = read()
    A = read_array()
    cnt = 0
    S = 0
    ans = []
    for (ai, i) in zip(A, range(n)):
        cnt += ai % 2
        S += ai
        if cnt % 3 == 0 or cnt % 3 == 2:
            ans.append(S - cnt // 3)
        elif cnt % 3 == 1:
            if not i:
                ans.append(S)
            else:
                ans.append(S - cnt // 3 - 1)
    print(' '.join(map(str, ans)))
t = read()
for _ in range(t):
    solve()

Solution (Python):
import sys
from math import gcd

def solve():
    inp = sys.stdin.readline
    n = int(inp())
    s = 0
    even = 0
    odd = 0
    res = []
    for i in map(int, inp().split()):
        s += i
        if i % 2 == 0:
            even += 1
        else:
            odd += 1
        while odd >= 3:
            s -= 1
            odd -= 3
            even += 1
        if odd == 2:
            res.append(s)
        elif odd == 1:
            if even == 0:
                res.append(s)
            else:
                res.append(s - 1)
        else:
            res.append(s)
    print(' '.join(map(str, res)))

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import sys
ri = lambda : int(sys.stdin.readline())
rl = lambda : list(map(int, sys.stdin.readline().split()))
rs = lambda : sys.stdin.readline()

def solve(n, a):
    (E, U) = (0, 0)
    s = 0
    out = []
    for i in range(n):
        x = a[i]
        if x % 2 == 0:
            E += 1
        else:
            U += 1
        s += x
        (e, u) = (E, U)
        pen = 0
        if u > 1:
            e += 1
            u -= 2
        elif u == 1:
            if e > 0:
                pen += 1
                u -= 1
        if u == 0:
            pass
        elif u == 1:
            if e > 0:
                pen += 1
        else:
            pen += 1 + (u - 1) // 3
            if (u - 1) % 3 == 1:
                pen += 1
        out.append(s - pen)
    return ' '.join((str(x) for x in out))
t = ri()
for _ in range(t):
    n = ri()
    a = rl()
    print(solve(n, a))