Overview

For each missile, we determine whether it can catch up to the enemy spaceship. The conclusion is that a missile can reach the spaceship only if the missile’s speed \(S_i\) is greater than the spaceship’s speed \(V\).

Analysis

Consider the positions at time \(t\).

• Missile’s position: \(S_i t\)
• Enemy spaceship’s position: \(D + Vt\)

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

\(S_i t \geq D + Vt\)

Rearranging the equation:

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

Since \(D \geq 1\), the missile and the spaceship are initially separated.

• When \(S_i > V\):
  Since \((S_i - V)\) is positive, taking a sufficiently large time \(t\) guarantees the missile catches up.

• When \(S_i = V\):
  Since the speeds are the same, the initial distance \(D\) never decreases. It cannot catch up.

• When \(S_i < V\):
  Since the spaceship is faster, the distance keeps increasing. It cannot catch up.

Therefore, the answer is simply the number of missiles where \(S_i > V\).

For example, when \(V = 10\), if the missile speeds are \(8, 10, 12, 15\), then the ones that can catch up are \(12\) and \(15\), giving 2 missiles.

If you naively simulate the time for each missile, you won’t know how far to advance time, which can cause TLE or WA due to precision errors. In this problem, by organizing the conditions mathematically, we can determine the result for each missile with just a single check.

Algorithm

1. Read \(N, D, V\) as input.
2. Examine each missile speed \(S_i\) in order.
3. If \(S_i > V\), increment the answer by \(1\).
4. Output the answer at the end.

\(D\) is not directly used in the determination. This is because the constraint \(D \geq 1\) ensures that no missile has already reached the spaceship at the initial position.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

The condition is strictly \(S_i > V\), not \(S_i \geq V\). When the speeds are equal, the initial distance \(D\) prevents the missile from ever catching up.

Also, since \(N\) can be as large as \(10^6\), in Python we use sys.stdin.buffer for fast input reading.

Source Code

import sys

input = sys.stdin.buffer.readline

N, D, V = map(int, input().split())
ans = sum(1 for s in map(int, sys.stdin.buffer.read().split()) if s > V)

print(ans)

---

This editorial was generated by gpt-5.5-high.