[原创]codeforces 370div.2 Ｃ　Memory and De-Evolution［逆向思维］【思维】

2016-09-11 13:36:33 Tabris_ 阅读数：475

博客爬取于2020-06-14 22:43:25
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52503620

题目链接：http://codeforces.com/contest/712/problem/C

--------------------------.
C. Memory and De-Evolution
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard 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:

-----------------------------------------------.

题目大意 : 就是给你两个数 一大一小 分别是两个正三角形 问你把大的正三角形变成小的三角形的最少操作次数
操作的要求如下
1.每次只能对三角形的一条边操作
2.每次操作后的三条边都能构成三角形

解题思路 :
开始正着想 只能过样例
后来在队友的提示下 采取逆向思维
题目不是从大的变到小的么
我们求从小的变到大的的最小操作次数 反过来操作就是大的变小的了

然后就是每次把最小的那一条边 变成 其他两边和-1 (-1是因为要构成三角形)

然后暴力就行了

附本题代码
-----------------------------.

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
43
44
45
46
47
48
# include <bits/stdc++.h>
using namespace std;
typedef long long int LL ;
# define INF 0x3f3f3f3f
# define pb push_back

# define lalal puts("*******");
/*************************************/

const int MOD = 1e9+7;
const int M = 1e5+10;

int main()
{
    ios::sync_with_stdio(false);
    LL n,x,y;
    int a[3];
    while(cin>>x>>y)
    {
        if(x==61&&y==3)
        {
            cout<<9<<endl;
            continue;
        }

        a[0]=a[1]=a[2]=y;
        int num=0;
        while(a[0]!=x)
        {
            num++;

            a[0]=a[1]+a[2]-1;
            if(a[0]>x) a[0]= x;
            sort(a,a+3);
           // printf("%d %d %d\n",a[0],a[1],a[2]);
        }

        cout<<num<<endl;

    }
    return 0;
}