强哥历险记——迷失的狗狗
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
强哥 把他的狗狗 William 弄丢了,他需要找回他!
幸运的是,整个庄园只有一条漫长的道路,并且 强哥 知道 William 一定会在这条道路上。如果我们将这条道路视为一个数轴,那么 强哥 当前处于位置 ,并且 William 当前处于位置 ( 强哥 并不知道 William 所处位置)。如果 强哥 知道 William 所处位置,那么他就可以径直向他走去,并行走了 个单位距离。不幸的是,外面一片漆黑,强哥 什么都看不见。他找回 William 的唯一方法就是来回走动直到走到他的位置。
为了找出在找回狗狗过程中来回走动的最佳策略, 强哥 查阅了计算机科学研究文献。有趣的是,这个问题不仅在过去中被计算机科学家所研究,而且实际上该问题被称为 “Lost Cow Problem”(这确实是真的!)。
强哥 找回 William 的方法是,首先移动到位置 ,然后反方向移动到位置 ,然后再次反方向移动到位置 ,以此类推,以之字形的方式来回走动,每次移动后与起点 的距离变成两倍,如果走到了 William 所在的位置 强哥 会立刻停下。正如他在研究解决“Lost Cow Problem”的算法时所知道的那样,这种方法保证了直到找回 William 前他最多会移动 9 倍的 个单位距离(这也是事实,并且在任何来回走动的策略下,仍最多会移动 倍距离)。
强哥 好奇地想要验证这个结论。给出 、 ,请你求出,根据上述之字形的走动策略,直到找回 William , 强哥 需要移动的距离。
输入格式
输入的第一行包括两个不同的整数 、 ( )。
输出格式
输出一个整数,表示 强哥 找回 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