実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 118

問題概要

ある市では $N$ 種類のゴミを定期的に収集しており、 $i$ 種類目のゴミは、日付を $q_i$ で割ったあまりが $r_i$ の日に収集される。次の $Q$ 個のクエリを処理せよ。

$j$ 番目のクエリ : $d_j$ 日に $t_j$ 種類目のゴミが出たときに、次にそれが収集される日を出力せよ。ただし、 $i$ 種類目のゴミが出た日が $i$ 種類目のゴミが回収される日であった場合、そのゴミは同じ日に収集されるとする。

制約

入力はすべて整数。
$1 \leq N, Q \leq 100$
$0 \leq r_i \lt q_i \leq 10^9$
$1 \leq d_j \leq 10^9$

考察

$m_j := d_j \mod q_{t_j}$ とすれば、 $r_{t_j} - m_j$ がゴミ $t_j$ を出してから回収されるまでの日数となる。つまり、これを $d_j$ に加えたものが各クエリの答えとなる。

...しかし、よく考えると $r_{t_j} - m_j$ は負になりうる (サンプルケース1の最後のクエリとか) 。

これを無理やり正にするために、 $0 \leq r_i \lt q_i$ であることを利用して $(r_{t_j} - m_j + q_i) \mod q_i$ とし、これを $d_j$ に加えればよい。これにより各クエリは $O(1)$ で処理できるので、全体の計算量は $O(Q)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<ll> q(N), r(N);
    rep(i, 0, N) cin >> q[i] >> r[i];
    int Q;
    cin >> Q;

    while (Q--)
    {
        ll t, d;
        cin >> t >> d;
        t--;

        ll m = d % q[t];
        cout << d + ((r[t] - m + q[t]) % q[t]) << endl;
    }
}