A Repeating Roll Pattern, a Billion Billion Rolls
A token starts on square 1 of a track of n squares, with jumps that work
exactly as in #2148: at most one per roll, never chaining, and a roll whose
target is past square n is wasted and moves nothing.
The rolls are not a list this time. A pattern of L rolls is given, and it
repeats for ever: roll 1 is the first entry, roll L the last, roll L + 1 the
first again. Exactly k rolls are made.
Print the final square and the number of wasted rolls.
The catch is k, which reaches 10^18. Carrying out 10^18 rolls at a
billion a second takes about thirty years.
``` n = 10, no jumps, pattern 2 3, k = 4 -> 8 1
1 -> 3 -> 6 -> 8, then 8 + 3 = 11 is past the end, so that roll is wasted ```
``` n = 10, no jumps, pattern 2 3, k = 10^18 -> 10 999999999999999996
after the trace above, the fifth roll is 2 and takes the token 8 -> 10, and from square 10 both 2 and 3 overshoot, so every roll from the sixth onwards is wasted. Exactly four rolls ever move the token. ```
## What most people try first
A loop over k. Correct and unfinishable. The next idea is usually to run one
whole pattern and multiply, which is wrong because the token is on a different
square at the start of each pass, so each pass does something different.
## The state is a PAIR, and there are not many of them
What determines the future is not the square alone and not the position in the pattern alone, but both together:
state = (square, index into the pattern)
There are at most n * L such states, which is at most 100000 at the stated
limits. Each state has exactly one successor, so after at most n * L + 1
rolls a state must repeat, and from that point the whole sequence of rolls
repeats identically for ever. The sequence of states is a tail followed by a
loop:
roll: 0 1 2 ... s-1 | s s+1 ... s+c-1 | s s+1 ...
[----- the tail ----] [-- the loop, length c --] [ again ...
Record, for every state met, the roll number it was first met at AND the number
of rolls wasted up to that point. When a state recurs at roll t having first
appeared at roll s:
loop length c = t - s
wasted per loop = wastedAt(t) - wastedAt(s)
Then skip whole loops in one step: with rem = k - t rolls still to make, do
rem / c whole loops by adding rem / c times the per-loop waste to the
total, and advance the roll counter by rem / c times c. What is left is
fewer than c rolls, which are carried out one at a time, and the token's
square is already correct because skipping whole loops returns it to the state
it was in.
## Why the skip is exact
Let step be the function taking one state to the next. The loop found means
step applied c times to the state at roll s gives that same state. Since
step is a function, applying it c more times gives the same state again, so
by induction the state at roll s + i + jc equals the state at roll s + i
for every i and every j at least 0.
The waste is where care is needed, because unlike the square it ACCUMULATES
rather than repeating. The rolls from s to t - 1 form one complete loop, and
the rolls from s + jc to s + (j+1)c - 1 pass through exactly the same
states in the same order, so each of them wastes exactly the same amount. The
per-loop waste is therefore constant and multiplying it by the number of whole
loops is exact. That is the one place where a problem of this shape differs
from #2147, where the answer depended only on the state reached and nothing
had to be accumulated.
## Overflow
k reaches 10^18, and so does the answer for the wasted count, since every
roll may be wasted. The signed 32 bit limit is 2147483647, so both need 64
bits; signed 64 bit reaches about 9.2 * 10^18, so 10^18 and the products
formed from it are inside it, because the per-loop waste is at most c and
(rem / c) * c is at most k.
JavaScript needs BigInt for k and for the wasted total: a plain Number is
exact only below 2^53, about 9.007 * 10^15, so 10^18 is not the value in
the input and the division rem / c on it would be wrong. Square numbers and
pattern indices stay small and need no BigInt.
## Cost
O(n L) states visited at most once each, so O(n L) time and memory,
independent of k. At the limits that is 100000 states whether k is 4 or
10^18.