codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.