AI工具人
提示词工程师

codeforces 317 A Perfect Pair


A. Perfect Pair


time limit per test


1 second


memory limit per test


256 megabytes


input


standard input


output


standard output


Let us call a pair of integer numbers m-perfect, if at least one number in the pair is greater
than or equal to m. Thus, the pairs (3, 3) and (0, 2) are 2-perfect while the pair (-1, 1) is not.


Two integers xy are written on the blackboard.
It is allowed to erase one of them and replace it with the sum of the numbers, (x + y).


What is the minimum number of such operations one has to perform in order to make the given pair of integers m-perfect?


Input


Single line of the input contains three integers xy and m ( - 1018 ≤ xym ≤ 1018).


Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preffered to use the cincout streams
or the %I64dspecifier.


Output


Print the minimum number of operations or "-1" (without quotes), if it is impossible to transform the given pair to the m-perfect
one.


Sample test(s)


input

1 2 5


output

2


input

-1 4 15


output

4


input

0 -1 5


output

-1

题意:

   给你x 和 y 还有M,让你通过变换x和y,使得其中一个大于或者等于m,变换的方法就是自身加上另外一个,如果可以通过若干步使满足条件,输出最小的步数,否则输出-1。

思路:

    如果xy小于0且m大于0,那么肯定不可能变换到m,如果 x < m && y < m && x+y<0也肯定没办法达到m。

    我先排除了输出-1的,然后再考虑如何计算最小的步数。我们主要在每一步中最小一个加上另一个就可以了,这是朴素的求法,但可能出现这样的情况 比如 -100000000 1 10000000   这样的话会循环100000000多次,肯定超时,所以我们要加快速度。

代码:

//cf 317 A
//2013-06-22-16.43
#include <iostream>

using namespace std;

int main()
{
    __int64 x, y, m;
    while (cin >> x >> y >> m)
    {
        if (x <= 0 && y <= 0)
        {
            if (x < m && y < m && x+y <= 0)
            {
                cout << "-1" << endl;
                continue;
            }
        }
        __int64 ans = 0;
        int cnt = 0;
        while (x < m && y < m)
        {
            if (x > y)
            {
                __int64 t = x; x = y; y = t;
            }
            if (x < 0 && y > 0 && -x > y)
            {
                ans += (-x)/y;
                x += (-x)/y * y;

            }
            else
            {
                x = x+y;
                ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}


赞(0) 打赏
未经允许不得转载:XINDOO » codeforces 317 A Perfect Pair

评论 抢沙发

觉得文章有用就打赏一下文章作者

非常感谢你的打赏,我们将继续给力更多优质内容,让我们一起创建更加美好的网络世界!

支付宝扫一扫

微信扫一扫