#U17B01D. The Lost Cow
The Lost Cow
描述
农夫约翰丢了他宝贵的奶牛贝西,他需要找到她!幸运的是,农场只有一条长长的路,约翰知道贝西一定在这条路上的某个位置。如果我们把这条路想象成一条数轴,那么约翰目前在位置x,而贝西在位置y(约翰不知道这个位置)。如果约翰知道贝西在哪里,他就可以直接走到她那里,行走的距离为 |x−y|。不幸的是,外面很黑,约翰什么也看不见。他唯一能找到贝西的方法就是来回走,直到他最终到达她的位置。
为了找出最佳策略,约翰查阅了计算机科学的研究文献,并惊讶地发现这个问题不仅以前被计算机科学家研究过,而且实际上被称为“丢失奶牛问题”(这是真的!)。
为约翰找到贝西的建议方案是:先移动到位置x+1,然后改变方向移动到位置x−2,再移动到位置x+4,依此类推,按照“之字形”模式,每一步都比他最初的起始位置远两倍。正如他在研究解决丢失奶牛问题的算法时所读到的,这种方法保证了他最多会行走9倍于他和贝西之间的直线距离**|x−y|**,然后就能找到她(这也是真的,而且9倍是任何策略都能达到的最小最坏情况保证)。
约翰很好奇想验证这个结果。给定x和y,请计算他按照上述之字形搜索策略找到贝西之前将行走的总距离。
输入格式(文件lostcow.in):
输入只有一行,包含两个不同的空格分隔的整数x和y。它们的范围都在0到1,000之间。
输出格式(文件lostcow.out):
输出只有一行,包含约翰为了到达贝西将要行走的距离。
示例输入:
3 6
示例输出:
9