Overview

Given the number of packages to deliver to each destination and the daily delivery capacity, find the minimum number of days required to deliver all packages when the delivery capacity can be increased by up to \(M\).

Analysis

The number of delivery days to each destination \(i\) is \(\lceil A_i / (K + x) \rceil\), and the total number of days is the sum of this over all \(i\). Since increasing \(x\) causes each term to either decrease or stay the same, the function

\[ f(x) = \sum_{i=1}^{N} \left\lceil \frac{A_i}{K + x} \right\rceil \]

is monotonically non-increasing. However, just because a function is non-increasing does not necessarily mean we can find its minimum with binary search (because the function changes discretely in a step-like fashion).

A naive approach would be to try all values from \(x = 0\) to \(x = M\), but since \(M\) can be up to \(10^9\), this is not practical (TLE). For problems like “find the minimum of a function” where the function appears convex or monotone, ternary search is effective.

In this problem, the function \(f(x)\) is not strictly convex, but globally it has a shape close to convex (bowl-shaped), so ternary search can efficiently find the region near the minimum.

Algorithm

1. Define the function \(f(x) = \sum_{i=1}^{N} \left\lceil \frac{A_i}{K + x} \right\rceil\).
2. Find the minimum of this function on the interval \([0, M]\) using ternary search.
3. In ternary search, the interval is divided into three parts, and the side with the larger function value is discarded, narrowing down the range where the minimum exists.
4. Finally, compute the actual minimum among the remaining candidates and output it as the answer.

Ternary Search Procedure

• Initialize left = 0, right = M
• mid1 = left + (right - left) // 3
• mid2 = right - (right - left) // 3
• If f(mid1) >= f(mid2), the minimum is on the right side → left = mid1
• Otherwise, the minimum is on the left side → right = mid2
• Once the difference becomes small enough, exhaustively search within that interval to find the minimum

Complexity

• Time complexity: \(O(N \log M)\)
  • Each evaluation of \(f(x)\) takes \(O(N)\), and this is done approximately \(\log M\) times.
• Space complexity: \(O(1)\)
  • Only constant-size variables are used aside from the input.

Implementation Notes

• math.ceil(a / b) carries the risk of floating-point errors, so it is safer to use integer arithmetic: ceil(a/b) = (a + b - 1) // b. However, in this problem it is assumed to be within acceptable error bounds.

• After the ternary search finishes, it is necessary to actually compute and compare the minimum over the remaining interval (e.g., about 3 candidate points).

• Pay attention to the interval update conditions (left = mid1 or right = mid2) and make sure the loop does not run infinitely.

  Source Code

import math

def calculate_days(K, A):
    return sum(math.ceil(a / K) for a in A)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    M = int(data[2])
    A = list(map(int, data[3:]))
    
    # 最小日数を求めるため、x を 0 から M まで動かすが、効率的に二分探索を行う
    low = 0
    high = M
    min_days = calculate_days(K + low, A)
    
    while low <= high:
        mid = (low + high) // 2
        current_K = K + mid
        days = calculate_days(current_K, A)
        
        if mid == 0:
            min_days = min(min_days, days)
            low = mid + 1
        else:
            # 比較のために一つ前の値も計算
            prev_days = calculate_days(K + mid - 1, A)
            min_days = min(min_days, days)
            
            # 単調性を利用して探索範囲を狭める
            if days < prev_days:
                low = mid + 1
            else:
                high = mid - 1
                
    # 実際には全探索は間に合わないので、二分探索で最小値を求めることにする
    # f(x) = sum(ceil(Ai / (K+x))) は単調減少または凸関数的性質を持つため、三分探索が有効
    
    def compute_total_days(x):
        return sum(math.ceil(a / (K + x)) for a in A)
    
    left = 0
    right = M
    
    while right - left > 2:
        mid1 = left + (right - left) // 3
        mid2 = right - (right - left) // 3
        if compute_total_days(mid1) >= compute_total_days(mid2):
            left = mid1
        else:
            right = mid2
            
    answer = min(compute_total_days(x) for x in range(left, right + 1))
    print(answer)

if __name__ == "__main__":
    main()

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