小 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;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。