Overview

For each of the \(N\) balls, determine whether the flying distance (= weight \(D_i\)) falls within the target’s range \([L-W, L+W]\), and count the number of balls that hit the target.

Analysis

Key Insight

When a ball has weight \(D\), it flies exactly a distance of \(D\). The condition for hitting the target is that the landing position (= distance \(D\)) is at least \(L - W\) and at most \(L + W\).

In other words, we simply need to check whether the following inequality holds for each ball:

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

Concrete Example

For example, if \(L = 10\), \(W = 3\), the target’s range is \([7, 13]\).

• Ball with weight \(5\) → lands at distance \(5\) → out of range → miss
• Ball with weight \(8\) → lands at distance \(8\) → in range → hit
• Ball with weight \(13\) → lands at distance \(13\) → in range → hit
• Ball with weight \(14\) → lands at distance \(14\) → out of range → miss

Approach

For this problem, it is sufficient to check each ball one by one. Since \(N\) is at most \(2 \times 10^5\), an \(O(N)\) approach that scans through all balls once is more than fast enough. No tricks like sorting or binary search are needed.

Algorithm

1. Compute the lower bound \(lo = L - W\) and upper bound \(hi = L + W\) of the target’s range.
2. For each of the \(N\) balls, check whether the weight \(D_i\) satisfies \(lo \leq D_i \leq hi\).
3. Count and output the number of balls that satisfy the condition.

N, L, W = map(int, input().split())
D = list(map(int, input().split()))
lo = L - W
hi = L + W
print(sum(1 for d in D if lo <= d <= hi))

Complexity

• Time complexity: \(O(N)\) — only one constant-time comparison is performed for each ball
• Space complexity: \(O(N)\) — for the list storing the weights of the balls

Implementation Notes

• In Python, writing lo <= d <= hi directly expresses the mathematical interval check. This is equivalent to lo <= d and d <= hi.

• The constraints guarantee \(W \leq L\), so \(L - W \geq 0\), meaning there is no concern about the lower bound becoming negative.

• Using the generator expression sum(1 for d in D if condition) provides a concise way to count the number of elements satisfying the condition.

  Source Code

N, L, W = map(int, input().split())
D = list(map(int, input().split()))
lo = L - W
hi = L + W
print(sum(1 for d in D if lo <= d <= hi))

---

This editorial was generated by claude4.6opus-thinking.