Overview

In a target-hitting game where the distance a ball flies is proportional to its weight, we need to determine whether each ball lands within the range of the target and count the number of balls that hit.

Analysis

The essence of the problem is to determine whether each ball’s weight \(D_i\) falls within the target’s range \([L-W, L+W]\). Given the constraints, \(N\) can be up to 200,000, but simply checking the condition for each ball is sufficiently efficient. The condition \(L - W \leq D_i \leq L + W\) is straightforward, and each ball can be checked in constant time.

Algorithm

1. Read the input values \(N\), \(L\), \(W\) and the list of ball weights \(D_list\)
2. Initialize a counter variable count to 0
3. For each ball’s weight \(D_i\), check whether the following condition is satisfied:
   • \(L - W \leq D_i \leq L + W\)
4. If the condition is satisfied, increment the counter by 1
5. Output the final value of the counter

Complexity

• Time complexity: \(O(N)\)
  • Since we perform one comparison for each ball
• Space complexity: \(O(N)\)
  • Since the list storing the ball weights has size \(N\)

Implementation Notes

• When writing the condition, care must be taken with the direction of the inequality signs

• Since all input values are integers, there is no need to worry about floating-point precision errors

• Although all ball weights are distinct, this does not particularly affect the solution to this problem

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    L = int(data[1])
    W = int(data[2])
    D_list = list(map(int, data[3:3+n]))
    
    count = 0
    for D in D_list:
        if L - W <= D <= L + W:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.