codeforces-scrape

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

257A.md (2570B)


      1 Source: https://codeforces.com/problemset/problem/257/A
      2 
      3 A. Sockets
      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 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Vasya has got many devices that work on electricity. He's got *n* supply-line filters to plug the devices, the *i*-th supply-line filter has *a**i* sockets.
     22 
     23 Overall Vasya has got *m* devices and *k* electrical sockets in his flat, he can plug the devices or supply-line filters directly. Of course, he can plug the supply-line filter to any other supply-line filter. The device (or the supply-line filter) is considered plugged to electricity if it is either plugged to one of *k* electrical sockets, or if it is plugged to some supply-line filter that is in turn plugged to electricity.
     24 
     25 What minimum number of supply-line filters from the given set will Vasya need to plug all the devices he has to electricity? Note that all devices and supply-line filters take one socket for plugging and that he can use one socket to plug either one device or one supply-line filter.
     26 
     27 Input
     28 
     29 The first line contains three integers *n*, *m*, *k* (1 ≤ *n*, *m*, *k* ≤ 50) — the number of supply-line filters, the number of devices and the number of sockets that he can plug to directly, correspondingly. The second line contains *n* space-separated integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 50) — number *a**i* stands for the number of sockets on the *i*-th supply-line filter.
     30 
     31 Output
     32 
     33 Print a single number — the minimum number of supply-line filters that is needed to plug all the devices to electricity. If it is impossible to plug all the devices even using all the supply-line filters, print -1.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 3 5 3  
     41 3 1 2
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 1
     48 ```
     49 
     50 Input
     51 
     52 ```
     53 4 7 2  
     54 3 3 2 4
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 2
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 5 5 1  
     67 1 3 1 2 1
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 -1
     74 ```
     75 
     76 Note
     77 
     78 In the first test case he can plug the first supply-line filter directly to electricity. After he plug it, he get 5 (3 on the supply-line filter and 2 remaining sockets for direct plugging) available sockets to plug. Thus, one filter is enough to plug 5 devices.
     79 
     80 One of the optimal ways in the second test sample is to plug the second supply-line filter directly and plug the fourth supply-line filter to one of the sockets in the second supply-line filter. Thus, he gets exactly 7 sockets, available to plug: one to plug to the electricity directly, 2 on the second supply-line filter, 4 on the fourth supply-line filter. There's no way he can plug 7 devices if he use one supply-line filter.