Overview

There are \(N\) bus routes, and each bus arrives every \(A_i\) minutes starting from time \(0\). The problem asks us to find the earliest time at or after time \(T\) (when the facility opens) that a bus arrives at the bus stop.

Analysis

For each bus route \(i\), the bus arrival times are \(0, A_i, 2A_i, 3A_i, \dots\), i.e., multiples of \(A_i\) (including \(0\)).

Since Takahashi wants to board a bus that arrives at or after time \(T\), for each route \(i\) we need to find “the smallest multiple of \(A_i\) that is greater than or equal to \(T\)”.

Mathematical Approach

Let \(a\) be the interval of a certain route \(i\). To find the first arrival time at or after time \(T\), we can compute it as follows:

1. Consider the quotient of \(T\) divided by \(a\).
2. If \(T\) is divisible by \(a\), then the arrival time is \(T\) itself.
3. If \(T\) is not divisible by \(a\), then the arrival time is the ceiling of \(T / a\) multiplied by \(a\).

This can be concisely expressed in programming (using integer arithmetic) as: $\(\text{arrival} = \left\lceil \frac{T}{a} \right\rceil \times a\)$

When using integer division (floor division //) as in Python, \(\lceil T/a \rceil\) can be written as (T + a - 1) // a. This allows us to compute “the smallest multiple of \(a\) that is greater than or equal to \(T\)” without any conditional branching.

Overall Strategy

Perform the above calculation for all routes, and the minimum value among them is the answer. Since we simply check each of the \(N\) routes in order, this can be solved with a straightforward loop.

Algorithm

1. Initialize a variable min_arrival to hold the answer with a very large value (such as infinity).
2. For each route’s interval \(A_i\), repeat the following:
   • Compute the first arrival time at or after time \(T\): arrival = ((T + A_i - 1) // A_i) * A_i
   • If arrival is less than min_arrival, update min_arrival.
3. Output the final min_arrival.

Complexity

• Time complexity: \(O(N)\)
  • We iterate through the \(N\) routes once, and each iteration involves only constant-time computation.
• Space complexity: \(O(N)\) or \(O(1)\)
  • It is \(O(N)\) if all input values are stored in a list, but \(O(1)\) if values are read and processed one at a time.

Implementation Notes

• Ceiling division: The technique (T + a - 1) // a is very common in competitive programming.

  • Example: When \(T=10, a=3\), \((10+3-1)//3 = 12//3 = 4\). \(4 \times 3 = 12\), which is correct.
  • Example: When \(T=9, a=3\), \((9+3-1)//3 = 11//3 = 3\). \(3 \times 3 = 9\), which also works correctly when \(T\) is divisible by \(a\).

• Initial value: The initial value of min_arrival must be set larger than the maximum possible value (under the given constraints, \(T + \max(A_i) \approx 2 \times 10^9\)). In Python, using float('inf') is convenient.

  Source Code

import sys

def main():
    # 全ての入力を読み込み、空白で分割してリストに格納します
    data = sys.stdin.read().split()
    if not data:
        return
    
    # N: バス路線の数, T: 施設が開く時刻
    N = int(data[0])
    T = int(data[1])
    
    # 最初にバスが到着する時刻を保持する変数
    # 十分に大きな値で初期化します
    min_arrival = float('inf')
    
    # 各バス路線の運行間隔 A_i についてループを回します
    for i in range(N):
        a = int(data[i + 2])
        
        # 各バス路線は 0, a, 2a, 3a... の時刻に到着します。
        # 時刻 T 以降で最初に到着する時刻は、a の倍数のうち T 以上の最小のものです。
        # これは ceil(T / a) * a で求められます。
        # 整数演算では ((T + a - 1) // a) * a と記述できます。
        # T = 0 の場合も、この式で正しく 0 が得られます。
        arrival = ((T + a - 1) // a) * a
        
        # これまでに見つかった到着時刻よりも早ければ更新します
        if arrival < min_arrival:
            min_arrival = arrival
            
    # 高橋君がバスに乗る時刻を出力します
    print(int(min_arrival))

if __name__ == '__main__':
    main()

---

This editorial was generated by gemini-3-flash-preview.