Overview

Given \(N\) types of plants, each with different initial heights and growth rates, the problem asks to find the minimum number of days until all plants reach a target height of \(M\) cm or more.

Analysis

Key Observations

1. Each plant grows independently: The height of the \(i\)-th plant on day \(d\) is \(A_i + B_i \times d\) cm.

2. The condition “all plants are \(M\) cm or more”: This is equivalent to finding “the day when the slowest-growing plant reaches \(M\) cm.” In other words, we need to find the maximum of the number of days required for each plant to reach \(M\) cm.

3. Calculating the required days for each plant: For the \(i\)-th plant to reach \(M\) cm or more:

   • If \(A_i \geq M\), the condition is already satisfied from the start, so \(0\) days
   • If \(A_i < M\), find the smallest integer \(d\) satisfying \(A_i + B_i \times d \geq M\)

Deriving the Required Days

Rearranging \(A_i + B_i \times d \geq M\): $\(d \geq \frac{M - A_i}{B_i}\)$

Since the number of days must be an integer, the required number of days is the ceiling of \(\frac{M - A_i}{B_i}\).

Concrete Example

Consider the case where \(M = 10\) cm: - Plant 1: \(A_1 = 3\), \(B_1 = 2\) → Required growth is \(7\) cm, days = \(\lceil 7/2 \rceil = 4\) days - Plant 2: \(A_2 = 8\), \(B_2 = 1\) → Required growth is \(2\) cm, days = \(\lceil 2/1 \rceil = 2\) days - Plant 3: \(A_3 = 12\), \(B_3 = 3\) → Already \(M\) or more, so \(0\) days

All plants reach \(M\) cm or more on day \(\max(4, 2, 0) = 4\).

Algorithm

1. For each plant, calculate the number of days required to reach \(M\) cm or more
   • If \(A_i \geq M\), then \(0\) days
   • Otherwise, \(\lceil (M - A_i) / B_i \rceil\) days
2. Output the maximum of the required days across all plants

Complexity

• Time complexity: \(O(N)\)
  • Calculate the required days for each plant in constant time, repeated \(N\) times
• Space complexity: \(O(1)\)
  • Only uses a variable to store the maximum (processing input sequentially)

Implementation Notes

1. Ceiling calculation: In Python, you can use math.ceil((M - A) / B) for ceiling division. If you want to calculate using only integers, you can also use the formula (M - A + B - 1) // B.

2. Checking the initial condition: By handling the case \(A_i \geq M\) first, you can avoid unnecessary calculations.

3. Beware of overflow: Although \(M\), \(A_i\), and \(B_i\) can be up to \(10^9\), Python does not have integer overflow, so you can calculate directly. In other languages (such as C++), you need to use 64-bit integers.

   Source Code

import math

def solve():
    N, M = map(int, input().split())
    
    max_days = 0
    for _ in range(N):
        A, B = map(int, input().split())
        if A >= M:
            # Already at or above target height
            days_needed = 0
        else:
            # Need (M - A) / B days, rounded up
            days_needed = math.ceil((M - A) / B)
        max_days = max(max_days, days_needed)
    
    print(max_days)

solve()

This editorial was generated by claude4.5opus.