2092C.md (2416B)
1 Source: https://codeforces.com/problemset/problem/2092/C 2 3 C. Asuna and the Mosquitoes 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 For her birthday, each of Asuna's $n$ admirers gifted her a tower. The height of the tower from the $i$-th admirer is equal to $a_i$. 22 23 Asuna evaluates the beauty of the received gifts as $\max(a_1, a_2, \ldots, a_n)$. She can perform the following operation an arbitrary number of times (possibly, zero). 24 25 * Take such $1 \le i \neq j \le n$ that $a_i + a_j$ is odd and $a_i \gt 0$, then decrease $a_i$ by $1$ and increase $a_j$ by $1$. 26 27 It is easy to see that the heights of the towers remain non-negative during the operations. 28 29 Help Asuna find the maximum possible beauty of the gifts after any number of operations! 30 31 Input 32 33 Each test consists of several test cases. The first line of the input data contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows. 34 35 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of admirers of Asuna. 36 37 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n \ (1 \le a_i \le 10^9)$ — the heights of the towers. 38 39 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, output a single integer: the maximum value of the beauty of the gifts that Asuna can achieve. 44 45 Example 46 47 Input 48 49 ``` 50 4 51 52 3 53 54 5 3 9 55 56 2 57 58 3 2 59 60 4 61 62 1 2 2 1 63 64 5 65 66 5 4 3 2 9 67 ``` 68 69 Output 70 71 ``` 72 9 73 5 74 5 75 21 76 ``` 77 78 Note 79 80 In the first test case, no pair of towers satisfies the required condition for applying the operation, so no operations can be performed. In this case, the answer is $\max(5, \ 3, \ 9) = 9$. 81 82 In the second test case, the operation with $i = 2$ and $j = 1$ can be applied twice. After that, the array becomes: $a \ = \ [5, \ 0]$. Thus, the answer is 5. 83 84 In the third test case, the following sequence of operations can be applied: 85 86 1. Operation with $i=1$ and $j=2$. 87 88 $[1, \ 2, \ 2, \ 1] \quad \rightarrow \quad [0, \ 3, \ 2, \ 1]$ 89 2. Operation with $i=3$ and $j=2$. 90 91 $[0, \ 3, \ 2, \ 1] \quad \rightarrow \quad [0, \ 4, \ 1, \ 1]$ 92 3. Operation with $i=3$ and $j=2$. 93 94 $[0, \ 4, \ 1, \ 1] \quad \rightarrow \quad [0, \ 5, \ 0, \ 1]$ 95 96 $\max(0, \ 5, \ 0, \ 1) \ = \ 5$. 97 98 Therefore, the answer is 5.