Overview

A problem to find the number of missiles that can catch up to a spaceship escaping from Earth. We just need 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 two cases.

Case 1: When \(S_i \leq V\)

The left side is non-positive (\(\leq 0\)) for \(t \geq 0\). On the other hand, since \(D \geq 1 > 0\), there is no \(t \geq 0\) that satisfies this inequality. In other words, the missile cannot catch up to the spaceship.

Intuitively, if the missile’s speed is less than or equal to the spaceship’s speed, it’s obvious that it can never catch up to a spaceship that starts at a distance \(D\) ahead.

Case 2: When \(S_i > V\)

Since \(S_i - V > 0\), dividing both sides by \(S_i - V\):

\[t \geq \frac{D}{S_i - V}\]

This always has a positive solution, so given enough time, the missile will catch up to the spaceship.

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

Algorithm

1. Read \(N\), \(D\), \(V\) (\(D\) is not directly used in the determination condition)
2. For each missile’s speed \(S_i\), determine whether \(S_i > V\)
3. Count and output the number of missiles that satisfy the condition

Concrete Example

For \(N=3\), \(D=10\), \(V=5\), \(S = [3, 5, 8]\): - \(S_1 = 3 \leq 5\): Cannot reach - \(S_2 = 5 \leq 5\): Cannot reach (even with the same speed, it cannot catch up due to the initial distance) - \(S_3 = 8 > 5\): Can reach (catches up at time \(t = 10/(8-5) = 10/3\))

The answer is \(1\).

Complexity

• Time complexity: \(O(N)\) (constant-time comparison for each missile)
• Space complexity: \(O(1)\) (only a counter variable is used)

Implementation Notes

• The value of \(D\) is not needed for determining reachability. We can determine it solely by whether \(S_i > V\) (since \(D \geq 1\) is guaranteed).

• Since \(N\) can be as large as \(10^6\), in C++ we use ios::sync_with_stdio(false) and cin.tie(nullptr) to speed up I/O.

• Since speed values can be up to \(10^9\), we read them as long long type (in this problem only comparisons are performed so int would also work, but we use long long for safety).

  Source Code

#include <iostream>
#include <vector>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    long long D, V;
    cin >> N >> D >> V;
    
    int count = 0;
    for(int i = 0; i < N; i++){
        long long s;
        cin >> s;
        if(s > V) count++;
    }
    
    cout << count << endl;
    return 0;
}

---

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