Overview

For each document, we calculate the number of pages \(A_i\) divided by the number of pages per sheet \(B_i\), rounded up to the nearest integer.

Analysis

Let \(q\) be the quotient and \(r\) be the remainder when \(A_i\) is divided by \(B_i\). We can express this as:

\(A_i = qB_i + r \quad (0 \leq r < B_i)\)

First, we can print \(B_i\) pages on each of the \(q\) sheets. Then, the number of required sheets depends on whether there are any leftover pages:

• If \(r = 0\): All pages can be printed, so \(q\) sheets are sufficient.
• If \(r > 0\): An additional \(1\) sheet is needed to print the remaining \(r\) pages. Since \(r < B_i\), all remaining pages can be printed on this single additional sheet.

For example, if \(A_i = 10\) and \(B_i = 4\), the quotient is \(2\) and the remainder is \(2\). With \(2\) sheets, only \(8\) pages can be printed, so \(3\) sheets are required.

If you only output the result of integer division, you will be short by \(1\) sheet whenever there is a remainder, resulting in WA. Therefore, if the remainder is not \(0\), we add \(1\) to the quotient.

Note that counting sheet by sheet would also run well within the time limit under the given constraints, but using the quotient and remainder allows us to find the answer for each document in constant time.

Algorithm

1. Read the number of documents \(N\).
2. For each document, perform the following steps:
   1. Read the number of pages \(A_i\) and the number of pages per sheet \(B_i\).
   2. Set the initial value of the required number of sheets to the quotient obtained from integer division, \(A_i / B_i\).
   3. If the remainder of \(A_i\) divided by \(B_i\) is not \(0\), add \(1\) to the number of sheets.
   4. Output the calculated number of sheets.

For each document, this ensures that enough sheets are provided to print all pages without adding unnecessary sheets, thereby finding the minimum required number of sheets.

Complexity

• Time complexity: \(O(N)\)
  For each document, operations such as division and modulo are performed a constant number of times.
• Space complexity: \(O(1)\)
  Since each document is processed and output one by one, no arrays or additional storage are needed.

Implementation Details

• The reference code is in C++. For positive integers, / computes the quotient rounded down, and % computes the remainder.

• Add \(1\) to sheets only when a % b != 0. Be careful not to add it when it divides evenly.

• Even when \(A_i < B_i\), the quotient will be \(0\) and the remainder will be \(A_i\), correctly yielding \(1\) sheet.

• Output the answer for each document on a new line.

  Source Code

// 問題文から独立に実装: 商を取り、余りがあれば 1 枚追加
#include <iostream>
int main() {
    int n; std::cin >> n;
    while (n--) {
        int a, b; std::cin >> a >> b;
        int sheets = a / b;
        if (a % b != 0) sheets++;
        std::cout << sheets << "\n";
    }
}

This editorial was generated by gpt-6-astra-medium.