USACO 2017 US Open Contest, Bronze

问题 1. 失踪的奶牛

农场主 John 丢失了他心爱的奶牛 Bessie，他需要找到她！ 幸运的是，农场上只有一条长长的小路，农场主 John 知道 Bessie 一定在这条路上的某个位置。如果我们将这条路看作数轴，农场主 John 现在在位置 x，而 Bessie 在位置 y（位置未知）。如果农场主 John 知道 Bessie 的位置，他可以直接走过去，行走的距离为 |x − y|。 不幸的是，现在天已经黑了，农场主 John 看不见任何东西。他唯一能做的就是来回走动，直到最终找到她的位置。

为了找到最好的走动策略，农场主 John 查阅了计算机科学的研究文献，颇为有趣的是，他发现这个问题不仅计算机科学家曾经研究过，实际上这就是“失踪奶牛问题”（这是真的！）。

研究文献中推荐的解决方案是，农场主 John 按照一定的模式来回走动： 首先走到位置 x + 1，然后转身走到位置 x − 2，再走到位置 x + 4，以此类推。每次走的距离是上一次的两倍，这样形成一个“之”字形的走动模式。他发现，按照这种模式，最坏情况下他最多会走 9 倍于直接距离 |x − y| 的距离，最终找到 Bessie（这个结论也是正确的，且 9 倍是最坏情况下的最小保证距离）。

农场主 John 对这个结果很好奇。给定 x 和 y，请计算按照上述“之”字形查找策略，他将走多少距离才能找到 Bessie。

输入格式 (文件 lostcow.in)：

输入包含一行，包含两个不同的整数 x 和 y，二者之间用空格隔开。 x 和 y 的值在 0 到 1000 之间。

输出格式 (文件 lostcow.out)：

输出一行，包含农场主 John 为了找到 Bessie 所走的总距离。

示例输入：

3 6

示例输出：

9

题目分析：

这个问题的关键是理解“之”字形模式的走动方式。

• 农场主 John 先向一个方向走，然后再转身向另一个方向走，每次的步伐距离是上一次的两倍。
• 他会一直按照这种模式走，直到经过的所有位置覆盖了 Bessie 的位置。

例如，对于输入 x = 3 和 y = 6：

• 初始时，John 站在位置 3，Bessie 在位置 6。
• 第一走的距离是 1，走到位置 4。
• 然后转身，走 2 单位，走到位置 2。
• 再转身，走 4 单位，走到位置 6（就是 Bessie 的位置）。

最终的总距离为 1 + 2 + 4 = 9。