18463번 - Farm of Monsters 다국어

There are n monsters, and the i-th monster initially has h_i health points.

Let’s call a monster alive if his HP is strictly greater than zero.

You have an attack power of a, and your opponent has an attack power of b.

As long as one monster is still alive, you and your opponent take turns fighting monsters (beginning with you).

You are very smart, so on your turn, you can attack any monster that is alive or do nothing. If you choose to attack some monster i, the monster’s health, h_i, will decrease by exactly a.

After your attack, if the monster is dead (not alive), you gain one victory point.

Your opponent, on the other hand, is not so smart. During his turn, he finds the monster with the smallest index that is alive and attacks it (i.e. he finds the smallest i such that h_i > 0 and decreases h_i exactly by b).

What is the greatest number of victory points that you can obtain?

The first line contains three integers n, a, b (1 ≤ n ≤ 300 000, 1 ≤ a, b ≤ 10⁹): the number of monsters and the attack powers of you and your opponent, respectively.

The second line contains n integers h₁, h₂, . . . , h_n (1 ≤ h_i ≤ 10⁹): the health points of the monsters.

Print one integer: the largest number of victory points that you can obtain.

In the first example, on your first turn, you can kill the third monster, and on your second turn, you can kill the second monster.

In the second example, you can wait until the leftmost monster will have hi = 1, and then kill it yourself.