Overview

For each document, find the value obtained by dividing the number of pages by the number of pages per sheet and rounding up to the nearest integer.

Analysis

Let \(A\) be the number of pages in a document, and let \(B\) be the number of pages that can be printed on a single sheet of paper.

For example, if \(A=10\) and \(B=3\), \(3\) sheets of paper can only accommodate \(9\) pages. Since an additional sheet is required for the remaining \(1\) page, the answer is \(4\) sheets.

Because integer division A // B truncates the fractional part (rounds down), directly using it will leave you \(1\) sheet short when \(A\) is not divisible by \(B\), resulting in a wrong answer. Therefore, the required number of sheets is:

• If \(A\) is divisible by \(B\): \(A // B\) sheets
• If \(A\) is not divisible by \(B\): \(A // B + 1\) sheets

This ceiling division can be computed without conditional branches using the following formula:

\(\displaystyle \left\lceil \frac{A}{B} \right\rceil = \left\lfloor \frac{A+B-1}{B} \right\rfloor\)

In Python, this can be written as (A + B - 1) // B.

Let us verify why this formula holds. Let \(A = qB + r\) (\(0 \leq r < B\)):

• If \(r = 0\), then \(A + B - 1 = qB + (B - 1)\), so integer division by \(B\) yields \(q\).
• If \(r > 0\), then \(A + B - 1 = (q + 1)B + (r - 1)\), so integer division by \(B\) yields \(q + 1\).

Simulating sheet by sheet to count the required number would also easily run within the time limit given these constraints. However, using the formula above allows us to determine the answer for each document in a single calculation.

Algorithm

1. Read the number of documents \(N\).
2. For each document, perform the following:
   • Read the number of pages \(A_i\) and the number of pages per sheet \(B_i\).
   • Compute (A_i + B_i - 1) // B_i.
   • Convert the result to a string and append it to an output list.
3. Join the elements of the list with newlines and print them in the order of input.

Complexity

• Time Complexity: \(O(N)\)
  A constant-time calculation is performed for each document.
• Space Complexity: \(O(N)\)
  The provided code stores the entire input and the output list in memory.

Implementation Notes

• In Python, // performs integer division. Since / results in a floating-point number, use // for this problem.

• Make sure to enclose the addition in parentheses, as in (a + b - 1) // b.

• When \(A_i < B_i\), \(1\) sheet is still required. This formula correctly yields \(1\).

• In the provided code, the entire input is split using split(). Using \(0\)-based indexing for \(i\), data[1 + 2 * i] corresponds to the number of pages, and data[2 + 2 * i] corresponds to the number of pages per sheet.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    out = []
    for i in range(n):
        a = int(data[1 + 2 * i])
        b = int(data[2 + 2 * i])
        out.append(str((a + b - 1) // b))
    sys.stdout.write("\n".join(out) + "\n")

main()

---

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