Overview

This problem asks you to determine how many of the \(N\) prepared missiles can catch up to an enemy spaceship that is moving away from Earth. By rearranging the equations, the problem can be solved simply by comparing the speeds of the missiles and the spaceship, without performing any complex simulation.

Analysis

First, let’s express the condition for a missile to catch up to the spaceship mathematically.

At time \(t \ (t \geq 0)\), the positions of the enemy spaceship and the \(i\)-th missile are as follows: - Spaceship’s position: \(D + Vt\) - Missile’s position: \(S_i t\)

A missile can reach the spaceship if, at some time \(t \geq 0\), the missile’s position becomes greater than or equal to the spaceship’s position. In other words, we need to determine whether there exists a \(t \geq 0\) satisfying the following inequality:

\[S_i t \geq D + Vt\]

To rearrange this inequality with respect to \(t\), we move \(Vt\) to the left side:

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

Here, from the problem constraints, we know that the spaceship’s initial position \(D\) is at least \(1\) (\(D \geq 1\)). With this in mind, we consider cases based on the relationship between the missile’s speed \(S_i\) and the spaceship’s speed \(V\).

1. When \(S_i \leq V\) (the missile is the same speed as or slower than the spaceship)

   • We have \(S_i - V \leq 0\).
   • Since \(t \geq 0\), the left side \((S_i - V) t\) is always at most \(0\).
   • Since the right side satisfies \(D \geq 1\), there is absolutely no \(t \geq 0\) that satisfies the inequality \((S_i - V) t \geq D\).
   • In other words, the missile can never catch up.

2. When \(S_i > V\) (the missile is faster than the spaceship)

   • We have \(S_i - V > 0\).
   • By making time \(t\) sufficiently large (specifically, \(t \geq \frac{D}{S_i - V}\)), the inequality can always be satisfied.
   • In other words, the missile will always eventually catch up.

From the above analysis, regardless of the value of the initial position \(D\), we can conclude that “the missile’s speed \(S_i\) being greater than the spaceship’s speed \(V\) (\(S_i > V\))” is the necessary and sufficient condition for the missile to reach the spaceship.

Algorithm

1. Read the spaceship’s speed \(V\) and each missile’s speed \(S_i \ (1 \leq i \leq N)\) from the input.
2. For each \(S_i\), determine whether \(S_i > V\) holds.
3. Count the number of missiles satisfying the condition and output it as the final answer.

The spaceship’s initial position \(D\) does not affect the determination, so it can be ignored.

Complexity

• Time complexity: \(O(N)\) For each of the \(N\) missile speeds \(S_i\), we perform one comparison with \(V\), so the processing completes in time proportional to the number of missiles \(N\). Since \(N \leq 10^6\), this comfortably fits within the time limit.
• Space complexity: \(O(N)\) Since all input is read into memory, memory proportional to the number of missiles \(N\) is used.

Implementation Notes

• Fast I/O: In this problem, \(N\) can be as large as \(10^6\), so reading input line by line using input() in Python may result in a Time Limit Exceeded (TLE) due to I/O overhead. By using sys.stdin.read().split(), all input can be read at once efficiently.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    V = int(input_data[2])
    
    count = 0
    for x in input_data[3:]:
        if int(x) > V:
            count += 1
            
    print(count)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.5-flash-thinking.