1237A.md (2213B)
1 Source: https://codeforces.com/problemset/problem/1237/A 2 3 A. Balanced Rating Changes 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Another Codeforces Round has just finished! It has gathered $n$ participants, and according to the results, the expected rating change of participant $i$ is $a_i$. These rating changes are perfectly balanced — their sum is equal to $0$. 22 23 Unfortunately, due to minor technical glitches, the round is declared semi-rated. It means that all rating changes must be divided by two. 24 25 There are two conditions though: 26 27 * For each participant $i$, their modified rating change $b_i$ must be integer, and as close to $\frac{a_i}{2}$ as possible. It means that either $b_i = \lfloor \frac{a_i}{2} \rfloor$ or $b_i = \lceil \frac{a_i}{2} \rceil$. In particular, if $a_i$ is even, $b_i = \frac{a_i}{2}$. Here $\lfloor x \rfloor$ denotes rounding down to the largest integer not greater than $x$, and $\lceil x \rceil$ denotes rounding up to the smallest integer not smaller than $x$. 28 * The modified rating changes must be perfectly balanced — their sum must be equal to $0$. 29 30 Can you help with that? 31 32 Input 33 34 The first line contains a single integer $n$ ($2 \le n \le 13\,845$), denoting the number of participants. 35 36 Each of the next $n$ lines contains a single integer $a_i$ ($-336 \le a_i \le 1164$), denoting the rating change of the $i$-th participant. 37 38 The sum of all $a_i$ is equal to $0$. 39 40 Output 41 42 Output $n$ integers $b_i$, each denoting the modified rating change of the $i$-th participant in order of input. 43 44 For any $i$, it must be true that either $b_i = \lfloor \frac{a_i}{2} \rfloor$ or $b_i = \lceil \frac{a_i}{2} \rceil$. The sum of all $b_i$ must be equal to $0$. 45 46 If there are multiple solutions, print any. We can show that a solution exists for any valid input. 47 48 Examples 49 50 Input 51 52 ``` 53 3 54 10 55 -5 56 -5 57 ``` 58 59 Output 60 61 ``` 62 5 63 -2 64 -3 65 ``` 66 67 Input 68 69 ``` 70 7 71 -7 72 -29 73 0 74 3 75 24 76 -29 77 38 78 ``` 79 80 Output 81 82 ``` 83 -3 84 -15 85 0 86 2 87 12 88 -15 89 19 90 ``` 91 92 Note 93 94 In the first example, $b_1 = 5$, $b_2 = -3$ and $b_3 = -2$ is another correct solution. 95 96 In the second example there are $6$ possible solutions, one of them is shown in the example output.