#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​。它们的范围都在01,000之间。

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

输出只有一行,包含约翰为了到达贝西将要行走的距离。

示例输入:

3 6

示例输出:

9