CF967B.Watering System

入门

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Arkady wants to water his only flower. Unfortunately, he has a very poor watering system that was designed for nn flowers and so it looks like a pipe with nn holes. Arkady can only use the water that flows from the first hole.

Arkady can block some of the holes, and then pour AA liters of water into the pipe. After that, the water will flow out from the non-blocked holes proportionally to their sizes s1,s2,…,sns_1, s_2, \ldots, s_n. In other words, if the sum of sizes of non-blocked holes is SS, and the ii-th hole is not blocked, si⋅AS\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 BB liters of water flow out of the first hole?

阿尔卡季想浇灌他唯一的一株花。不幸的是,他只有一个非常简陋的灌溉系统,该系统原本是为 nn 株花设计的,因此其结构是一根带有 nn 个孔的管道。阿尔卡季只能使用从第一个孔流出的水。

阿尔卡季可以封住其中一些孔,然后向管道中注入 AA 升水。随后,水将按各未被封住的孔的尺寸 s1,s2,…,sns_1, s_2, \ldots, s_n 的比例从这些未被封住的孔中流出。换言之,若所有未被封住的孔的尺寸之和为 SS,且第 ii 个孔未被封住,则将有 si⋅AS\frac{s_i \cdot A}{S} 升水从该孔流出。

为了使至少 BB 升水从第一个孔流出,阿尔卡季最少需要封住多少个孔?

输入格式

The first line contains three integers nn, AA, BB (1≤n≤100 0001 \le n \le 100\,000, 1≤B≤A≤1041 \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 nn integers s1,s2,…,sns_1, s_2, \ldots, s_n (1≤si≤1041 \le s_i \le 10^4) — the sizes of the holes.

第一行包含三个整数 nn、AA、BB(1≤n≤100 0001 \le n \le 100\,000,1≤B≤A≤1041 \le B \le A \le 10^4)—— 分别表示洞的数量、Arkady 注入系统的水量,以及他希望从第一个洞流出的水量。

第二行包含 nn 个整数 s1,s2,…,sns_1, s_2, \ldots, s_n(1≤si≤1041 \le s_i \le 10^4)—— 表示各个洞的尺寸。

输出格式

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

输出一个整数——Arkady 需要封堵的洞的数量。

输入输出样例

  • 输入#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, 10⋅26≈3.333\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, 80⋅310=24\frac{80 \cdot 3}{10} = 24 liters will flow out of the first hole, that is not less than 2020.

In the third example Arkady has to block all holes except the first to make all water flow out of the first hole.

在第一个例子中,阿尔卡季至少需要堵住一个洞。此后,将有 10⋅26≈3.333\frac{10 \cdot 2}{6} \approx 3.333 升水从第一个洞流出,这满足阿尔卡季的要求。

在第二个例子中,即使不堵住任何洞,也将有 80⋅310=24\frac{80 \cdot 3}{10} = 24 升水从第一个洞流出,该值不小于 2020。

在第三个例子中,阿尔卡季必须堵住除第一个洞外的所有洞,以使全部水流都从第一个洞流出。

输入解题思路,AI测评打分。不知道怎么写?

首页