概要

各資料について、ページ数 \(A_i\) を用紙 \(1\) 枚あたりのページ数 \(B_i\) で割り、端数を切り上げた値を求めます。

考察

\(A_i\) を \(B_i\) で割った商を \(q\)、余りを \(r\) とすると、

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

と表せます。

まず、\(q\) 枚の用紙にそれぞれ \(B_i\) ページずつ印刷できます。その後、余りのページがあるかどうかで必要な枚数が変わります。

• \(r = 0\) の場合：すべて印刷できるので、\(q\) 枚で十分です。
• \(r > 0\) の場合：残った \(r\) ページを印刷するために、もう \(1\) 枚必要です。\(r < B_i\) なので、追加の \(1\) 枚ですべて印刷できます。

例えば、\(A_i = 10\)、\(B_i = 4\) の場合、商は \(2\)、余りは \(2\) です。\(2\) 枚では \(8\) ページしか印刷できないため、必要な用紙は \(3\) 枚です。

整数の割り算の結果だけを出力すると、余りがある場合に \(1\) 枚不足して WA になります。 そこで、余りが \(0\) でなければ商に \(1\) を加えます。

なお、用紙を \(1\) 枚ずつ数える方法でも今回の制約では十分間に合いますが、商と余りを使えば各資料の答えを一定時間で求められます。

アルゴリズム

1. 資料の件数 \(N\) を読み込みます。
2. 各資料について、次の処理を行います。
   1. ページ数 \(A_i\) と、用紙 \(1\) 枚あたりのページ数 \(B_i\) を読み込みます。
   2. 整数の割り算で得られる商 \(A_i / B_i\) を、必要な枚数の初期値とします。
   3. \(A_i\) を \(B_i\) で割った余りが \(0\) でなければ、枚数に \(1\) を加えます。
   4. 求めた枚数を出力します。

各資料について、印刷できるだけの用紙を確保しつつ、不要な用紙は追加しないため、必要な最小枚数が求まります。

計算量

• 時間計算量: \(O(N)\)
  各資料について、割り算や余りの計算などを一定回数行います。
• 空間計算量: \(O(1)\)
  資料を \(1\) 件ずつ処理して出力するため、配列などは不要です。

実装のポイント

• 提示コードは C++ です。正の整数同士の / は小数部分を切り捨てた商を、% は余りを求めます。

• a % b != 0 のときだけ、sheets に \(1\) を加えます。割り切れる場合に追加しないよう注意してください。

• \(A_i < B_i\) の場合も、商が \(0\)、余りが \(A_i\) となるため、正しく \(1\) 枚と求められます。

• 答えは資料ごとに改行して出力します。

  ソースコード

// 問題文から独立に実装: 商を取り、余りがあれば 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";
    }
}

---

この解説は gpt-6-astra-medium によって生成されました。