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

131 阅读 0 评论 87 点赞

我是靠谱客的博主冷静猫咪，这篇文章主要介绍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
1 2 5

     output 
   
复制代码2
2

     input 
   
复制代码-1 4 15
-1 4 15

     output 
   
复制代码4
4

     input 
   
复制代码0 -1 5
0 -1 5

     output 
   
复制代码-1-1

注意x，y异号的情况可以优化。

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

完整代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*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;
}