Overview

The enemy spaceship starts at coordinate \(D\) and moves away at speed \(V\), while missiles are launched from coordinate \(0\) at speed \(S_i\) to chase it.
The problem is to determine whether each missile can catch up to the spaceship, and count how many can.

Analysis

Consider the positions at time \(t\).

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

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

\(S_i t \geq D + Vt\)

Rearranging this gives:

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

Here, from the constraints \(D \geq 1\), so the right-hand side is positive.

Case \(S_i \leq V\)

Since \((S_i - V) \leq 0\), the left-hand side cannot be positive for \(t \geq 0\).
In other words, the distance to the spaceship never decreases, so the missile cannot reach it.

Case \(S_i > V\)

Since \((S_i - V) > 0\), by choosing a sufficiently large time satisfying

\(t \geq \frac{D}{S_i - V}\)

the missile will always reach the spaceship.

Therefore, whether a missile can reach the spaceship can be determined simply by:

\(S_i > V\)

For example, when \(D=10, V=3\):

• If \(S_i=5\), the missile is faster, so it will eventually catch up
• If \(S_i=3\), they have the same speed, so the distance of \(10\) never decreases and it cannot catch up
• If \(S_i=2\), the gap widens further, so it cannot catch up

There is no need to simulate time. A method that finely examines continuous time is not only slow, but also prone to errors in handling precision and termination conditions.

Algorithm

Read each missile’s speed \(S_i\) in order.

1. Initialize a variable ans representing the answer to \(0\)
2. For each missile, read its speed \(S_i\)
3. If \(S_i > V\), the missile can reach the spaceship, so increment ans by \(1\)
4. Finally, output ans

Since only the relative magnitude of speeds is needed for the determination, distance \(D\) is received as input but is not used in the judgment.

Complexity

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

Implementation Notes

Since \(N\) can be as large as \(10^6\), there is no need to store all speeds in an array.
By making the determination on the spot while reading input, almost no additional memory is used.

Also, since \(D, V, S_i\) can be up to \(10^9\), they fit in int, but considering the possibility of handling arithmetic expressions, using long long is safer.

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long D, V;
    cin >> N >> D >> V;

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        long long S;
        cin >> S;
        if (S > V) ++ans;
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.