Unfair Game
Contest: Codeforces Round 938 (Div. 3)
Difficulty rating: 1800
Tags: dp, games, greedy, math, schedules

Alice and Bob gathered in the evening to play an exciting game on a sequence of $$$n$$$ integers, each integer of the sequence doesn't exceed $$$4$$$. The rules of the game are too complex to describe, so let's just describe the winning condition — Alice wins if the bitwise XOR of all the numbers in the sequence is non-zero; otherwise, Bob wins.

The guys invited Eve to act as a judge. Initially, Alice and Bob play with $$$n$$$ numbers. After one game, Eve removes one of the numbers from the sequence, then Alice and Bob play with $$$n-1$$$ numbers. Eve removes one number again, after which Alice and Bob play with $$$n - 2$$$ numbers. This continues until the sequence of numbers is empty.

Eve seems to think that in such a game, Alice almost always wins, so she wants Bob to win as many times as possible. Determine the maximum number of times Bob can win against Alice if Eve removes the numbers optimally.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first and only line of each test case contains four integers $$$p_i$$$ ($$$0 \le p_i \le 200$$$) — the number of ones, twos, threes, and fours in the sequence at the beginning of the game.

Output format:
For each test case, print the maximum number of times Bob will win in a separate line, if Eve removes the numbers optimally.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, Bob wins when Eve has not removed any numbers yet.

In the second example, Bob wins if Eve removes one one and one three.

Example input:
5
1 1 1 0
1 0 1 2
2 2 2 0
3 3 2 0
0 9 9 9

Example output:
1
1
3
3
12

Editorial:
Let's try to solve the problem if all the numbers in the sequence are equal to $$$4$$$. If the number of elements is even, the bitwise XOR is zero, and if it's odd, then it's equal to $$$4$$$. By removing one $$$4$$$ at a time, Eve will change the parity, so the answer will be $$$\lfloor {p_4 \over 2} \rfloor$$$.
Suppose there are some other numbers in the sequence besides $$$4$$$. For Bob to win, the number of $$$4$$$s still needs to be even. Therefore, we can solve the problem for the remaining numbers separately from the fours.
One of the solutions uses dynamic programming. Let's denote $$$dp_{i,j,k}$$$ as the maximum number of Bob's wins, if there were initially $$$i$$$ ones, $$$j$$$ twos, and $$$k$$$ threes. Since an empty sequence is not considered in the answer, then $$$dp_{0,0,0} = 0$$$. We will iterate over which number to remove, and get the following transitions: $$$dp_{i,j,k} = \max(dp_{i - 1,j,k}, dp_{i,j - 1,k}, dp_{i,j,k - 1}) + x(i,j,k)$$$. Here, $$$x(i,j,k) = 1$$$ if the bitwise XOR of $$$i$$$ ones, $$$j$$$ twos, and $$$k$$$ threes is zero, and $$$x(i,j,k) = 0$$$ otherwise. The complexity of calculating these values is $$$O(N ^ 3)$$$, where $$$N = 200$$$.
Another solution is analytical. Bob wins in two cases: if the number of ones, twos, and threes is even; if the number of ones, twos, and threes is odd. In the first case, the bitwise XOR is zero, because each number occurs an even number of times, and in the second case, $$$1 \oplus 2 \oplus 3 = 0$$$.
To maintain the parities, Eve needs to remove the same number, so with two removals, Bob will win once. If the second condition is not initially met, it is always more advantageous to remove numbers to reach the first case, then the answer is $$$\sum^{3}_{i = 1} \lfloor{cnt_i \over 2}\rfloor$$$. If the second condition is already met, then $$$1$$$ needs to be added to the answer.