問題概要
A,Bの2数が与えられる。これらに対し、以下の操作を行う。
- 片方を選ぶ
- n回目の操作だとしたら、選んだ数へnを足す
A,Bを等しくするには最小で何回の操作が必要か答えよ。入力はT個与えられる。
制約
- 1 ≦ A,B ≦ 109
- 1 ≦ t ≦ 100
解答
この問題は以下のように言い換えられる。
- AとBの差の絶対値をdiffとする
- 1からnのうちいくつかをマイナスにする
- それらの総和をdiffにする
たとえば差の絶対値が5のときは次のようにすれば良い。
1 + 2 + 3 + 4 + 5 = 15 1 + 2 + 3 + 4 - 5 = 5
この観察から以下が言える。
- 最低でも1からnまでの総和はdiff以上でなければならない
- あるmをマイナスにすると、総和は2m減る
ここまで分かればおおよその方針ができる。まず、diff以上となるnを探す。もし、1からnの総和とdiffの偶奇が等しければnが答え。等しくなければ偶奇が等しくなるまでnを増やす。
証明
まず、1から(n-1)の総和をS'、1からnまでの総和をSとする。また、S' < diff ≦ Sとする。
S' + n = Sより、S' < diff ≦ S' + nである。
さらに、 0 < diff - S' ≦ nである。
ここでdiff - S' = 2kとする。0 < 2k ≦ nよりkは1からnに含まれている。よってkのみマイナスとすれば総和がdiffと一致する。
もしdiff - S'が奇数ならば、どのようにしても総和とdiffは一致しない。これを解消できる最小のnが答えなのは明らか。
