Overview

This is a problem where \(N\) types of sweets are packed into boxes by type, and we need to find the minimum total number of boxes. Each box can only contain sweets of the same type, and can hold at most \(K\) sweets.

Analysis

The key point for solving this problem is the constraint that “sweets of different types cannot be placed in the same box.”

Because of this constraint, we can independently calculate “the minimum number of boxes needed to transport each type” and sum them all up to get the answer. Since leftover space in a box cannot be shared with sweets of other types, each type can be considered independently.

Specifically, if the total number of sweets of a certain type is \(S = A_i + B_i\), the number of boxes required is as follows: - When \(S = 0\): \(0\) boxes - When \(S > 0\): The value obtained by dividing \(S\) by \(K\) and rounding up (\(\lceil S / K \rceil\))

For example, when \(K = 10\) and there are \(23\) sweets in total, they can be split into groups of 10, 10, and 3, requiring a minimum of \(3\) boxes. This matches the result of rounding up \(23 \div 10 = 2.3\).

Algorithm

1. Initialize a variable total_boxes to \(0\) to store the answer.
2. For each type \(i = 1, 2, \dots, N\), repeat the following:
   • Add Takahashi’s portion \(A_i\) and Aoki’s portion \(B_i\) to get the total \(S = A_i + B_i\).
   • If \(S > 0\), calculate the number of boxes needed \(\lceil S / K \rceil\) and add it to total_boxes.
3. Output the final total_boxes.

Trick for Ceiling Division

Integer division (/ or //) in programming languages typically performs “floor division” (rounding down). To compute the ceiling division \(\lceil S / K \rceil\) using only integer arithmetic, the following formula is commonly used: $\((S + K - 1) // K\)$ This allows us to obtain the exact ceiling value while avoiding floating-point precision issues.

Complexity

• Time complexity: \(O(N)\) Since each of the \(N\) types of sweets is processed exactly once, the computation finishes in time proportional to the input size.
• Space complexity: \(O(1)\) or \(O(N)\) It is \(O(1)\) if the input is processed sequentially. It becomes \(O(N)\) if all input is read at once into a list or similar structure.

Implementation Notes

• Handling large numbers: The total number of sweets and boxes can become very large. Python natively supports arbitrary-precision integers, but when using other languages (such as C++), the total values can exceed the range of 32-bit integers, so 64-bit integer types such as long long must be used.

• Fast input: Since \(N\) can be as large as \(2 \times 10^5\), which is relatively large, in Python it is advisable to use sys.stdin.read().split() or sys.stdin.readline to read input quickly.

  Source Code

import sys

def main():
    # 標準入力からすべてのデータを取得し、スペース・改行で分割する
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了
    if not input_data:
        return
    
    # イテレータを使用してデータを順番に取得する
    it = map(int, input_data)
    
    # N: お菓子の種類数, K: 1箱に入れられる最大個数
    try:
        N = next(it)
        K = next(it)
    except StopIteration:
        return
    
    total_boxes = 0
    
    # 各種類のお菓子について、必要な箱の数を計算する
    for _ in range(N):
        try:
            A = next(it)
            B = next(it)
            
            # 合計個数
            S = A + B
            
            # 合計が0個の場合は箱は不要
            if S > 0:
                # 必要な箱の数は ceil(S / K)
                # 整数演算のみで求める場合は (S + K - 1) // K
                total_boxes += (S + K - 1) // K
        except StopIteration:
            break
            
    # 結果を出力
    print(total_boxes)

if __name__ == '__main__':
    main()

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