Codeforces #188 Div2 C "Perfect Pair"
問題
http://codeforces.com/contest/318/problem/C
訳
整数のペアでどちらかの数がm以上であれば、そのペアをm-perfectと呼ぶことにした。例えば(3, 3)や(0, 2)は2-perfectであるば、(-1, 1)はそうではない。
黒板に、2つの整数x, yが書かれている。これらのうち1つを消し、そして(x + y)という数で置き換えることができる。
あたえられた整数のペアをm-perfectとするために、最小何回上記の操作を実行すればよいかを出力せよ。
制約
-10^18 <= x, y, m <= 10^18
考えた事
まずx, yどちらかがmより大きければ0でよい。
x, yが両方とも0以下であれば、操作で数を大きくする事ができないので-1でよい。
逆にそうでなければ操作によって、必ずmに到達する事ができる。
操作で置き換えるのは小さいほうの数でよいので、フィボナッチ数列的な感じでやっていけばよい。(1, 0)から10^18までどのくらい操作が必要か試したところ、90回ぐらいやればよさそうなので、計算量的には全く問題ない。
(x > y)として、yがマイナスだったら、xを何回足せばyが0以上なるかを出し、それを答えに足した上で上記の操作をシミュレートすればよい。
ソースコード
int main() { long long x, y, m; cin >> x >> y >> m; if( x < y ) swap( x, y ); // すでにでかい if( x >= m ){ cout << 0 << endl; return 0; } // 両方とも0以下 if( x <= 0 && y <= 0 ){ cout << -1 << endl; return 0; } long long ans = 0; // yがマイナスだったら・・・ if( y < 0 ){ long long t = abs( y ); long long num = t / x + (t % x ? 1 : 0); ans = num; y += x * num; } // フィボナッチ的なアレ while( x < m ){ y += x; swap( x, y ); ans++; } cout << ans << endl; }