Project Euler | 欧拉计划
0%

Problem 993

题目发布于 翻译更新于

Problem 993

Banana Beaver

A beaver plays a game on an infinitely long number line.
When the game starts, the beaver is at position $0$, carrying $N$ bananas, and there are no other bananas on the number line.

At each step, the beaver will do the following according to the bananas it sees at positions $x$ and $x + 1$, where $x$ is the beaver’s current position:

  • If there is a banana at $x$ and another banana at $x + 1$, then the beaver will pick up a banana at position $x+1$, and then move itself to position $x-1$.
  • If there is a banana at $x$ but there is no banana at $x+1$, then it will pick up a banana at $x$ and move itself to position $x+2$.
  • If there is no banana at $x$ but there is a banana at $x+1$, then it will move a banana from position $x+1$ to position $x$ and move itself to position $x+2$.
  • If there is no banana at $x$ and no banana at $x + 1$, then the beaver checks whether it still carries at least three bananas. If so, then it will drop a banana at each of the three positions $x - 1, x, x + 1$ and move itself to position $x-2$; otherwise the game ends.

For example, if $N \ge 3$, then the last rule applies to the starting position, so after $1$ step, there are $3$ bananas on the number line, at positions $-1, 0, 1$, with the beaver at position $-2$.

Similarly, if $N \ge 5$, then after $5$ steps, there are $5$ bananas on the number line, at positions $-2,-1,0,1,2$, with the beaver at position $-1$.

Let $\operatorname{BB}(N)$ be the position of the beaver when the game ends (which can be proved to always happen).

You are given $\operatorname{BB}(1000) = 1499$.

Find $\operatorname{BB}(10^{18})$.

香蕉海狸

一只海狸正在一条无限长的数轴上玩一个游戏。
游戏开始时，海狸处于位置$0$，携带$N$根香蕉，且数轴上没有其它香蕉。

每一步中，海狸将根据其当前位置$x$以及位置$x$和$x + 1$处的香蕉数量，执行以下操作：

  • 如果位置$x$处有一根香蕉，且位置$x+1$处也有一根香蕉，则海狸拿起位置$x+1$处的香蕉，然后移动到位置$x-1$。
  • 如果位置$x$处有一根香蕉，但位置$x+1$处没有香蕉，则海狸拿起位置$x$处的香蕉，然后移动到位置$x+2$。
  • 如果位置$x$处没有香蕉，但位置$x+1$处有一根香蕉，则海狸将位置$x+1$处的香蕉放到位置$x$处，然后移动到位置$x+2$。
  • 如果位置$x$处没有香蕉，且位置$x+1$处也没有香蕉，则海狸检查自己是否携带至少三根香蕉。如是，则在位置$x-1, x, x+1$处各放下一根香蕉，然后移动到位置$x-2$；如否则游戏结束。

例如，如果$N \ge 3$，则初始状态适用最后一条规则，因此第$1$步后，数轴上有$3$根香蕉，分别在位置$-1, 0, 1$处，海狸处于位置$-2$。

类似地，如果$N \ge 5$，则第$5$步后，数轴上有$5$根香蕉，分别在位置$-2,-1,0,1,2$处，海狸处于位置$-1$。

记$\operatorname{BB}(N)$为游戏结束时海狸所处的位置（可以证明游戏总会结束）。

已知$\operatorname{BB}(1000) = 1499$。

求$\operatorname{BB}(10^{18})$。

译注：通常提及BB函数指的是Busy Beaver或忙碌海狸函数，此处替换为Banana显然是在玩缩写梗。