跳跃机器人

Luogu
IDLGB3626
Time1000ms
Memory512MB
DifficultyP2
广度优先搜索 BFS
地上有一排格子,共 $n$ 个位置。机器猫站在第一个格子上,需要取第 $n$ 个格子里的东西。 机器猫当然不愿意自己跑过去,所以机器猫从口袋里掏出了一个机器人!这个机器人的行动遵循下面的规则: - 初始时,机器人位于 $1$ 号格子 - 若机器人目前在 $x$ 格子,那么它可以跳跃到 $x-1, x+1, 2x$ 里的一个格子(不允许跳出界) 问机器人最少需要多少次跳跃,才能到达 $n$ 号格子。 ## Input 仅一行,一个正整数,表示 $n$。 ## Output 仅一行,一个正整数,表示最少跳跃次数。 [samples] ## Note #### 样例解释 第一组样例: $1\to 2 \to 4\to 8 \to 16 \to 15 \to 30$ 第二组样例: $1\to 2\to 3\to6\to12\to24\to25\to 50$ 第三组样例: $1\to 2\to4\to8\to16\to32\to64$ 第四组样例: $1\to 2\to4\to8\to16\to32\to31\to62\to63$ 请注意在本组样例中,$63$ 不能通过 $64-1$ 得到,因为格子总数为 $63$,没有第 $64$ 个格子。 #### 数据规模与约定 对于 $100\%$ 的数据,有 $1\leq n \leq 10^6$。
Samples
Input #1
30
Output #1
6
Input #2
50
Output #2
7
Input #3
64
Output #3
6
Input #4
63
Output #4
8
API Response (JSON)
{
  "problem": {
    "name": "跳跃机器人",
    "description": {
      "content": "地上有一排格子,共 $n$ 个位置。机器猫站在第一个格子上,需要取第 $n$ 个格子里的东西。 机器猫当然不愿意自己跑过去,所以机器猫从口袋里掏出了一个机器人!这个机器人的行动遵循下面的规则: - 初始时,机器人位于 $1$ 号格子 - 若机器人目前在 $x$ 格子,那么它可以跳跃到 $x-1, x+1, 2x$ 里的一个格子(不允许跳出界) 问机器人最少需要多少次跳跃,才能到达 $n$ 号",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3626"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "地上有一排格子,共 $n$ 个位置。机器猫站在第一个格子上,需要取第 $n$ 个格子里的东西。\n\n机器猫当然不愿意自己跑过去,所以机器猫从口袋里掏出了一个机器人!这个机器人的行动遵循下面的规则:\n\n- 初始时,机器人位于 $1$ 号格子\n- 若机器人目前在 $x$ 格子,那么它可以跳跃到 $x-1, x+1, 2x$ 里的一个格子(不允许跳出界)\n\n问机器人最少需要多少次跳跃,才能到达 $n$ 号...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments