小 K 的演化理论

小 K 的演化理论

时间： 1ms        内存：256M

描述：

小 K 最近对物体的演化很感兴趣，特别是三角形。她从边长为 $x$ 的等边三角形开始，想要通过一些操作获得边长为 $y$ 的等边三角形。

在每一次的操作中，小 K 可以修改当前三角形其中一条边的长度，但小 P 为了阻止她达到目的，要她保证任何时候都必须使得此时的三边依然可以围成一个三角形，且每条边的长度都必须是整数。

问：小 K 最少需要多少次操作才可以将边长为 $x$ 的等边三角形转化为边长为 $y$ 的等边三角形？

输入：

输入只有一行，包含两个整数 $x,y\ (3 \le y < x \le 100000)$。

输出：

输出小 K 为了达成目标所最少需要的操作次数。

示例输入：

6 3

示例输出：

4

提示：

参考答案（内存最优[1120]）：

#include<cstdio>
using namespace std;
int x,y;
int a[4];
int main()
{
    scanf("%d%d",&x,&y);
    a[1]=a[2]=a[0]=y;
    for(int i=1;;i++)
    {
        a[i%3]=a[1]+a[2]+a[0]-a[i%3]-1;
        if(a[i%3]>=x)
        {
            printf("%d",i+2);
            return 0;
        }
    }
}

参考答案（时间最优[1]）：

#include<stdio.h>
int main()
{
    int x,y;
    int a,b,c;
    int count=0;
    scanf("%d%d",&x,&y);
    a=y;b=y;c=y;
    while(a<x||b<x||c<x)
        {
            if(c!=x)
            {
                for(c=x;c>y;c=c-1)
                {
                    if(a+b>c&&b+c>a&&a+c>b)
                    {
                       count++;
                       break;
                    }
                }
            }
            if(b!=x)
            {
                for(b=x;b>y;b=b-1)
                {
                    if(a+b>c&&b+c>a&&a+c>b)
                    {
                       count++;
                       break;
                    }
                }
            }
            if(a!=x)
            {
                for(a=x;a>y;a=a-1)
                {
                    if(a+b>c&&b+c>a&&a+c>b)
                    {
                       count++;
                       break;
                    }
                }
            }
        }
    printf("%d",count);
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。