#F. 强哥历险记——迷失的狗狗

    传统题 1000ms 256MiB

强哥历险记——迷失的狗狗

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

强哥 把他的狗狗 William 弄丢了,他需要找回他!

幸运的是,整个庄园只有一条漫长的道路,并且 强哥 知道 William 一定会在这条道路上。如果我们将这条道路视为一个数轴,那么 强哥 当前处于位置 xx ,并且 William 当前处于位置 yy ( 强哥 并不知道 William 所处位置)。如果 强哥 知道 William 所处位置,那么他就可以径直向他走去,并行走了 xy|x - y| 个单位距离。不幸的是,外面一片漆黑,强哥 什么都看不见。他找回 William 的唯一方法就是来回走动直到走到他的位置。

为了找出在找回狗狗过程中来回走动的最佳策略, 强哥 查阅了计算机科学研究文献。有趣的是,这个问题不仅在过去中被计算机科学家所研究,而且实际上该问题被称为 “Lost Cow Problem”(这确实是真的!)。

强哥 找回 William 的方法是,首先移动到位置 x+1x + 1 ,然后反方向移动到位置 x2x - 2 ,然后再次反方向移动到位置 x+4x + 4 ,以此类推,以之字形的方式来回走动,每次移动后与起点 xx 的距离变成两倍,如果走到了 William 所在的位置 强哥 会立刻停下。正如他在研究解决“Lost Cow Problem”的算法时所知道的那样,这种方法保证了直到找回 William 前他最多会移动 9 倍的 xy|x - y| 个单位距离(这也是事实,并且在任何来回走动的策略下,仍最多会移动 99 倍距离)。

强哥 好奇地想要验证这个结论。给出 xxyy ,请你求出,根据上述之字形的走动策略,直到找回 William , 强哥 需要移动的距离。

输入格式

输入的第一行包括两个不同的整数 xxyy0x,y10000 \le x, y \le 1000 )。

输出格式

输出一个整数,表示 强哥 找回 William 所需要移动的距离。

3 6
9

提示

样例解释

强哥 行走路径为 $x = 3 \rightarrow x = 4 \rightarrow x = 1 \rightarrow x = 6$ 。

2024暑期北京线下营ACM欢乐赛(第一期)

未参加
状态
已结束
规则
ACM/ICPC
题目
7
开始于
2024-7-9 19:30
结束于
2024-7-9 20:48
持续时间
1.3 小时
主持人
参赛人数
35