問題一覧 > 通常問題

No.2921 Seated in Classroom

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 192
作問者 : kusirakusira / テスター : 👑 loop0919 hirayuu_yc nouka28 tnodino mymelochan Nyaa Uruzu
1 ProblemId : 11321 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-10-12 14:06:11

問題文

第3回緑以下コンテストは青山学院大学青山キャンパスの教室で開催されます。

この教室には 1010010^{100}44 列の長机があります。各長机には席が 22 つあり、それぞれの椅子に 11 人ずつ座ることができます(下図参照)。

また、左右両端にはコンセント口があり、一番外側の列の長机にはコンセント口からコードを伸ばすことができます。

コンテストの参加者はそれぞれパソコンを持参しますが、一部の参加者はパソコンを充電する必要があります。

パソコンを充電する必要がある参加者はコンセント口からコードを伸ばしてパソコンに接続するため、一番外側の長机の席に座らなければなりません。

パソコンを充電する必要がない参加者はどの席にも座ることができます。

パソコンを充電する必要がある参加者が NN 人、パソコンを充電する必要がない参加者が MM 人います。

くしら君は参加者がなるべく前に詰めるように着席させたいと考えています。

適切に参加者を着席させたときの「参加者たちが座っている行番号の最大値」の最小値はいくつですか。

なお、全参加者が椅子に座れることは制約により保証されます。

厳密に述べます。

長さ N+MN+M の数列 AA があります。ii 番目 (1iN+M)(1 \le i \le N+M) の参加者が座っている席がある長机の位置が上から xx 行目、左から yy 列目であるとき、Ai=xA_i = x です。

数列 AA の最大値の最小値を求めてください。

TT 個のテストケースに答えてください。

制約

  • 1T2×1051 \le T \le 2 \times 10^5
  • 1N,M1091 \le N,M \le 10^{9}
  • 入力は全て整数

入力

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

TT
test1\text{test}_1
test2\text{test}_2
\vdots
testT\text{test}_T

testi\text{test}_iii 番目のテストケースを表し、各テストケースは以下の形式で与えられる。

N MN\ M

出力

TT 行出力せよ。ii 行目には ii 番目のテストケースに対する答えを出力せよ。

サンプル

サンプル1
入力
5
6 7
5 14
18 6
1 18
9 17
出力
2
3
5
3
4

11 つ目のテストケースについて、以下のように着席することで、22 行目以内に全員を着席させることができます。
黄五角形はパソコンを充電する必要がある参加者、緑丸はパソコンを充電する必要がない参加者を表します。

サンプル2
入力
6
7764 52463
1658 7836
657456 647734
64567 734634
476 857467
48756587 675761
出力
7529
1187
164364
99901
107243
12189147

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