Problem Overview

For each of the \(N\) documents, compute the number of sheets needed to print \(A_i\) pages, where each sheet holds \(B_i\) pages. The last sheet may contain fewer than \(B_i\) pages.

Algorithm

The number of sheets required for document \(i\) is the ceiling of \(A_i\) divided by \(B_i\):

\[\left\lceil \frac{A_i}{B_i} \right\rceil\]

Using integer arithmetic, this can be computed as:

\[\left\lceil \frac{A_i}{B_i} \right\rceil = \frac{A_i + B_i - 1}{B_i} \quad (\text{integer division})\]

Compute this value for each document and print it on its own line.

Proof of Correctness

Lemma: \(x\) sheets can hold at most \(x B_i\) pages. The required number of sheets \(x\) is the smallest non-negative integer satisfying \(x B_i \geq A_i\).

Proof: Each sheet holds at most \(B_i\) pages, so \(x\) sheets hold at most \(x B_i\) pages. Printing all \(A_i\) pages is possible if and only if \(x B_i \geq A_i\), and the smallest such \(x\) is the answer.

Theorem: \((A_i + B_i - 1) / B_i\) (integer division, truncating) equals the smallest non-negative integer \(x\) with \(x B_i \geq A_i\).

Proof: Write \(A_i = q B_i + r\) with \(0 \leq r < B_i\).

• If \(r = 0\): \((A_i + B_i - 1) / B_i = (q B_i + B_i - 1) / B_i = q + (B_i - 1)/B_i = q\), since \(0 \leq B_i - 1 < B_i\). Since \(q B_i = A_i\), the minimum solution is \(x = q\), matching.
• If \(r > 0\): \((A_i + B_i - 1) / B_i = (q B_i + r + B_i - 1) / B_i = q + (r + B_i - 1)/B_i\). Since \(1 \leq r \leq B_i - 1\), we have \(B_i \leq r + B_i - 1 \leq 2B_i - 2 < 2B_i\), so this equals \(q + 1\). Meanwhile \(q B_i < A_i < (q+1) B_i\), so the minimum solution is \(x = q + 1\), matching.

Hence the algorithm outputs the correct number of sheets for every document.

Complexity

• Time: \(O(N)\) — constant work per document.
• Space: \(O(1)\) auxiliary space if input is processed streaming (the C++ implementation does this; the Python implementation reads all input at once, using \(O(N)\)).

Tie-breaking

Each document’s answer is uniquely determined, so there is no tie-breaking. The output simply writes the result for document \(i\) on line \(i\), in input order.