CF712C.Memory and De-Evolution

普及/提高-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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?

Memory 现在对物体的“逆演化”(de-evolution)产生了兴趣,特别是三角形。他从一个边长为 xx 的正三角形出发,希望经过若干次操作,得到一个边长为 yy 的正三角形。

每一秒,他可以修改当前三角形的一条边的长度,使得修改后仍构成一个非退化三角形(即面积为正的三角形)。在任意时刻,每条边的长度都必须是整数。

Memory 得到边长为 yy 的正三角形所需的最少秒数是多少?

输入格式

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.

第一行且唯一一行包含两个整数 xx 和 yy(3 ≤ y < x ≤ 100 0003 ≤ y < x ≤ 100\,000),分别表示起始和终止的等边三角形边长。

输出格式

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.

输出一个整数——Memory 从边长为 xx 的等边三角形出发,获得边长为 yy 的等边三角形所需的最少秒数。

输入输出样例

  • 输入#1

    6 3

    输出#1

    4
  • 输入#2

    8 5

    输出#2

    3
  • 输入#3

    22 4

    输出#3

    6

说明/提示

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:

.

在第一个样例测试中,Memory 起始时拥有一个边长为 6 的等边三角形,目标是得到一个边长为 3 的等边三角形。用 (a, b, c) 表示边长分别为 a、b、c 的三角形。于是,Memory 可以执行如下操作:。

在第二个样例测试中,Memory 可以执行如下操作:。

在第三个样例测试中,Memory 可以执行如下操作:

。

输入解题思路,AI测评打分。不知道怎么写?

首页