首页 > 代码库 > codeforces 712C C. Memory and De-Evolution(贪心)
codeforces 712C C. Memory and De-Evolution(贪心)
题目链接：http://codeforces.com/problemset/problem/712/C
题目大意：
给连个值x,y (3 ≤ y < x ≤ 100 000), x，y都为等边三角形。从y等边三角形 每次修改一条边，且修改后的三个边还能组成一个三角形（两边之和大于第三边）。问修改几次能够得到x为边的等边三角形。
例如：
输入： 22 4 输出： 6
解题思路：
从y->x ，定义三个边y1=y2=y3=y,
每次修改一条边 y1=y2+y3-1(两边之和大于第三遍) 修改++ 如果y1>=x break;
修改一条边 y2=y1+y3-1 修改++ 如果y2>=x break;
修改一条边 y3=y1+y2-1 修改++ 如果y3>=x break;
可以发现，如果（y1,y2,y3）有一个边>=x，则还需两步即可完成。
输出 修改+2
AC Code:
1 #include<bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int x,y,ans; 6 while(scanf("%d%d",&x,&y)!=EOF) 7 { 8 ans=0; 9 int y1,y2,y3;10 y1=y2=y3=y;11 while(y1!=x&&y2!=x&&y3!=x)12 {13 y1=y2+y3-1;14 ++ans;15 if(y1>=x)break;16 y2=y1+y3-1;17 ++ans;18 if(y2>=x)break;19 y3=y1+y2-1;20 ++ans;21 if(y3>=x)break;22 }23 cout<<ans+2<<endl;24 }25 return 0;26 }
codeforces 712C C. Memory and De-Evolution(贪心)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。