The Lost Cow

题目描述

农夫约翰丢失了他的获奖奶牛贝茜，他需要找到她！ 幸运的是，农场里只有一条很长的小路贯穿全场，农夫约翰知道贝茜一定在这条路上的某个位置。若将这条路看作数轴，则农夫约翰目前位于位置 $x$，贝茜目前位于位置 $y$（农夫约翰并不知道）。如果农夫约翰知道贝茜的位置，他可以直接走到她那里，行走距离为 $|x - y|$。不幸的是，外面很黑，农夫约翰什么也看不见。他找到贝茜的唯一方法就是来回走动，直到最终到达她的位置。

为了找出在搜索过程中来回走动的最佳策略，农夫约翰查阅了计算机科学研究文献，并有些惊讶地发现，这个完全相同的问题不仅曾被计算机科学家研究过，而且它实际上被称为“丢失的奶牛问题”（这是真的！）。

推荐给农夫约翰的寻找贝茜的方法是：先移动到位置 $x+1$，然后反向移动到位置 $x-2$，再到位置 $x+4$，以此类推，按照“之”字形（zig zag）模式移动；每一步相对于最初起点的距离都会变为之前的两倍。正如他在学习解决丢失奶牛问题的算法时所读到的那样，这种方法保证在最坏情况下，在找到贝茜之前，他行走的总距离至多是他与贝茜直接距离 $|x-y|$ 的 9 倍（这也是真的，而且 9 这个系数实际上是任何策略所能达到的最小的最坏情况保证）。

农夫约翰想验证这一结果。给定 $x$ 和 $y$，请计算他按照上述之字形搜索策略，直到找到贝茜为止所行走的总距离。

输入格式

输入只有一行，包含两个不同的用空格分隔的整数 $x$ 和 $y$。二者均在范围 $0 \ldots 1,000$ 之内。

输出格式

输出一行，包含农夫约翰到达贝茜位置所需要行走的距离。

3 6

9

提示

题目来源：Brian Dean

标签: USACO|2017|Bronze

来源

USACO|2017|Bronze