Codeforces Round #188 (Div. 1) / 317A Perfect Pair(数学&优化)

59 阅读 0 评论 39 点赞

我是靠谱客的博主冷静猫咪，最近开发中收集的这篇文章主要介绍Codeforces Round #188 (Div. 1) / 317A Perfect Pair(数学&优化)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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 x, y 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 x, y and m ( - 10¹⁸ ≤ x, y, m ≤ 10¹⁸).

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preffered to use the cin, cout 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异号的情况可以优化。

优化后复杂度：O(log m)

完整代码：

/*30ms,0KB*/

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

int main(void)
{
	__int64 x, y, m, count = 0;
	scanf("%I64d%I64d%I64d", &x, &y, &m);
	if (m <= max(x, y))
		printf("0");
	else
	{
		if (x <= 0 && y <= 0)
			printf("-1");
		else
		{
		    ///x,y异号的情况可以优化一下
			if (x < 0 && y > 0){
			    count = ceil((double) - x / y);
                x+=count*y;
			}
			else if (x > 0 && y < 0){
				count = ceil((double) - y / x);
				y+=count*x;
			}
			while (max(x, y) < m)
			{
				if (x < y)
					x += y;
				else
					y += x ;
				++count;
			}
			printf("%I64d", count);
		}
	}
	return 0;
}