{"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$ 号格子。\n\n## Input\n\n仅一行，一个正整数，表示 $n$。\n\n## Output\n\n仅一行，一个正整数，表示最少跳跃次数。\n\n[samples]\n\n## Note\n\n#### 样例解释\n\n第一组样例：  \n$1\\to 2 \\to 4\\to 8 \\to 16 \\to 15 \\to 30$\n\n第二组样例：  \n$1\\to 2\\to 3\\to6\\to12\\to24\\to25\\to 50$\n\n第三组样例：  \n$1\\to 2\\to4\\to8\\to16\\to32\\to64$\n\n第四组样例：  \n$1\\to 2\\to4\\to8\\to16\\to32\\to31\\to62\\to63$  \n\n请注意在本组样例中，$63$ 不能通过 $64-1$ 得到，因为格子总数为 $63$，没有第 $64$ 个格子。\n\n#### 数据规模与约定\n\n对于 $100\\%$ 的数据，有 $1\\leq n \\leq 10^6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3626","tags":["广度优先搜索 BFS"],"sample_group":[["30","6"],["50","7"],["64","6"],["63","8"]],"created_at":"2026-03-03 11:09:25"}}