Overview

This problem asks us to find all checkpoints where Takahashi arrives before Aoki (overtakes him) in a marathon race.

Analysis

Understanding the Problem

• Takahashi: Runs at a constant speed of \(V\) meters/second
• Aoki: Arrives at each checkpoint \(i\) at time \(T_i\) (has an uneven pace)
• “Overtaking” means Takahashi arrives at a checkpoint strictly earlier

Calculating Takahashi’s Arrival Time

Takahashi’s arrival time at checkpoint \(k\) is: $\(\text{Takahashi's arrival time} = \frac{D_1 + D_2 + \cdots + D_{k-1}}{V}\)$

For example, the arrival time at checkpoint 2 is \(\frac{D_1}{V}\) seconds.

Condition for Overtaking

Whether Takahashi overtakes at checkpoint \(k\): $\(\frac{D_1 + D_2 + \cdots + D_{k-1}}{V} < T_k\)$

Avoiding Floating-Point Issues

If we compute the above inequality naively, division may cause floating-point errors.

To avoid this, we transform the inequality: $\(D_1 + D_2 + \cdots + D_{k-1} < T_k \times V\)$

This way, we can determine the result using only integer comparisons.

Note on Overflow

Since \(T_i\) can be up to \(10^{18}\) and \(V\) can be up to \(10^9\), \(T_i \times V\) can be as large as \(10^{27}\). In Python, arbitrary-precision integers are handled automatically, so there’s no need to worry about overflow.

Algorithm

1. Initialize the cumulative distance total_distance to 0
2. For \(i = 1, 2, \ldots, N-1\), repeat the following:
   • Add \(D_i\) to total_distance (total distance to checkpoint \(i+1\))
   • If total_distance < T[i] * V, Takahashi overtakes at checkpoint \(i+1\)
   • If overtaking occurs, add to the result list
3. If the result list is empty, output -1; otherwise, output the checkpoint numbers

Concrete Example

For \(N=3, V=2, D=[10, 20], T=[6, 20]\):

Checkpoint	Takahashi’s Arrival Time	Aoki’s Arrival Time	Overtaking Determination
2	\(10/2=5\) seconds	\(6\) seconds	\(5 < 6\) → Overtakes
3	\(30/2=15\) seconds	\(20\) seconds	\(15 < 20\) → Overtakes

Output: 2 3

Complexity

• Time Complexity: \(O(N)\)
  • Because we check each checkpoint exactly once
• Space Complexity: \(O(N)\)
  • Required for storing input and maintaining the result list

Implementation Notes

1. Avoid floating-point numbers: By comparing with total_distance < T[i] * V instead of total_distance / V < T[i], we can determine the result accurately without errors.

2. Index correspondence:

   • D[i] is the distance from checkpoint \(i+1\) to \(i+2\) (0-indexed)
   • T[i] is Aoki’s arrival time at checkpoint \(i+2\) (0-indexed)
   • The output checkpoint number is 1-indexed, so it’s i + 2

3. Cumulative sum update: Instead of summing distances from the beginning each time, adding to the previous value allows efficient computation.

Source Code

def main():
    import sys
    input = sys.stdin.readline
    
    N, V = map(int, input().split())
    D = list(map(int, input().split()))
    T = list(map(int, input().split()))
    
    # Calculate the time when Takahashi arrives at checkpoint i
    # Start from checkpoint 1 (time 0)
    # Arrival time at checkpoint i+1 = (D_1 + D_2 + ... + D_i) / V
    
    # Aoki's arrival time at checkpoint i is T[i-2] (for i >= 2)
    # T_2, T_3, ..., T_N correspond to T[0], T[1], ..., T[N-2]
    
    result = []
    total_distance = 0
    
    for i in range(N - 1):
        # From checkpoint i to checkpoint i+1
        total_distance += D[i]
        # Arriving at checkpoint i+2 (i+1 in 0-indexed)
        # The actual checkpoint number is i+2
        checkpoint = i + 2
        
        # Takahashi's arrival time: total_distance / V
        # Aoki's arrival time: T[i] (stored in order T_2, T_3, ...)
        
        # Takahashi arrives first <=> total_distance / V < T[i]
        # <=> total_distance < T[i] * V
        
        takahashi_time_numerator = total_distance  # numerator
        takahashi_time_denominator = V  # denominator
        aoki_time = T[i]
        
        # total_distance / V < T[i]
        # <=> total_distance < T[i] * V
        if total_distance < aoki_time * V:
            result.append(checkpoint)
    
    if result:
        print(' '.join(map(str, result)))
    else:
        print(-1)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.