Overview

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

Analysis

Let \(A\) be the number of pages and \(B\) be the number of pages per sheet of paper.

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

If we simply use integer division A // B, the remainder is truncated, so we will be short by \(1\) sheet when \(A\) is not divisible by \(B\). On the other hand, if we always add \(1\), we will have \(1\) sheet too many when it is divisible.

Therefore, the required number of sheets is as follows:

• When \(A\) is divisible by \(B\): \(A \div B\) sheets
• When it is not divisible: the result of integer division plus \(1\) sheets

This can be expressed as \(\lceil A/B \rceil\), which represents \(A/B\) rounded up.

Although counting sheets by adding them one by one would easily run in time under the given constraints, ceiling division allows us to find the answer for each document in a single calculation.

Algorithm

1. Read the number of documents \(N\).
2. Repeat the following process \(N\) times:
   • Read the number of pages \(A\) and the number of pages per sheet \(B\).
   • Calculate \(\lceil A/B \rceil\) using -(-A // B) and print it.

In Python, // is an operator that rounds down towards negative infinity. Therefore, we can utilize the following identity:

\(\lceil A/B \rceil = -\lfloor -A/B \rfloor\)

For example, when \(A=10\) and \(B=3\), -10 // 3 results in -4. Negating its sign gives the required number of sheets, 4.

Complexity

• Time complexity: \(O(N)\)
  A constant-time calculation is performed for each document.
• Space complexity: \(O(1)\)
  Since the documents are processed one by one, there is no need to store the information for all documents.

Implementation Notes

• In Python, // on negative numbers does not simply truncate the fractional part. For example, -10 // 3 evaluates to -4, not -3.

• When \(A\) and \(B\) are positive integers as in this problem, (A + B - 1) // B can also be used to achieve the same ceiling division.

• This can be computed accurately using only integer operations without using floating-point numbers.

  Source Code

# 問題文から独立に実装
n = int(input())
for _ in range(n):
    a, b = map(int, input().split())
    print(-(-a // b))

---

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