C. Memory and De-Evolution

Codeforces
IDCF712C
Time2000ms
Memory256MB
Difficulty
greedymath
English · Original
Chinese · Translation
Formal · Original
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_. [samples] ## 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: .
Memory 现在对物体的逆进化感兴趣,特别是三角形。他从一个边长为 $x$ 的等边三角形开始,希望执行若干操作,得到一个边长为 $y$ 的等边三角形。 在每一秒内,他可以修改当前三角形的一条边的长度,使得它始终是一个非退化三角形(即面积为正的三角形)。在任何时刻,每条边的长度都必须是整数。 请问,Memory 要获得边长为 $y$ 的等边三角形,最少需要多少秒? 第一行且仅一行包含两个整数 $x$ 和 $y$($3 ≤ y < x ≤ 100 000$)—— 分别表示起始和目标等边三角形的边长。 请输出一个整数——Memory 从边长为 $x$ 的等边三角形开始,获得边长为 $y$ 的等边三角形所需的最少秒数。 在第一个样例中,Memory 从一个边长为 $6$ 的等边三角形开始,希望得到边长为 $3$ 的三角形。记边长为 $a$、$b$、$c$ 的三角形为 $(a, b, c)$。那么 Memory 可以进行:。 在第二个样例中,Memory 可以进行:。 在第三个样例中,Memory 可以进行: 。 ## Input 第一行且仅一行包含两个整数 $x$ 和 $y$($3 ≤ y < x ≤ 100 000$)—— 分别表示起始和目标等边三角形的边长。 ## Output 请输出一个整数——Memory 从边长为 $x$ 的等边三角形开始,获得边长为 $y$ 的等边三角形所需的最少秒数。 [samples] ## Note 在第一个样例中,Memory 从一个边长为 $6$ 的等边三角形开始,希望得到边长为 $3$ 的三角形。记边长为 $a$、$b$、$c$ 的三角形为 $(a, b, c)$。那么 Memory 可以进行:。在第二个样例中,Memory 可以进行:。在第三个样例中,Memory 可以进行:。
Given integers $ x $ and $ y $ such that $ 3 \leq y < x \leq 100{,}000 $, start with an equilateral triangle of side lengths $ (x, x, x) $. In one second, change exactly one side to any integer value such that the resulting triangle remains non-degenerate (i.e., satisfies the strict triangle inequality). The goal is to reach the equilateral triangle $ (y, y, y) $ in minimum seconds. Let $ a \leq b \leq c $ be the sorted side lengths at any step. The triangle is non-degenerate if and only if $ a + b > c $. Define the state as a triple $ (a, b, c) $ of positive integers with $ a \leq b \leq c $ and $ a + b > c $. The initial state is $ (x, x, x) $, and the target is $ (y, y, y) $. We seek the minimum number of operations (each changing one side to any integer) to reach the target. --- **Formal Problem Statement:** Let $ x, y \in \mathbb{Z} $, $ 3 \leq y < x \leq 100{,}000 $. Start: $ T_0 = (x, x, x) $. Target: $ T_f = (y, y, y) $. At each step, change exactly one side to any integer $ s \in \mathbb{Z}^+ $, such that the new triple $ (a, b, c) $, when sorted, satisfies $ a + b > c $. Minimize the number of steps to reach $ T_f $. --- **Objective:** Find the minimal number of operations to transform $ (x, x, x) $ into $ (y, y, y) $ under the above constraints.
Samples
Input #1
6 3
Output #1
4
Input #2
8 5
Output #2
3
Input #3
22 4
Output #3
6
API Response (JSON)
{
  "problem": {
    "name": "C. Memory and De-Evolution",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF712C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Memory 现在对物体的逆进化感兴趣,特别是三角形。他从一个边长为 $x$ 的等边三角形开始,希望执行若干操作,得到一个边长为 $y$ 的等边三角形。\n\n在每一秒内,他可以修改当前三角形的一条边的长度,使得它始终是一个非退化三角形(即面积为正的三角形)。在任何时刻,每条边的长度都必须是整数。\n\n请问,Memory 要获得边长为 $y$ 的等边三角形,最少需要多少秒?\n\n第一行且仅一行包含两个整数...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given integers $ x $ and $ y $ such that $ 3 \\leq y < x \\leq 100{,}000 $, start with an equilateral triangle of side lengths $ (x, x, x) $. In one second, change exactly one side to any integer value ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments