Problem Summary

A beaver moves on the infinite integer line. At every step it inspects only the two cells \(x\) and \(x+1\), where \(x\) is its current position. Depending on whether those cells contain bananas, it removes a banana, moves a banana one cell left, or, if both cells are empty and it still carries at least three bananas, drops three bananas at \(x-1,x,x+1\) and jumps two cells left.

The requested function \(\operatorname{BB}(N)\) is the final position when the beaver starts at \(0\) carrying \(N\) bananas and the line is initially empty. The official check value is

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

The direct state space is infinite because the line is unbounded and \(N=10^{18}\) is far too large for step-by-step simulation. The solution below reduces the game to a finite universal simulation and then uses an eventual affine period in a threshold sequence.

Mathematical Approach

1. Conservation Law

Let \(C\) be the number of bananas carried by the beaver and let \(L\) be the number of bananas currently lying on the number line. Every rule preserves the total number of bananas:

$$C+L=N.$$

Rules that pick up a banana decrease \(L\) by \(1\) and increase \(C\) by \(1\). The rule that moves a banana from \(x+1\) to \(x\) keeps \(L\) unchanged. The dropping rule decreases \(C\) by \(3\) and increases \(L\) by \(3\). Hence the carried count never needs to be stored explicitly if we know \(N\) and \(L\).

2. When Does a Game with \(N\) Bananas Stop?

The game can stop only at an empty-pair event, meaning that there is no banana at either \(x\) or \(x+1\). At such an event the beaver checks whether \(C \ge 3\). Using the invariant, this is

$$N-L\ge 3.$$

Therefore the game stops precisely when

$$N-L<3 \quad\Longleftrightarrow\quad L\ge N-2.$$

This is the key reduction: instead of simulating a separate game for every \(N\), simulate a single beaver that always performs the three-banana drop, and record the first position at which the line contains at least a specified number of bananas.

3. Universal Simulator and Threshold Function

Define \(F(t)\) to be the current position \(x\) at the first empty-pair event for which the number \(L\) of bananas on the line is at least \(t\). Because a game with \(N\) bananas stops at the first empty-pair event with \(L\ge N-2\), we have

$$\boxed{\operatorname{BB}(N)=F(\max(0,N-2)).}$$

The code computes this function with Simulator::first_positions. Whenever an empty-pair event is reached, the current \(L\) may skip several thresholds, so all still-unfilled entries up to \(L\) receive the same position \(x\). This is why the implementation uses a loop

$$\text{while filled} < \min(L,T):\quad F(\text{filled}+1)=x.$$

The simulated line is stored as a Boolean array with a large offset. The helper functions set and clear update the array and maintain \(L\) exactly.

4. Empirical Period as a Finite Certificate

After a transient prefix the threshold sequence becomes affine-periodic. The constants used by the program are

$$a=512,\qquad p=71,\qquad s=118.$$

For every checked threshold \(m\) in the range

$$512\le m\le 10000-71,$$

the program verifies

$$\boxed{F(m+71)=F(m)+118.}$$

This is stronger than checking only the final answer: it checks the whole post-transient segment generated by the finite simulation. Conceptually, this is a cycle in the normalized local configuration: after \(71\) additional line bananas, the same local pattern reappears shifted by \(118\) cells.

5. Extrapolating to \(10^{18}\)

Let

$$t=\max(0,N-2).$$

If \(t\) lies inside the precomputed table, the answer is simply \(F(t)\). Otherwise write

$$q=\left\lfloor {t-a\over p}\right\rfloor,\qquad r=a+((t-a)\bmod p).$$

Repeatedly applying the affine-periodic identity gives

$$\boxed{\operatorname{BB}(N)=F(r)+q\,s.}$$

For the target \(N=10^{18}\), the code uses \(t=10^{18}-2\), \(q=14084507042253513\), and \(r=575\). The stored table supplies \(F(r)\), and the final decimal value is printed by the program.

6. Worked Checkpoint: \(N=1000\)

Here \(t=N-2=998\). The period formula gives

$$q=\left\lfloor {998-512\over 71}\right\rfloor=6,\qquad r=512+((998-512)\bmod 71)=572.$$

The finite simulator gives \(F(572)=791\). Therefore

$$F(998)=F(572)+6\cdot 118=791+708=1499,$$

which matches the official checkpoint.

How the Code Works

The C++ program first builds \(F(0),F(1),\dots,F(10000)\). It then runs small correctness checkpoints: \(\operatorname{BB}(0)=\operatorname{BB}(1)=\operatorname{BB}(2)=0\), \(\operatorname{BB}(3)=1\), \(\operatorname{BB}(5)=-1\), and \(\operatorname{BB}(1000)=1499\). It also checks the affine period \(F(m+71)=F(m)+118\) throughout the post-transient range.

The Python and Java versions use the same constants, the same threshold table, and the same extrapolation formula. The only implementation-level difference is numeric representation: Python integers are arbitrary precision, Java uses long, and C++ prints a __int128_t value through a small decimal conversion helper.

Complexity Analysis

Let \(T=10000\) be the table limit used by the implementation. The universal simulation is finite and stores \(O(T)\) cells in the Boolean window. Once the table and the period check are complete, a query for any \(N\), including \(10^{18}\), is answered by a constant number of integer operations.

Thus the target computation has fixed precomputation cost and \(O(1)\) extrapolation time. A naive simulation up to \(N=10^{18}\) would be infeasible because it would need to wait for an enormous number of drop and pickup events.

References

1. Problem page: Project Euler 993
2. Finite-state cycle detection: Wikipedia - Cycle detection
3. Cellular automata and local update rules: Wikipedia - Cellular automaton