Overview

This problem asks you to determine whether a launched missile can catch up to an enemy spaceship that is moving away from Earth. At first glance, it appears to be a physics pursuit problem (a classic “catching up” problem), but when the equations are simplified, it reduces to the very simple condition of “whether the missile’s speed is greater than the spaceship’s speed.”

Analysis

Let’s express the coordinates of the enemy spaceship and missile \(i\) at time \(t \geq 0\) as mathematical formulas.

• Enemy spaceship’s coordinate: \(D + V \cdot t\)
• Missile \(i\)’s coordinate: \(S_i \cdot t\)

A missile reaching the spaceship means that at some time \(t \geq 0\), “missile’s coordinate \(\geq\) spaceship’s coordinate” holds. In other words, we need to determine whether there exists a \(t \geq 0\) satisfying the following inequality:

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

Rearranging this expression, we get:

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

Here, from the problem constraints, the initial position satisfies \(D \geq 1\) (always positive). Under this condition, we classify whether a \(t \geq 0\) satisfying the above inequality exists based on the relationship between \(S_i\) and \(V\).

1. When \(S_i \leq V\) We have \(S_i - V \leq 0\). Since \(t \geq 0\), the left side \(t(S_i - V)\) is always at most \(0\). Since the right side satisfies \(D \geq 1\), there is absolutely no \(t\) that satisfies the inequality \(t(S_i - V) \geq D\). (Intuitively, you cannot catch up to an opponent fleeing at a speed greater than or equal to yours)

2. When \(S_i > V\) We have \(S_i - V > 0\). In this case, by choosing a sufficiently large time \(t\) (specifically \(t \geq \frac{D}{S_i - V}\)), the inequality can always be satisfied. (You can always eventually catch up to an opponent fleeing at a slower speed, no matter how far away their initial position is)

From the above analysis, we can see that the necessary and sufficient condition for a missile to reach the spaceship is \(S_i > V\). The value of the initial position \(D\) has absolutely no effect on determining whether the missile catches up.

Algorithm

1. Read \(N, D, V\) from input.
2. Read each missile’s speed \(S_i\) in order and determine whether \(S_i > V\) is satisfied.
3. Count the number of missiles satisfying the condition and output the final count.

Since each missile’s determination can be made independently, there is no need to store all speeds in an array. It is possible to determine and count on the fly while reading the input.

Complexity

• Time complexity: \(O(N)\) For each of the \(N\) missiles, the determination is made in constant time \(O(1)\). Since \(N \leq 10^6\), this easily fits within the time limit.
• Space complexity: \(O(1)\) Since input is processed on the fly, there is no need to allocate an array of \(N\) elements, resulting in extremely low memory usage.

Implementation Notes

• Fast I/O: Since \(N\) can be as large as \(10^6\), in C++ we add ios_base::sync_with_stdio(false); cin.tie(NULL); at the beginning of the main function to eliminate the bottleneck of std::cin and std::cout and speed up I/O.

• Variable types: The values of \(D\) and \(V\) can be up to \(10^9\), which fits within the maximum value of a typical 32-bit integer type (int) (approximately \(2 \times 10^9\)), but using long long type is safer to prevent overflow.

  Source Code

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long D, V;
    if (!(cin >> N >> D >> V)) return 0;

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

    cout << count << "\n";

    return 0;
}

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