100633: [AtCoder]ABC063 D - Widespread

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

Description

Score : $400$ points

Problem Statement

You are going out for a walk, when you suddenly encounter $N$ monsters. Each monster has a parameter called health, and the health of the $i$-th monster is $h_i$ at the moment of encounter. A monster will vanish immediately when its health drops to $0$ or below.

Fortunately, you are a skilled magician, capable of causing explosions that damage monsters. In one explosion, you can damage monsters as follows:

  • Select an alive monster, and cause an explosion centered at that monster. The health of the monster at the center of the explosion will decrease by $A$, and the health of each of the other monsters will decrease by $B$. Here, $A$ and $B$ are predetermined parameters, and $A > B$ holds.

At least how many explosions do you need to cause in order to vanish all the monsters?

Constraints

  • All input values are integers.
  • $1 ≤ N ≤ 10^5$
  • $1 ≤ B < A ≤ 10^9$
  • $1 ≤ h_i ≤ 10^9$

Input

Input is given from Standard Input in the following format:

$N$ $A$ $B$
$h_1$
$h_2$
$:$
$h_N$

Output

Print the minimum number of explosions that needs to be caused in order to vanish all the monsters.


Sample Input 1

4 5 3
8
7
4
2

Sample Output 1

2

You can vanish all the monsters in two explosion, as follows:

  • First, cause an explosion centered at the monster with $8$ health. The healths of the four monsters become $3$, $4$, $1$ and $-1$, respectively, and the last monster vanishes.
  • Second, cause an explosion centered at the monster with $4$ health remaining. The healths of the three remaining monsters become $0$, $-1$ and $-2$, respectively, and all the monsters are now vanished.

Sample Input 2

2 10 4
20
20

Sample Output 2

4

You need to cause two explosions centered at each monster, for a total of four.


Sample Input 3

5 2 1
900000000
900000000
1000000000
1000000000
1000000000

Sample Output 3

800000000

Input

题意翻译

你散步的时候,突然$N$个魔物出现了。 各个魔物都有体力这个值,第$i$个魔物出现时的体力是$h_i$,而体力$0$以下的魔物立即消失。 幸运的是,你是一个熟练的魔法师,可以发动爆炸来攻击魔物。一次爆炸可以减少魔物的体力,如下所示。 选择生存的魔物,以魔物为中心引起爆炸。成为爆炸中心的魔物的体力$A$减少,其他魔物的体力$B$分别减少。 这里需要说明的是,$A$和$B$是预先确定的值,且$A>B$。 为了消灭所有的魔物,你最少需要引起几次爆炸呢?

加入题单

上一题 下一题 算法标签: