English · Original
Chinese · Translation
Formal · Original
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.
[samples]
## 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.
Arkady 想要给他的唯一一盆花浇水。不幸的是，他有一个为 $n$ 盆花设计的非常差的浇水系统，看起来像一根有 $n$ 个孔的管道。Arkady 只能使用从第一个孔流出的水。
Arkady 可以堵塞某些孔，然后向管道中倒入 $A$ 升水。之后，水将从未被堵塞的孔中按其大小 $s_1, s_2, dots.h, s_n$ 成比例流出。换句话说，如果未被堵塞孔的大小之和为 $S$，且第 $i$ 个孔未被堵塞，则会有 $frac(s_i dot.op A, S)$ 升水从该孔流出。
Arkady 至少需要堵塞多少个孔，才能使至少 $B$ 升水从第一个孔流出？
第一行包含三个整数 $n$, $A$, $B$ ($1 lt.eq n lt.eq 100 thin 000$, $1 lt.eq B lt.eq A lt.eq 10^4$) —— 孔的数量、Arkady 倒入系统的水量，以及他希望从第一个孔流出的水量。
第二行包含 $n$ 个整数 $s_1, s_2, dots.h, s_n$ ($1 lt.eq s_i lt.eq 10^4$) —— 孔的大小。
输出一个整数 —— Arkady 应该堵塞的孔的数量。
在第一个例子中，Arkady 至少需要堵塞一个孔。堵塞后，$frac(10 dot.op 2, 6) approx 3. 333$ 升水将从第一个孔流出，这符合 Arkady 的需求。
在第二个例子中，即使不堵塞任何孔，$frac(80 dot.op 3, 10) = 24$ 升水也会从第一个孔流出，这不小于 $20$。
在第三个例子中，Arkady 必须堵塞除第一个孔外的所有孔，才能使所有水都从第一个孔流出。
## Input
第一行包含三个整数 $n$, $A$, $B$ ($1 lt.eq n lt.eq 100 thin 000$, $1 lt.eq B lt.eq A lt.eq 10^4$) —— 孔的数量、Arkady 倒入系统的水量，以及他希望从第一个孔流出的水量。第二行包含 $n$ 个整数 $s_1, s_2, dots.h, s_n$ ($1 lt.eq s_i lt.eq 10^4$) —— 孔的大小。
## Output
输出一个整数 —— Arkady 应该堵塞的孔的数量。
[samples]
## Note
在第一个例子中，Arkady 至少需要堵塞一个孔。堵塞后，$frac(10 dot.op 2, 6) approx 3. 333$ 升水将从第一个孔流出，这符合 Arkady 的需求。在第二个例子中，即使不堵塞任何孔，$frac(80 dot.op 3, 10) = 24$ 升水也会从第一个孔流出，这不小于 $20$。在第三个例子中，Arkady 必须堵塞除第一个孔外的所有孔，才能使所有水都从第一个孔流出。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of holes.
Let $ A \in \mathbb{R}^+ $ be the total volume of water poured into the pipe.
Let $ B \in \mathbb{R}^+ $ be the minimum desired volume of water from the first hole.
Let $ S = (s_1, s_2, \dots, s_n) $ be a sequence of positive integers representing the sizes of the holes, where $ s_1 $ is the size of the first hole.
Let $ I \subseteq \{1, 2, \dots, n\} $ be the set of non-blocked holes. Define $ S_I = \sum_{i \in I} s_i $ as the total size of non-blocked holes.
The volume of water flowing from the first hole is:
$$
v(I) = \begin{cases}
\frac{s_1}{S_I} \cdot A & \text{if } 1 \in I \\
0 & \text{if } 1 \notin I
\end{cases}
$$
**Constraints**
1. $ 1 \leq n \leq 100{,}000 $
2. $ 1 \leq B \leq A \leq 10^4 $
3. $ 1 \leq s_i \leq 10^4 $ for all $ i \in \{1, \dots, n\} $
4. $ 1 \in I $ (the first hole must remain unblocked to output water)
**Objective**
Find the minimum number of holes to block, i.e., minimize $ n - |I| $, such that:
$$
\frac{s_1 \cdot A}{S_I} \geq B
$$
Equivalently, maximize $ |I| $ (minimize blocking) subject to:
$$
S_I \leq \frac{s_1 \cdot A}{B}
$$
and $ I \subseteq \{1, 2, \dots, n\} $, $ 1 \in I $.
API Response (JSON)
{
"problem": {
"name": "B. Watering System",
"description": {
"content": "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 tha",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF967B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 tha...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Arkady 想要给他的唯一一盆花浇水。不幸的是，他有一个为 $n$ 盆花设计的非常差的浇水系统，看起来像一根有 $n$ 个孔的管道。Arkady 只能使用从第一个孔流出的水。\n\nArkady 可以堵塞某些孔，然后向管道中倒入 $A$ 升水。之后，水将从未被堵塞的孔中按其大小 $s_1, s_2, dots.h, s_n$ 成比例流出。换句话说，如果未被堵塞孔的大小之和为 $S$，且第 $i$ 个...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of holes. \nLet $ A \\in \\mathbb{R}^+ $ be the total volume of water poured into the pipe. \nLet $ B \\in \\mathbb{R}^+ $ be the minimum desired...",
"is_translate": false,
"language": "Formal"
}
]
}