{"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 that flows from the first hole.\n\nArkady 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.\n\nWhat is the minimum number of holes Arkady should block to make at least $B$ liters of water flow out of the first hole?\n\n## Input\n\nThe 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.\n\nThe second line contains $n$ integers $s_1, s_2, \\ldots, s_n$ ($1 \\le s_i \\le 10^4$) — the sizes of the holes.\n\n## Output\n\nPrint a single integer — the number of holes Arkady should block.\n\n[samples]\n\n## Note\n\nIn 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.\n\nIn 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$.\n\nIn the third example Arkady has to block all holes except the first to make all water flow out of the first hole.","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$ 个孔未被堵塞，则会有 $frac(s_i dot.op A, S)$ 升水从该孔流出。\n\nArkady 至少需要堵塞多少个孔，才能使至少 $B$ 升水从第一个孔流出？\n\n第一行包含三个整数 $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\n第二行包含 $n$ 个整数 $s_1, s_2, dots.h, s_n$ ($1 lt.eq s_i lt.eq 10^4$) —— 孔的大小。\n\n输出一个整数 —— Arkady 应该堵塞的孔的数量。\n\n在第一个例子中，Arkady 至少需要堵塞一个孔。堵塞后，$frac(10 dot.op 2, 6) approx 3. 333$ 升水将从第一个孔流出，这符合 Arkady 的需求。\n\n在第二个例子中，即使不堵塞任何孔，$frac(80 dot.op 3, 10) = 24$ 升水也会从第一个孔流出，这不小于 $20$。\n\n在第三个例子中，Arkady 必须堵塞除第一个孔外的所有孔，才能使所有水都从第一个孔流出。\n\n## Input\n\n第一行包含三个整数 $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$) —— 孔的大小。\n\n## Output\n\n输出一个整数 —— Arkady 应该堵塞的孔的数量。\n\n[samples]\n\n## Note\n\n在第一个例子中，Arkady 至少需要堵塞一个孔。堵塞后，$frac(10 dot.op 2, 6) approx 3. 333$ 升水将从第一个孔流出，这符合 Arkady 的需求。在第二个例子中，即使不堵塞任何孔，$frac(80 dot.op 3, 10) = 24$ 升水也会从第一个孔流出，这不小于 $20$。在第三个例子中，Arkady 必须堵塞除第一个孔外的所有孔，才能使所有水都从第一个孔流出。","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 volume of water from the first hole.  \nLet $ 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.\n\nLet $ 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.\n\nThe volume of water flowing from the first hole is:  \n$$\nv(I) = \\begin{cases}\n\\frac{s_1}{S_I} \\cdot A & \\text{if } 1 \\in I \\\\\n0 & \\text{if } 1 \\notin I\n\\end{cases}\n$$\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 100{,}000 $  \n2. $ 1 \\leq B \\leq A \\leq 10^4 $  \n3. $ 1 \\leq s_i \\leq 10^4 $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. $ 1 \\in I $ (the first hole must remain unblocked to output water)  \n\n**Objective**  \nFind the minimum number of holes to block, i.e., minimize $ n - |I| $, such that:  \n$$\n\\frac{s_1 \\cdot A}{S_I} \\geq B\n$$  \nEquivalently, maximize $ |I| $ (minimize blocking) subject to:  \n$$\nS_I \\leq \\frac{s_1 \\cdot A}{B}\n$$  \nand $ I \\subseteq \\{1, 2, \\dots, n\\} $, $ 1 \\in I $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF967B","tags":["math","sortings"],"sample_group":[["4 10 3\n2 2 2 2","1"],["4 80 20\n3 2 1 4","0"],["5 10 10\n1000 1 1 1 1","4"]],"created_at":"2026-03-03 11:00:39"}}