Codeforces #188 Div2 C "Perfect Pair"

問題

http://codeforces.com/contest/318/problem/C

訳

整数のペアでどちらかの数がm以上であれば、そのペアをm-perfectと呼ぶことにした。例えば(3, 3)や(0, 2)は2-perfectであるば、(-1, 1)はそうではない。

黒板に、２つの整数x, yが書かれている。これらのうち１つを消し、そして(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;
}