808C.md (1866B)
1 Source: https://codeforces.com/problemset/problem/808/C 2 3 C. Tea Party 4 5 time limit per test 6 7 1 second 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 Polycarp invited all his friends to the tea party to celebrate the holiday. He has *n* cups, one for each of his *n* friends, with volumes *a*1, *a*2, ..., *a**n*. His teapot stores *w* milliliters of tea (*w* ≤ *a*1 + *a*2 + ... + *a**n*). Polycarp wants to pour tea in cups in such a way that: 22 23 * Every cup will contain tea for at least half of its volume 24 * Every cup will contain integer number of milliliters of tea 25 * All the tea from the teapot will be poured into cups 26 * All friends will be satisfied. 27 28 Friend with cup *i* won't be satisfied, if there exists such cup *j* that cup *i* contains less tea than cup *j* but *a**i* > *a**j*. 29 30 For each cup output how many milliliters of tea should be poured in it. If it's impossible to pour all the tea and satisfy all conditions then output -1. 31 32 Input 33 34 The first line contains two integer numbers *n* and *w* (1 ≤ *n* ≤ 100, ). 35 36 The second line contains *n* numbers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 100). 37 38 Output 39 40 Output how many milliliters of tea every cup should contain. If there are multiple answers, print any of them. 41 42 If it's impossible to pour all the tea and satisfy all conditions then output -1. 43 44 Examples 45 46 Input 47 48 ``` 49 2 10 50 8 7 51 ``` 52 53 Output 54 55 ``` 56 6 4 57 ``` 58 59 Input 60 61 ``` 62 4 4 63 1 1 1 1 64 ``` 65 66 Output 67 68 ``` 69 1 1 1 1 70 ``` 71 72 Input 73 74 ``` 75 3 10 76 9 8 10 77 ``` 78 79 Output 80 81 ``` 82 -1 83 ``` 84 85 Note 86 87 In the third example you should pour to the first cup at least 5 milliliters, to the second one at least 4, to the third one at least 5. It sums up to 14, which is greater than 10 milliliters available.