Codeforces 712C Memory and De-Evolution

C. Memory and De-Evolution

time limit per test:2 seconds

memory limit per test:256 megabytes

input:standard input

output:standard output

Memory is now interested in the de-evolution of objects, specifically triangles. He starts with an equilateral triangle of side length x, and he wishes to perform operations to obtain an equilateral triangle of side length y.

In a single second, he can modify the length of a single side of the current triangle such that it remains a non-degenerate triangle (triangle of positive area). At any moment of time, the length of each side should be integer.

What is the minimum number of seconds required for Memory to obtain the equilateral triangle of side length y?

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:

.

解题思路:

【题意】 现有边长为x的等边三角形,Memory想要将其变成边长为y的等边三角形

现规定Memory每秒能够改变一条边的大小,但要保证改变后的三条边仍能构成一个三角形

问,最少需要多少时间才能变为边长为y的等边三角形

【类型】 贪心,逆推

【分析】

从边长为6的等边三角形变为边长为3的等边三角形。先将一边变为3,则(6,6,3),如果再将一边变成3,则(6,3,3)并不能组成三角形,所以只能先变为(6,4,3)然后变为(3,4,3),最后变为(3,3,3),一共4步,所以输出4,此题很明显是贪心,直接贪就是了,用一个数记录需要的时间即可!此题需要注意的是最好选择逆推法,由y->x,这样就能保证合法且最快了!

【时间复杂度&&优化】 O(n)

题目链接→Codeforces Problem 712C Memory and De-Evolution

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int s[3];
 6     int x,y,i;
 7     while(cin>>x>>y)
 8     {
 9         int ans=0;
10         s[0]=s[1]=s[2]=y;
11         for(i=0;s[0]<x||s[1]<x||s[2]<x;i++)
12         {
13             s[0]=s[1]+s[2]-1;
14             sort(s,s+3);
15             ans++;
16         }
17         cout<<ans<<endl;
18     }
19     return 0;
20 }

 经过学长的提醒,我想出了另外一种方法,这样更简单!

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int s[3];
 6     int x,y,i;
 7     while(cin>>x>>y)
 8     {
 9         s[0]=s[1]=s[2]=y;
10         for(i=0;s[0]<x||s[1]<x||s[2]<x;i++)
11             s[i%3]=s[(i+1)%3]+s[(i+2)%3]-1;//从小变大,每次都是最小边变另外两边的和减1,s[0],s[1],s[2]依次变就能保证,变时候一定是三个里面最小的
12         cout<<i<<endl;
13     }
14     return 0;
15 }

这样写也可以!

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int s[3];
 6     int x,y,i;
 7     while(cin>>x>>y)
 8     {
 9         s[0]=s[1]=s[2]=y;
10         int ans=0;
11         while(s[0]!=x||s[1]!=x||s[2]!=x)
12         {
13             sort(s,s+3);
14             s[0]=min(s[1]+s[2]-1,x);
15             ans++;
16         }
17         cout<<ans<<endl;
18     }
19     return 0;
20 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏玩转JavaEE

Spring常用配置

上篇文章我们简单介绍了Spring的基本配置,算是一个简单的入门,这篇文章我们再一起来看看Spring在使用的过程中一些其他的常见配置。 Bean的Scope ...

3246
来自专栏IT 指南者专栏

Spring框架系列(二)之Bean的注解管理

微信公众号:compassblog 欢迎关注、转发,互相学习,共同进步! 有任何问题,请后台留言联系! 1、Spring中的两种容器 在系列(一)中我们已经知道...

3396
来自专栏desperate633

资源竞速(Race Conditions)和临界区(Critical Sections)临界区临界区的资源竞速避免资源竞速临界区的吞吐量

critical section是每个线程中访问临界资源的那段代码,不论是硬件临界资源,还是软件临界资源,多个线程必须互斥地对它进行访问。 资源竞速就是可能在...

1030
来自专栏lgp20151222

Spring中的@scope注解

但是也可以理解成,singleton是启动创建,prototype/request/session/globalsession是动态创建。

1201
来自专栏用户2442861的专栏

Python日志输出——logging模块

http://blog.csdn.net/chosen0ne/article/details/7319306

1221
来自专栏aoho求索

Spring Cloud Stream应用与自定义RocketMQ Binder:实现RocketMQ绑定器

前言: 本文作者张天,节选自笔者与其合著的《Spring Cloud微服务架构进阶》,即将在八月出版问世。本文将其中Spring Cloud Stream应用与...

2653
来自专栏帅小子的日常

使用redis做缓存

7257
来自专栏代码拾遗

深入理解Spring MVC

使用Spring Boot和web,thymeleaf的starter来设置初始工程。xml配置如下:

1072
来自专栏开发与安全

linux网络编程之System V 消息队列(一):消息队列内核结构和msgget、msgctl 函数

一、消息队列 1、消息队列提供了一个从一个进程向另外一个进程发送一块数据的方法 2、每个数据块都被认为是有一个类型,接收者进程接收的数据块可以有不同的类型值 ...

2260
来自专栏java学习

Spring常用注解(收藏大全)

如果你是初学者,或者是自学者!你可以加小编微信(xxf960513)!小编可以给你学习上,工作上的一些建议以及可以给你(免费)提供学习资料!最重要我们还可以交个...

962

扫码关注云+社区

领取腾讯云代金券