问题6704--丢失的奶牛

6704: 丢失的奶牛

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MiB

题目描述

农夫约翰失去了他的奶牛贝西,他需要找到她!

幸运的是,只有一条很长的路穿过农场,农民约翰知道贝西一定在这条路上的某个地方。如果我们将路径视为一条数字线,则农民约翰当前位于位置x,贝西当前位于位置y(农民约翰未知)。如果农夫约翰只知道贝西的位置,他可以直接走到她身边,走一段距离|xy|。不幸的是,外面很黑,农民约翰什么也看不见。他找到贝西的唯一方法就是来回走动,直到他最终到达她的位置。

为了找出在搜索过程中来回走动的最佳策略,农民约翰查阅了计算机科学研究文献,发现这个确切的问题不仅在过去被计算机科学家研究过,而且它是实际上被称为“丢失的奶牛问题”(这是真的!),他感到有些好笑。

 

Farmer John找到Bessie的建议解决方案是移动到x+1位置,然后反向移动到x2,然后到位置x+4,以此类推,以“之字形”模式,每一步从他的初始起始位置移动的距离是以前的两倍。正如他在研究解决迷路奶牛问题的算法时所读到的,这种方法保证了他在最坏情况下将移动9倍于直接距离|x-y|在他找到贝西之前,他和贝西之间的距离(这也是事实,而9的系数实际上是任何策略所能达到的最小最坏情况保证)。

 

农夫约翰很想验证这个结果。给定xy,请根据上面的之字形搜索策略计算他在找到贝西。

 

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

单行输入包含两个不同的空格分隔的整数xy。它们都在01000的范围内。

 

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

打印一行输出,农民约翰找到达贝西的路程。

 

示例输入:

3 6

 

示例输出:

9

样例输入 复制


样例输出 复制


来源/分类