codeforces-scrape

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

967B.md (1978B)


      1 Source: https://codeforces.com/problemset/problem/967/B
      2 
      3 B. Watering System
      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 Arkady wants to water his only flower. Unfortunately, he has a very poor watering system that was designed for $n$ flowers and so it looks like a pipe with $n$ holes. Arkady can only use the water that flows from the first hole.
     22 
     23 Arkady can block some of the holes, and then pour $A$ liters of water into the pipe. After that, the water will flow out from the non-blocked holes proportionally to their sizes $s_1, s_2, \ldots, s_n$. In other words, if the sum of sizes of non-blocked holes is $S$, and the $i$-th hole is not blocked, $\frac{s_i \cdot A}{S}$ liters of water will flow out of it.
     24 
     25 What is the minimum number of holes Arkady should block to make at least $B$ liters of water flow out of the first hole?
     26 
     27 Input
     28 
     29 The first line contains three integers $n$, $A$, $B$ ($1 \le n \le 100\,000$, $1 \le B \le A \le 10^4$) — the number of holes, the volume of water Arkady will pour into the system, and the volume he wants to get out of the first hole.
     30 
     31 The second line contains $n$ integers $s_1, s_2, \ldots, s_n$ ($1 \le s_i \le 10^4$) — the sizes of the holes.
     32 
     33 Output
     34 
     35 Print a single integer — the number of holes Arkady should block.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 4 10 3  
     43 2 2 2 2
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 1
     50 ```
     51 
     52 Input
     53 
     54 ```
     55 4 80 20  
     56 3 2 1 4
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 0
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 5 10 10  
     69 1000 1 1 1 1
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 4
     76 ```
     77 
     78 Note
     79 
     80 In the first example Arkady should block at least one hole. After that, $\frac{10 \cdot 2}{6} \approx 3.333$ liters of water will flow out of the first hole, and that suits Arkady.
     81 
     82 In the second example even without blocking any hole, $\frac{80 \cdot 3}{10} = 24$ liters will flow out of the first hole, that is not less than $20$.
     83 
     84 In the third example Arkady has to block all holes except the first to make all water flow out of the first hole.