Overview

This problem asks you to find the earliest bus arrival time at or after time \(T\) across multiple bus routes. We calculate the arrival time for each route and output the minimum.

Analysis

Key Insight

Each bus route \(i\) has buses arriving at times \(0, A_i, 2A_i, 3A_i, \ldots\). In other words, arrival times for bus route \(i\) are multiples of \(A_i\).

To find the first arrival time at or after time \(T\), we need to find “the smallest multiple of \(A_i\) that is at least \(T\)”.

Understanding Through Examples

For example, when \(T = 7\) and \(A_i = 3\): - Bus route \(i\) arrives at times \(0, 3, 6, 9, 12, \ldots\) - The first arrival at or after \(T = 7\) is at time \(9\)

This can be calculated as \(\lceil 7 / 3 \rceil \times 3 = 3 \times 3 = 9\).

Problem with the Naive Approach

The approach of “starting from time \(0\) and incrementing by \(1\) until finding a time at or after \(T\) when some bus arrives” would result in TLE (Time Limit Exceeded) since \(T\) can be as large as \(10^9\).

Solution

By using the ceiling function (ceiling division) to directly calculate for each bus route, we can find the answer in \(O(1)\).

The smallest multiple of \(A_i\) that is at least \(T\) \(= \lceil T / A_i \rceil \times A_i\)

Algorithm

1. For each bus route \(i\), calculate the first arrival time at or after time \(T\)
   • If \(T = 0\): arrival time is \(0\)
   • If \(T > 0\): let \(k = \lceil T / A_i \rceil\), then arrival time is \(k \times A_i\)
2. Find the minimum arrival time across all routes
3. Output that minimum value

Computing Ceiling Division

Integer ceiling division \(\lceil T / A_i \rceil\) can be computed using the following formula:

\[k = \lfloor (T + A_i - 1) / A_i \rfloor\]

This achieves ceiling by adding \(A_i - 1\) to \(T\) before performing floor division.

Complexity

• Time complexity: \(O(N)\)
  • Calculate arrival time in \(O(1)\) for each bus route, repeated for \(N\) routes
• Space complexity: \(O(N)\)
  • Required for storing the input array \(A\)

Implementation Notes

1. Implementing ceiling division: Using the expression (T + a - 1) // a achieves ceiling division with only integer operations. While you can also use math.ceil(T / a), integer operations are safer if you’re concerned about floating-point precision errors.

2. Handling the case \(T = 0\): When \(T = 0\), all bus routes have a bus arriving at time \(0\), so the answer is \(0\). In the code, (0 + a - 1) // a = 0 computes correctly, but explicit case handling is also fine.

3. Overflow considerations: When \(T\) and \(A_i\) are at most \(10^9\), \(k \times A_i\) is at most around \(10^9\). Since Python doesn’t have integer overflow issues, no special handling is needed.

Source Code

import math

def solve():
    N, T = map(int, input().split())
    A = list(map(int, input().split()))
    
    min_time = float('inf')
    
    for a in A:
        # First arrival time of bus route a at or after time T
        # Buses arrive at times 0, a, 2a, 3a, ...
        # Find the smallest a*k that is at least T
        if T == 0:
            arrival = 0
        else:
            # ceil(T / a) * a
            k = (T + a - 1) // a  # ceil(T / a)
            arrival = k * a
        
        min_time = min(min_time, arrival)
    
    print(min_time)

solve()

---

This editorial was generated by claude4.5opus.