← 返回题目列表

Codeforces · 712/C

C. 记忆与反进化

中文机器翻译题面 查看原题

记忆现在对物体的反进化感兴趣,特别是三角形。他从边长为 x 的等边三角形开始,他希望执行操作以获得边长为 y 的等边三角形。

在一秒钟内,他可以修改当前三角形的单边长度,使其保持为非退化三角形(面积为正的三角形)。在任何时刻,每条边的长度都应该是整数。

内存求得边长为y的等边三角形最少需要多少秒?

输入

第一行也是唯一一行包含两个整数 x 和 y (3 ≤ y < x ≤ 100 000) - 分别是等边三角形的起始和结束边长。

输出

打印一个整数——如果内存从边长为 x 的等边三角形开始,则获得边长为 y 的等边三角形所需的最少秒数。

示例

输入 #1

6 3

输出 #1

4

输入 #2

8 5

输出 #2

3

输入 #3

22 4

输出 #3

6

注意

在第一个示例测试中,Memory 从一个边长为 6 的等边三角形开始,想要一个边长为 3 的三角形。将边长为 a、b 和 c 的三角形表示为 (a, b, c)。然后,内存可以执行$$(6,6,6)\rightarrow(6,6,3)\rightarrow(6,4,3)\rightarrow(3,4,3)\rightarrow(3,3,3)$$。

在第二个样本测试中,内存可以执行 $$( 8, 8, 8 ) \rightarrow ( 8, 8, 5 ) \rightarrow ( 8, 5, 5 ) \rightarrow ( 5, 5, 5 )$$。

在第三个样本测试中,Memory 可以执行:$$(22,22,22)\rightarrow(7,22,22)\rightarrow(7,22,16)\rightarrow(7,10,16)\rightarrow(7,10,4)$$

$$( 7, 4, 4 ) \rightarrow ( 4, 4, 4 )$$。