# Codeforces 712C Memory and De-Evolution

C. Memory and De-Evolution

time limit per test:2 seconds

memory limit per test:256 megabytes

input:standard input

output:standard output

Memory is now interested in the de-evolution of objects, specifically triangles. He starts with an equilateral triangle of side length x, and he wishes to perform operations to obtain an equilateral triangle of side length y.

In a single second, he can modify the length of a single side of the current triangle such that it remains a non-degenerate triangle (triangle of positive area). At any moment of time, the length of each side should be integer.

What is the minimum number of seconds required for Memory to obtain the equilateral triangle of side length y?

Input

The first and only line contains two integers x and y (3 ≤ y < x ≤ 100 000) — the starting and ending equilateral triangle side lengths respectively.

Output

Print a single integer — the minimum number of seconds required for Memory to obtain the equilateral triangle of side length y if he starts with the equilateral triangle of side length x.

Examples

Input

`6 3`

Output

`4`

Input

`8 5`

Output

`3`

Input

`22 4`

Output

`6`

Note

In the first sample test, Memory starts with an equilateral triangle of side length 6 and wants one of side length 3. Denote a triangle with sides a, b, and c as (a, b, c). Then, Memory can do

.

In the second sample test, Memory can do

.

In the third sample test, Memory can do:

.

【题意】 现有边长为x的等边三角形,Memory想要将其变成边长为y的等边三角形

【类型】 贪心,逆推

【分析】

【时间复杂度&&优化】 O(n)

``` 1 #include <bits/stdc++.h>
2 using namespace std;
3 int main()
4 {
5     int s[3];
6     int x,y,i;
7     while(cin>>x>>y)
8     {
9         int ans=0;
10         s[0]=s[1]=s[2]=y;
11         for(i=0;s[0]<x||s[1]<x||s[2]<x;i++)
12         {
13             s[0]=s[1]+s[2]-1;
14             sort(s,s+3);
15             ans++;
16         }
17         cout<<ans<<endl;
18     }
19     return 0;
20 }```

经过学长的提醒，我想出了另外一种方法，这样更简单！

``` 1 #include <bits/stdc++.h>
2 using namespace std;
3 int main()
4 {
5     int s[3];
6     int x,y,i;
7     while(cin>>x>>y)
8     {
9         s[0]=s[1]=s[2]=y;
10         for(i=0;s[0]<x||s[1]<x||s[2]<x;i++)
11             s[i%3]=s[(i+1)%3]+s[(i+2)%3]-1;//从小变大，每次都是最小边变另外两边的和减1,s[0],s[1],s[2]依次变就能保证，变时候一定是三个里面最小的
12         cout<<i<<endl;
13     }
14     return 0;
15 }```

``` 1 #include <bits/stdc++.h>
2 using namespace std;
3 int main()
4 {
5     int s[3];
6     int x,y,i;
7     while(cin>>x>>y)
8     {
9         s[0]=s[1]=s[2]=y;
10         int ans=0;
11         while(s[0]!=x||s[1]!=x||s[2]!=x)
12         {
13             sort(s,s+3);
14             s[0]=min(s[1]+s[2]-1,x);
15             ans++;
16         }
17         cout<<ans<<endl;
18     }
19     return 0;
20 }```

780 篇文章62 人订阅

0 条评论

## 相关文章

3246

3396

### 资源竞速（Race Conditions）和临界区（Critical Sections）临界区临界区的资源竞速避免资源竞速临界区的吞吐量

critical section是每个线程中访问临界资源的那段代码，不论是硬件临界资源，还是软件临界资源，多个线程必须互斥地对它进行访问。 资源竞速就是可能在...

1030

1201

### Python日志输出——logging模块

http://blog.csdn.net/chosen0ne/article/details/7319306

1221

2653

7257

1072

2260

962