1261 - 【USACO】迷失的奶牛(USACO 2017 OPEN)

通过次数

9

提交次数

27

时间限制 : 1 秒
内存限制 : 128 MB

Farmer John把他的奶牛Bessie弄丢了,他需要找回她!
幸运的是,整个农场只有一条漫长的道路,并且Farmer John知道Bessie 一定会在这条道路上。如果我们将这条 道路视为一个数轴,那么Farmer John当前处于位置x,并且Bessie当前处于位置y (Farmer John并不知道 Bessie所处位置)。如果Farmer John知道Bessie所处位置,那么他就可以径直向她走去,并行走了|x-y|个单位距离。不幸的是,外面一片漆黑,Farmer John什么都看不见。他找回Bessie的唯一方法就是来回走动直到走到她的位置。
为了找出在找回奶牛过程中来回走动的最佳策略,Farmer John查阅了计算机科学研究文献。有趣的是,这个问题不仅在过去中被计算机科学家所研究,而且实际上该问题被称为“Lost Cow Problem"(这确实是真的!)。
Farmer John找回Bessie的方法是,首先移动到位置x+1,然后反方向移动到位置x-2,然后再次反方向 移动到位置x+4:,以此类推,以之字形的方式来回走动,每次移动后与起点x的距离变成两倍,如果走到了 Bessie所在的位置Farmer John会立刻停下。正如他在研究解决“Lost Cow Problem ”的算法时所知道的那样,这种方法保证了直到找回Bessie前他最多会移动9倍的|x-y|个单位距离(这也是事实,并且在任何来回走动的策略下,仍最多会移动9倍距离)。
Farmer John好气地想要验证这个结论。给出x,y,请你求出,根据上述之字形的走动策略,直到找回Bessie ,Farmer John需要移动的距离。

输入

输入的第一行包括两个不同的整数x,y ( 0 ≤ x,y ≤ 1,000 )

输出

输出一个整数,表示Farmer John找回Bessie所需要移动的距离。

样例

输入

3 6

输出

9

提示

Farmer John 行走路径为 x = 3—>x = 4—>x =1—>x = 6