小 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;
}

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