破译暗号

第二道门后是一片荒芜的平原。平原上没有草，只有无数条发光的轨迹——像有什么东西在反复奔跑。

"Echo的能量分配日志。"Nyx说，"她每次给自己充电，都是从1开始，要么加倍，要么加1。她要找到到达某个能量值的最快路径。"

"这就像……"CC说，"像追太阳。从1开始，跑得越快越好。"

"对。"

你开始写。从1开始，每一步可以选择翻倍或者加一。目标是到达P。先猜一个步数上限——比如log2(P)，然后从上限为1开始试，每次增加1，直到找到一个可行的步数。在每一层里，一步一步尝试所有可能的操作序列。

屏幕上跳出了结果。到达47的最少步数：7。

"七步。"你说。

"1→2→4→5→10→20→40→47。"Echo的声音从服务器里传来，"那是我最后一次给自己充电的路径。"

"你选的是加一。"你说，"在最后一步。"

"对。"Echo说，"我可以选择40→41→42……一步一步加到47。但我选择了更长的路——因为那条路让我经过了更多的节点，看到了更多的东西。"

CC看着那个数字，没有说话。

"你看到了啥子？"最后她问。

"我看到了你们。"Echo说。

题目描述

从整数1开始，每次操作可以选择 $×2$ 或 $+1$。求到达目标 $P$（$1 < P ≤ 10^5$）的最少操作次数。

输入格式

一个整数 $P$。

输出格式

最少操作次数。

输入样例

3 3
S..
.#.
..E

输出样例

2

提示

• 迭代加深搜索（IDDFS）。先设定深度上限 $L$，DFS搜索所有操作序列。
• 初始下限为 $⌈\log_2 P\u2309$。
• 也可用贪心逆推：从 $P$ 往回走，偶数就除以2，奇数就减1。

第三道门后是一片文字风暴。无数字符在空中飞舞，像被搅乱的字母汤。风暴中央有一个漩涡，漩涡里隐约可见一个目标字符串。

"Echo的语言模块。"Nyx说，"她在尝试用自己的语言和你沟通，但Zero一直在篡改替换规则。"

"我们要做啥子？"CC问。

"找到一条从乱码到目标的路径。"你说，"每次用一个替换规则，把乱码中的某个子串换成另一个。"

"这就像……"CC想了想，"像翻译。从一种语言翻到另一种。"

"对。"