#U1617OB1. The Lost Cow
The Lost Cow
农夫约翰失去了他的奖品奶牛贝西,他需要找到她!
幸运的是,只有一条长长的小路穿过农场,农夫约翰知道贝西必须在这条小路上的某个位置。如果我们将路径想象成一条数字线,那么 Farmer John 当前位于位置 x,而 Bessie 当前位于位置 y(Farmer John 不知道)。如果 Farmer John 只知道 Bessie 在哪里,他可以直接走到她身边,走 |x−y| 的距离。不幸的是,外面很黑,农夫约翰什么也看不见。他能找到贝西的唯一方法就是来回走动,直到他最终到达她的位置。
为了找出在他的搜索中来回走动的最佳策略,Farmer John 查阅了计算机科学研究文献,发现这个确切的问题不仅过去曾被计算机科学家研究过,而且是实际上称为“丢失的奶牛问题”(这实际上是真的!)。
Farmer John 推荐的寻找 Bessie 的解决方案是移动到位置 x+1,然后反向移动到位置 x−2,然后移动到位置 x+4,依此类推,以“之字形”模式,每一步距离他最初的起始位置的距离是以前的两倍。正如他在研究解决迷路的奶牛问题的算法时所读到的那样,这种方法可以保证他在最坏的情况下将行驶 9 倍的直接距离 |x−y|。在他找到她之前,他和 Bessie 之间的关系(这也是事实,而 9 的系数实际上是任何策略都可以实现的最小这种最坏情况保证)。
Farmer John 很想验证这个结果。给定 x 和 y,请根据上面的“之字形”搜索策略计算他在找到 Bessie 之前将行进的总距离。
输入格式(文件 lostcow.in):
单行输入包含两个不同的空格分隔整数 x 和 y。两者都在 0…1,000 范围内。
输出格式(文件 lostcow.out):
打印一行输出,包含 Farmer John 到达 Bessie 的路程。
样例输入:
3 6
样例输出:
9