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.