AtCoder Beginner Contest 063
翻译中…
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.
翻译中…
样例
Input #1
4 5 3
8
7
4
2
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.
Input #2
2 10 4
20
20
Output #2
4
You need to cause two explosions centered at each monster, for a total of four.
Input #3
5 2 1
900000000
900000000
1000000000
1000000000
1000000000
Output #3
800000000
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。