Overview

Given the initial height and growth rate of each plant, find the minimum number of days until all plants reach at least a specified height \(M\).

Analysis

Each plant \(i\) has a height of \(A_i + B_i \times d\) after \(d\) days. Since we want to find the number of days \(d\) for all plants to reach at least \(M\), we can compute the “first day the height reaches \(M\) or more” for each plant and take the maximum among them.

Specifically, we solve the following inequality for each plant: $\( A_i + B_i \times d \geq M \)\( Rearranging: \)\( B_i \times d \geq M - A_i \Rightarrow d \geq \frac{M - A_i}{B_i} \)\( After computing the right-hand side as a decimal, we need to **round up** to obtain the **smallest integer \)d$**. This can be done using math.ceil.

However, if the initial height \(A_i\) is already \(M\) or more, that plant satisfies the condition from day 0, so the required number of days is 0.

A naive approach of incrementing the number of days by 1 and checking whether all plants have reached \(M\) or more each time may result in TLE (Time Limit Exceeded), since the answer can be very large. Instead, we directly calculate the required number of days for each plant to efficiently determine the answer.

Algorithm

1. For each plant, if \(A_i \geq M\), the required number of days is 0.
2. Otherwise, compute the decimal value of \(d \geq \frac{M - A_i}{B_i}\) and round it up to get the required number of days.
3. The answer is the maximum of the required number of days across all plants.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding input)

Implementation Notes

• Use math.ceil() for rounding up.

• When performing division between integers, be careful that accurate rounding up may not work without first converting to floating point (though in Python this works safely).

• If the initial height already satisfies the condition (\(A_i \geq M\)), treat the required number of days as 0.

  Source Code

import math

def main():
    N, M = map(int, input().split())
    plants = [tuple(map(int, input().split())) for _ in range(N)]
    
    # 各植物がM以上になる日を計算し、その最大値を取る
    max_day = 0
    for A, B in plants:
        if A >= M:
            day = 0
        else:
            # A + B * d >= M を満たす最小のdを求める
            # B * d >= M - A
            # d >= (M - A) / B
            # 切り上げ
            day = math.ceil((M - A) / B)
        max_day = max(max_day, day)
    
    print(max_day)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.