← 返回题目列表

AtCoder · arc075_b

D. 广泛传播

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

你正在出去散步,突然遇到 N 怪物。每个怪物都有一个参数称为 健康,以及健康 i- 第一个怪物是 h_i 相遇的那一刻。当怪物的生命值下降到以下时,怪物会立即消失 0 或以下。

幸运的是,你是一位熟练的魔法师,能够引起爆炸来伤害怪物。在一次爆炸中,你可以对怪物造成如下伤害:

  • 选择一只活着的怪物,并以该怪物为中心引发爆炸。爆炸中心怪物的生命值将减少 A,其他每个怪物的生命值都会减少 B。在这里, A 和 B 是预定参数,并且 A > B 成立。

你至少需要引起多少次爆炸才能消灭所有怪物?

约束

  • 所有输入值均为整数。
  • 1 ≤ N ≤ 10^5
  • 1 ≤ B < A ≤ 10^9
  • 1 ≤ h_i ≤ 10^9

输入

输入由标准输入按以下格式给出:

N A B
h_1
h_2
:
h_N

输出

打印消灭所有怪物所需的最小爆炸次数。


示例输入 1

4 5 3
8
7
4
2

示例输出 1

2

你可以在两次爆炸中消灭所有怪物,如下:

  • 首先,以怪物为中心引发爆炸 8 健康。四个怪物的生命值变为 3, 4, 1 和 -1,最后一个怪物消失。
  • 其次,以怪物为中心引发爆炸 4 剩余健康状况。剩下的三个怪物的生命值变为 0, -1 和 -2,所有怪物现在都消失了。

示例输入 2

2 10 4
20
20

示例输出 2

4

你需要以每个怪物为中心引发两次爆炸,总共四次。


示例输入 3

5 2 1
900000000
900000000
1000000000
1000000000
1000000000

示例输出 3

800000000