Overview

A problem of counting the number of missiles that can catch up to a spaceship escaping from Earth. The solution is to determine whether each missile’s speed is greater than the spaceship’s speed.

Analysis

Consider the position of each object at time \(t\).

• Position of the enemy spaceship: \(D + Vt\)
• Position of the \(i\)-th missile: \(S_i \cdot t\)

The condition for a missile to reach the spaceship is that there exists some \(t \geq 0\) such that:

\[S_i \cdot t \geq D + V \cdot t\]

Rearranging this:

\[(S_i - V) \cdot t \geq D\]

Here we consider cases:

• If \(S_i > V\): Equality holds at \(t = \frac{D}{S_i - V}\), so the missile can catch up to the spaceship.
• If \(S_i = V\): The left side is always \(0\), and since \(D > 0\), there is no \(t\) that satisfies the inequality. If the missile and spaceship have the same speed, the initial distance \(D\) can never be closed.
• If \(S_i < V\): Since \(S_i - V < 0\), as \(t\) increases the left side diverges to negative infinity, so the missile can never catch up.

Conclusion: The condition for a missile to reach the spaceship is simply \(S_i > V\).

Let’s verify with a concrete example. When \(D = 10, V = 3\): - If \(S_i = 5\), it catches up at \(t = \frac{10}{5-3} = 5\) ✓ - If \(S_i = 3\), the speeds are the same so the distance \(10\) never decreases ✗ - If \(S_i = 2\), the distance keeps increasing ✗

Algorithm

1. Read \(N, D, V\)
2. For each missile’s speed \(S_i\), determine whether \(S_i > V\)
3. Count and output the number of missiles satisfying the condition

Note that the value of \(D\) is not directly used in the condition check (since \(D \geq 1\) is guaranteed, if \(S_i > V\) then the missile will always catch up in finite time).

Complexity

• Time complexity: \(O(N)\) (one comparison per missile)
• Space complexity: \(O(N)\) (storing input data)

Implementation Notes

• Since \(N\) can be as large as \(10^6\), sys.stdin.buffer.read() is used to read input quickly.

• No floating-point calculations are needed; the problem can be solved using only integer comparisons.

• While \(D\) is necessary for the problem setup, since \(D \geq 1\) is guaranteed, note that the condition becomes \(S_i > V\) (strict inequality, not including equality).

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    D = int(data[1])
    V = int(data[2])
    count = sum(1 for i in range(3, 3 + N) if int(data[i]) > V)
    print(count)

main()

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