Watering System (Codeforces 967B)
Tags: Math, sortings

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.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.What is the minimum number of holes Arkady should block to make at least $$$B$$$ liters of water flow out of the first hole?

Input: 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.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.

Output: Print a single integer — the number of holes Arkady should block.

Note: 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.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$$$.In the third example Arkady has to block all holes except the first to make all water flow out of the first hole.

Sample Inputs:
4 10 3
2 2 2 2

4 80 20
3 2 1 4

5 10 10
1000 1 1 1 1

Sample Outputs:
1

0

4

Solution (Python):
from itertools import accumulate
from bisect import bisect_left, bisect_right
(n, a, b) = (int(i) for i in input().split())
s = (int(i) for i in input().split())
(x, s) = (next(s), list(accumulate(sorted(s))))
z = a * x / b - x
res = len(s) - bisect_right(s, z)
print(res)

Solution (Python):
(n, a, b, t, *m) = map(int, open(0).read().split())
s = t * a / b - t
ans = n - 1
for x in sorted(m):
    s -= x
    if s < 0:
        break
    ans -= 1
print(ans)

Solution (Python):
def watering():
    (n, a, b) = map(int, input().split())
    s = list(map(int, input().split()))
    volume = s[0] * (a / b - 1)
    rest_holes_sum = sum(s[1:])
    k = 0
    delta = volume - rest_holes_sum
    s_rest = sorted(s[1:], reverse=True)
    while delta < 0:
        delta += s_rest[k]
        k += 1
    print(k)
watering()