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