A - Intercept the Spaceship Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は宇宙防衛軍の司令官として、地球から遠ざかる敵の宇宙船を迎撃するミッションを指揮しています。

宇宙空間に一直線の航路があり、地球は座標 0 の位置にあります。敵の宇宙船は座標 D の位置におり、地球から遠ざかる方向（座標が増加する方向）に一定の速度 V で逃走を開始しました。

高橋君は N 機の迎撃ミサイルを発射準備しています。 i 番目のミサイルは速度 S_i で飛行することができます。ミサイルは敵の宇宙船と同じ方向（座標が増加する方向）にのみ飛行でき、時刻 0 に座標 0 から発射されます。

高橋君は、敵の宇宙船に到達できるミサイルを把握する必要があります。ミサイルが敵の宇宙船に到達するとは、ある時刻 t \geq 0 においてミサイルの座標が敵の宇宙船の座標以上になることを意味します。

N 機のミサイルのうち、敵の宇宙船に到達できるミサイルの数を求めてください。

制約

  • 1 \leq N \leq 10^6
  • 1 \leq D \leq 10^9
  • 1 \leq V \leq 10^9
  • 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数

入力

N D V
S_1 S_2 \ldots S_N
  • 1 行目には、ミサイルの数を表す N 、敵の宇宙船の初期位置を表す D 、敵の宇宙船の速度を表す V が、スペース区切りで与えられる。
  • 2 行目には、各ミサイルの速度を表す S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。

出力

敵の宇宙船に到達できるミサイルの数を 1 行で出力してください。

入力例 1

5 10 3
2 3 4 5 10

出力例 1

3

入力例 2

4 7 5
1 5 4 2

出力例 2

0

入力例 3

12 100 20
5 20 21 19 100 1 25 20 30 18 22 40

出力例 3

6

入力例 4

30 123456789 500000000
499999999 500000000 500000001 600000000 700000000 1 999999999 250000000 800000000 450000000 510000000 490000000 520000000 530000000 540000000 550000000 560000000 570000000 580000000 590000000 400000000 300000000 200000000 100000000 750000000 650000000 350000000 150000000 900000000 1000000000

出力例 4

18

入力例 5

1 1000000000 1000000000
1000000000

出力例 5

0

Score : 200 pts

Problem Statement

Takahashi is commanding a mission as the commander of the Space Defense Force to intercept an enemy spaceship that is moving away from Earth.

There is a straight route in outer space, and Earth is located at coordinate 0. The enemy spaceship is at coordinate D and has begun fleeing at a constant speed V in the direction away from Earth (the direction of increasing coordinates).

Takahashi is preparing to launch N interceptor missiles. The i-th missile can fly at speed S_i. Missiles can only fly in the same direction as the enemy spaceship (the direction of increasing coordinates), and are launched from coordinate 0 at time 0.

Takahashi needs to determine which missiles can reach the enemy spaceship. A missile reaching the enemy spaceship means that at some time t \geq 0, the missile's coordinate becomes greater than or equal to the enemy spaceship's coordinate.

Find the number of missiles among the N missiles that can reach the enemy spaceship.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq D \leq 10^9
  • 1 \leq V \leq 10^9
  • 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • All inputs are integers

Input

N D V
S_1 S_2 \ldots S_N
  • The first line contains N representing the number of missiles, D representing the initial position of the enemy spaceship, and V representing the speed of the enemy spaceship, separated by spaces.
  • The second line contains S_1, S_2, \ldots, S_N representing the speeds of each missile, separated by spaces.

Output

Output the number of missiles that can reach the enemy spaceship in one line.

Sample Input 1

5 10 3
2 3 4 5 10

Sample Output 1

3

Sample Input 2

4 7 5
1 5 4 2

Sample Output 2

0

Sample Input 3

12 100 20
5 20 21 19 100 1 25 20 30 18 22 40

Sample Output 3

6

Sample Input 4

30 123456789 500000000
499999999 500000000 500000001 600000000 700000000 1 999999999 250000000 800000000 450000000 510000000 490000000 520000000 530000000 540000000 550000000 560000000 570000000 580000000 590000000 400000000 300000000 200000000 100000000 750000000 650000000 350000000 150000000 900000000 1000000000

Sample Output 4

18

Sample Input 5

1 1000000000 1000000000
1000000000

Sample Output 5

0