codeforces-scrape

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

2176C.md (3471B)


      1 Source: https://codeforces.com/problemset/problem/2176/C
      2 
      3 C. Odd Process
      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 You have $n$ coins with denominations $a_1, a_2, \ldots, a_n$ and a natural number $k$. You also have a bag, which is initially empty, where you can place coins. You need to perform exactly $k$ actions. In each action, you take one coin from those you have left and put it in your bag. After that, you can no longer take that coin.
     22 
     23 At the same time, you have a cat that loves even numbers, so every time the sum of the denominations of the coins in your bag becomes even, your cat empties the bag, meaning it takes all the coins to a place known only to it, and the bag is empty again. Note that the bag is emptied every time the sum becomes even during the process of adding coins, not just at the very last moment.
     24 
     25 Let your score be the sum of the denominations of the coins in the bag. Your task is to perform $k$ actions such that your final score is maximized. Find the answer for all $1 \le k \le n$.
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     30 
     31 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of coins you have.
     32 
     33 The second line of each test case contains $n$ natural numbers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the denominations of the coins.
     34 
     35 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case, output $n$ numbers — the maximum possible score that can be achieved by performing exactly $k$ actions for all $k$ from $1$ to $n$.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 6
     47 
     48 3
     49 
     50 1 1 1
     51 
     52 3
     53 
     54 1 2 3
     55 
     56 5
     57 
     58 4 1 3 1 2
     59 
     60 5
     61 
     62 4 2 3 1 3
     63 
     64 3
     65 
     66 4 1 2
     67 
     68 3
     69 
     70 4 2 2
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 1 0 1
     77 
     78 3 5 0
     79 
     80 3 7 9 7 9
     81 
     82 3 7 9 7 9
     83 
     84 1 5 7
     85 
     86 0 0 0
     87 ```
     88 
     89 Note
     90 
     91 In the first set of input data, you have coins with denominations [$1,1,1$].
     92 
     93 * $k=1$: in this case, the sum of the denominations in the bag is $1$, regardless of the chosen coin. The final score is also $1$.
     94 * $k=2$: in this case, the sum of the denominations in the bag is initially $1$, regardless of the choice of coin. When choosing the second coin, the sum will be $2$, regardless of the choice of coin, and thus the bag will be emptied. The final score is $0$.
     95 * $k=3$: in this case, when choosing the first two coins, the sum will be $2$ and the bag will be emptied, after which the sum will be $0$. When choosing the third coin, the sum will become $1$.
     96 
     97 In the second set of input data, you have coins with denominations [$1,2,3$].
     98 
     99 * $k=1$: in this case, when choosing the coin with denomination $2$, the bag will be emptied and the final score will be $0$. When choosing the coin with denomination $1$ or $3$, the final scores will be $1$ and $3$, respectively. The maximum possible final score is $3$.
    100 * $k=2$: in this case, when choosing two coins $1$ and $3$ in any order, their sum will be $4$, after which the bag will be emptied and the final score will be $0$. However, when choosing $3$ as the first coin, the score will be $3$. Then you can choose, for example, coin $2$, and the final score will become $5$.
    101 * $k=3$: in this case, the sum of all coins will be $6$, and since each time the bag is emptied it does not change the parity of the accumulated sum, the final score is $0$.