codeforces-scrape

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

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, ![](https://espresso.codeforces.com/e5d84551489cb4fc0bb3ccad99a9b61ed555797d.png)).
     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.