Overview

A problem where you throw balls at a target and count how many hit. The weight of each ball corresponds to its flight distance, and the condition for hitting the target is whether the flight distance falls within the range \([L - W, L + W]\).

Analysis

In this problem, each ball’s weight \(D_i\) directly becomes its flight distance, so the condition for hitting the target can be expressed by the following inequality:

\[ L - W \leq D_i \leq L + W \]

In other words, we just need to determine whether each ball’s weight falls within this range.

Naive Approach and Its Issues

The simplest method is to check this inequality for every ball. However, since \(N\) can be up to \(2 \times 10^5\) according to the constraints, a full scan each time results in a worst-case time complexity of \(O(N)\), which may not be fast enough (especially in slower languages like Python).

Improvement: Sort + Binary Search

By sorting the ball weights in advance, we can efficiently find the number of balls within the range \([L - W, L + W]\). This can be achieved using binary search.

• bisect_left(D, left): The smallest index in the array where the value is greater than or equal to left
• bisect_right(D, right): The smallest index in the array where the value is strictly greater than right

The difference between these two values is exactly the number of balls satisfying the condition.

Concrete Example

Suppose we have the following input:

N=5, L=10, W=3
D = [7, 9, 10, 12, 15]

The target range is \([10 - 3, 10 + 3] = [7, 13]\).

For the sorted \(D = [7, 9, 10, 12, 15]\): - bisect_left(D, 7) → 0 - bisect_right(D, 13) → 4

Therefore, the number of balls within the range is \(4 - 0 = 4\).

Algorithm

1. Read the input.
2. Sort the ball weight list \(D\) in ascending order.
3. Compute the target range \([L - W, L + W]\).
4. Use bisect_left and bisect_right to find the number of balls within the range.
5. Output the result.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(1)\) (no additional large memory used)

Implementation Notes

• In Python, binary search can be easily performed using the bisect module.

• Note that bisect_left finds the “greater than or equal to” boundary, while bisect_right finds the “strictly greater than” boundary.

• Since the order of the input does not matter, sorting causes no issues.

  Source Code

import bisect

N, L, W = map(int, input().split())
D = list(map(int, input().split()))

# 的の範囲 [L - W, L + W]
left = L - W
right = L + W

# ボールの重さをソート
D.sort()

# 的に入る範囲に含まれるボールの数を二分探索で求める
# 重さ D が left 以上 right 以下のものを数える
low_index = bisect.bisect_left(D, left)
high_index = bisect.bisect_right(D, right)

print(high_index - low_index)

---

This editorial was generated by qwen3-coder-480b.