問題の概要

\(N\) 件の資料それぞれについて、\(A_i\) ページを 1 枚あたり \(B_i\) ページずつ印刷するときに必要な用紙の枚数を求める。最後の 1 枚は \(B_i\) ページに満たなくてもよい。

アルゴリズム

資料 \(i\) に必要な用紙の枚数は、\(A_i\) を \(B_i\) で割った値の切り上げ、すなわち

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

である。整数演算では、これは次の式で計算できる。

\[\left\lceil \frac{A_i}{B_i} \right\rceil = \frac{A_i + B_i - 1}{B_i} \quad (\text{整数除算})\]

各資料についてこの値を計算し、1 行ずつ出力すればよい。

正当性の証明

補題: \(x\) 枚の用紙で印刷できる最大ページ数は \(x B_i\) である。必要な枚数 \(x\) は \(x B_i \geq A_i\) を満たす最小の非負整数である。

証明: \(x\) 枚の用紙にはそれぞれ最大 \(B_i\) ページ印刷できるので、合計で最大 \(x B_i\) ページ印刷できる。\(A_i\) ページすべてを印刷するには \(x B_i \geq A_i\) が必要十分であり、そのような最小の \(x\) が答えである。

定理: \((A_i + B_i - 1) / B_i\)（整数除算、切り捨て）は \(x B_i \geq A_i\) を満たす最小の非負整数 \(x\) に等しい。

証明: \(A_i = q B_i + r\)（\(0 \leq r < B_i\)）と書く。

• \(r = 0\) のとき: \((A_i + B_i - 1) / B_i = (q B_i + B_i - 1) / B_i = q + (B_i - 1) / B_i = q\)（\(0 \leq B_i - 1 < B_i\) より）。また \(q B_i = A_i\) なので \(x = q\) が最小解であり一致する。
• \(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\)。\(1 \leq r \leq B_i - 1\) より \(B_i \leq r + B_i - 1 \leq 2 B_i - 2 < 2 B_i\) なので、この値は \(q + 1\)。一方 \(q B_i < A_i < (q+1) B_i\) より最小解は \(x = q + 1\) であり一致する。

よってアルゴリズムは各資料について正しい枚数を出力する。

計算量

• 時間計算量: \(O(N)\)（各資料につき定数時間）
• 空間計算量: 入力を逐次読んで処理すれば \(O(1)\) の補助空間（C++ 実装は逐次処理、Python 実装は入力全体を読むため \(O(N)\)）

タイブレーク

各資料の答えは一意に定まるため、タイブレークは存在しない。出力は入力順に \(i\) 行目へ \(i\) 件目の結果を書くだけである。