Overview

Given the operating intervals of each bus route and the time \(T\) when the destination facility opens, the problem asks to find the time of the first bus that arrives at or after time \(T\).

Analysis

Each bus route \(i\) operates at intervals of \(A_i\) minutes, with the first bus arriving at time \(0\). In other words, the arrival times of bus route \(i\) are \(0, A_i, 2A_i, 3A_i, \ldots\).

Takahashi wants to board the first bus that arrives at or after time \(T\), so for each bus route, we need to calculate the first arrival time at or after \(T\). This is equivalent to finding the smallest \(kA_i\) such that \(kA_i \geq T\) for each \(A_i\).

A naive approach would be to increment \(k\) from 0 for each bus route until finding the first \(k\) satisfying \(kA_i \geq T\), but since \(T\) and \(A_i\) can be as large as \(10^9\), this method would be too slow (potentially \(O(T)\) in the worst case).

Instead, by using the quotient and remainder of dividing \(T\) by each \(A_i\), we can compute the first arrival time at or after \(T\) in \(O(1)\).

Algorithm

1. For each bus route \(i\), let \(q\) be the quotient and \(r\) be the remainder when dividing \(T\) by \(A_i\).
   • If \(r = 0\): A bus arrives exactly at time \(T\), so the arrival time is \(T\).
   • If \(r \neq 0\): The next arrival time is \((q + 1) \times A_i\).
2. Among the arrival times computed above for all bus routes, output the minimum as the answer.

Since the computation for each bus route takes constant time, the overall solution runs in \(O(N)\) time.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (to store the input array)

Implementation Notes

• After reading the input, loop over each \(A_i\) and branch based on whether the remainder of \(T\) divided by \(A_i\) is 0 or not.

• Initialize the minimum value to a sufficiently large value (float('inf')).

• Use integer division (//) and the modulo operation (%) to efficiently compute the next arrival time.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    T = int(data[1])
    A_list = list(map(int, data[2:2+n]))
    
    min_time = float('inf')
    for a in A_list:
        if T % a == 0:
            candidate = T
        else:
            candidate = (T // a + 1) * a
        
        if candidate < min_time:
            min_time = candidate
    
    print(min_time)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.