TopCoder SRM677_Div1 : DoubleOrOneEasy
TopCoder Statistics - Problem Statement
問題
入力として a, b, newA, newBが与えられる。
以下、2つの操作を自由に行えるとしa,bをnewA,newBに変換する最小操作回数を、どう操作しても不可能な場合は-1を返せ。 という問題。
- a, bそれぞれに1を足す
- a, bそれぞれの値を2倍する
例として、入力が以下のような場合を考える。
a = 100, b = 1000, newA = 204, newB = 2004
この場合は3回の操作が最適となる。
100, 1000
↓ (1を足す)
101, 1001
↓ (1を足す)
102, 1002
↓ (2倍する)
204, 2004
解法
それぞれ値の取る範囲が~
と大きいため、ナイーブに全通り試すことはできない。
考察するとなるべく1を足した後に2倍した方が解に近づきやすくなるため、
newA,newBをa,bに戻すという逆の操作で、newAとnewBが2で割りきれる時は割り
割り切れない時は1引いていけばよい事が分かる。
その過程で都度a,bとの距離を確認すれば良い。
途中で一方が偶数/他方が奇数となった場合は、2で割る操作ができなくなるためループを打ち切る。
本番ではこの判定を入力後にしか行っていなかったためHackされてしまった。
計算量は となる。
