A - Target Shooting Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は夏祭りの的当てゲームに挑戦しています。

高橋君の前には N 個のボールが用意されています。各ボールはそれぞれ重さが異なり、 i 番目のボールの重さは D_i です。高橋君がボールを投げると、ボールの重さに比例した距離だけ飛びます。具体的には、重さが D のボールを投げると、ちょうど距離 D だけ飛びます。

的は高橋君から距離 L の位置に設置されています。的には幅があり、高橋君からの距離が L - W 以上 L + W 以下の範囲にボールが落ちれば、的に当たったとみなされます。

高橋君が N 個のボールをすべて 1 つずつ投げたとき、的に当たるボールの数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq W \leq L \leq 10^9
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
  • D_i はすべて異なる
  • 入力はすべて整数

入力

N L W
D_1 D_2 \ldots D_N
  • 1 行目には、ボールの個数を表す N 、的までの距離を表す L 、的の幅に関する値 W が、スペース区切りで与えられる。
  • 2 行目には、各ボールの重さを表す D_1, D_2, \ldots, D_N が、スペース区切りで与えられる。

出力

的に当たるボールの数を 1 行で出力せよ。

入力例 1

5 10 3
5 8 10 13 15

出力例 1

3

入力例 2

4 50 5
1 10 30 100

出力例 2

0

入力例 3

10 100 20
50 79 80 95 100 120 121 150 200 60

出力例 3

4

入力例 4

20 500000000 100000000
1 100000000 399999999 400000000 400000001 450000000 500000000 550000000 599999999 600000000 600000001 700000000 800000000 999999999 1000000000 250000000 123456789 500000001 499999999 350000000

出力例 4

9

入力例 5

1 1 1
1

出力例 5

1

Score : 200 pts

Problem Statement

Takahashi is playing a target shooting game at a summer festival.

In front of Takahashi, N balls are prepared. Each ball has a different weight, and the weight of the i-th ball is D_i. When Takahashi throws a ball, it flies a distance proportional to its weight. Specifically, when a ball of weight D is thrown, it flies exactly a distance of D.

A target is placed at distance L from Takahashi. The target has some width, and a ball is considered to have hit the target if it lands at a distance from Takahashi that is at least L - W and at most L + W.

When Takahashi throws all N balls one by one, find the number of balls that hit the target.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq W \leq L \leq 10^9
  • 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
  • All D_i are distinct
  • All inputs are integers

Input

N L W
D_1 D_2 \ldots D_N
  • The first line contains N representing the number of balls, L representing the distance to the target, and W representing the value related to the target's width, separated by spaces.
  • The second line contains D_1, D_2, \ldots, D_N representing the weight of each ball, separated by spaces.

Output

Output the number of balls that hit the target in one line.

Sample Input 1

5 10 3
5 8 10 13 15

Sample Output 1

3

Sample Input 2

4 50 5
1 10 30 100

Sample Output 2

0

Sample Input 3

10 100 20
50 79 80 95 100 120 121 150 200 60

Sample Output 3

4

Sample Input 4

20 500000000 100000000
1 100000000 399999999 400000000 400000001 450000000 500000000 550000000 599999999 600000000 600000001 700000000 800000000 999999999 1000000000 250000000 123456789 500000001 499999999 350000000

Sample Output 4

9

Sample Input 5

1 1 1
1

Sample Output 5

1