305110: CF967B. Watering System

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Watering System

题意翻译

有n个洞,每个洞有一个s值,记没有被堵上的洞总的s值为sum,问你至少填几个洞能使a*s1/sum>=b

题目描述

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?

输入输出格式

输入格式


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.

输出格式


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

输入输出样例

输入样例 #1

4 10 3
2 2 2 2

输出样例 #1

1

输入样例 #2

4 80 20
3 2 1 4

输出样例 #2

0

输入样例 #3

5 10 10
1000 1 1 1 1

输出样例 #3

4

说明

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.

Input

题意翻译

有n个洞,每个洞有一个s值,记没有被堵上的洞总的s值为sum,问你至少填几个洞能使a*s1/sum>=b

加入题单

上一题 下一题 算法标签: