問題一覧 > 通常問題

No.3260 岩井スターグラフ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 155
作問者 : 👑 loop0919 / テスター : 高橋ゆに あじゃじゃ DeltaStruct Andrew8128 kazuppa bolero elphe のらら こめだわら よには yimiya（いみや）
ProblemId : 12258 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-09-06 11:59:30

問題文

以下の手続きで作られた無向グラフを、腕の本数 $X$ 、腕の長さ $Y$ の岩井スターグラフと定義します。

  • $0$ から $XY$ までの番号がそれぞれ割り当てられた $XY + 1$ 個の頂点を用意する。
  • $i = 0, 1, \cdots, X - 1$ の順に以下の操作を繰り返す。
    • 頂点 $iY + 1$ と頂点 $iY + 2$ 、頂点 $iY + 2$ と頂点 $iY + 3$ 、 $\cdots$ 、頂点 $iY + Y - 1$ と頂点 $iY + Y$ をそれぞれ無向辺で結ぶ。
    • 頂点 $0$ と頂点 $iY + 1$ を無向辺で結ぶ。

この岩井スターグラフには $N$ 人の岩井星人さんがおり、$k$ 番目 $(1 \leq k \leq N)$ の岩井星人さんは頂点 $U_k$ から頂点 $V_k$ まで辺を通って移動します。

各岩井星人さんについて、移動が完了するまでに通る辺の本数の最小値をそれぞれ求めてください。

制約

  • $1 \leq X, Y \leq 10^6$
  • $1 \leq N \leq 2 \times 10^5$
  • $0 \leq U_i < V_i \leq XY$
  • 入力で与えられる値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$X$ $Y$ $N$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_N$ $V_N$

出力

$N$ 行出力せよ。 $k$ 行目には、$k$ 番目の岩井星人さんの移動が完了するまでに通る辺の本数の最小値を出力せよ。

サンプル

サンプル1
入力
4 3 3
0 3
11 12
3 4
出力
3
1
4

腕の本数 $4$ 、腕の長さ $3$ の岩井スターグラフは次のようになっています。


例えば、$1$ 番目の岩井星人さんは頂点 $0 \to 1 \to 2 \to 3$ の順に通ることで移動が完了します。このとき通る辺の本数は最小で $3$ 本です。

サンプル2
入力
1000000 1000000 2
1000000 1000000000000
998244353 1000000007
出力
2000000
244360

頂点の番号が $32 ~ \mathrm{bit}$ 整数型の範囲に収まらない場合があることに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。