C - Memory and De-Evolution CodeForces

C - Memory and De-Evolution CodeForces - 712C（三角形）

本文主要是介绍C - Memory and De-Evolution CodeForces - 712C（三角形），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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:

题意： 边长分别为b和a的等边三角形，每次变上一个三角形的一个边，保证变完还是三角形，问多少次可以变成边长为a的等边三角形。

思路： 一开始我是从b开始变化的。题目中给的例子是6 6 6 -> 6 6 3，8 8 8 -> 8 8 5，
22 22 22 -> 7 22 22。于是按照这个变化规则，我就猜测枚举第一次变化的数字，之后都是最优变化（假设从小到大是x y z，那么变化完就是 y - x + 1 x y），其中一旦出现了a + x > y的情况，那么就一定可以变出一个a来，此时特殊判断。然后模拟过程。这个过程实现上就很麻烦，而且并不能保证最优。

但是正解还是很简单的，从后往前变很难保证最优，如果逆向思考，就是从a a a 变到 b b b。变化过程依然是按照三角形规则的最优变化，但是不同的是只要变成了大于等于b，也就得出了结果。

#include <cstdio>
#include <iostream>using namespace std;int main()
{int a,b;scanf("%d%d",&a,&b);int x = b,y = b,z = b;int ans = 0;while(true){if(x >= a && y >= a && z >= a){break;}ans ++;if(ans % 3 == 0){x = y + z - 1;}else if(ans % 3 == 1){y = x + z - 1;}else if(ans % 3 == 2){z = x + y - 1;}}printf("%d\n",ans);
}