The Square Only One Token May Hold
Two tokens, player 0 and player 1, both start on square 1 of a track of n
squares. Jumps work exactly as in #2148: at most one per move, never
chaining.
The k rolls are shared. Roll 1 belongs to player 0, roll 2 to player 1, roll
3 to player 0, and so on, so roll i counting from 0 belongs to player
i mod 2. A roll that overshoots is simply lost and the turn passes; it is not
re-rolled and it is not reported.
Each move is carried out in this order, and the order is the problem:
1. if pos + r > n, the roll does nothing at all and the move is over
2. otherwise the moving token goes to pos + r
3. then, if that square starts a jump, the moving token takes it, once
4. then, if the OTHER token is on the square the moving token has ended on,
and that square is not square 1, the other token is sent back to square 1
Square 1 is shared ground: both tokens may stand on it and nobody is sent back from it.
Print the final square of player 0, the final square of player 1, and how many times a token was sent back.
``` n = 10, no jumps, rolls 3 3 3 3 -> 1 4 3
player 0 moves to 4. Player 1 moves to 4 and sends player 0 back to 1. Player 0 moves to 4 and sends player 1 back to 1. Player 1 moves to 4 and sends player 0 back to 1. Three send-backs, and player 0 finishes on 1. ```
## What most people try first
Checking for the shared square before the jump. That gets the collisions on the wrong square: a token that lands on 7 and jumps to 2 collides with whoever is on 2, not with whoever is on 7. Step 3 strictly precedes step 4, and the statement is written as a numbered list for that reason.
The other frequent slip is sending the MOVING token back instead of the one that was already there. The rule is that the arrival wins the square, so it is always the resident that leaves.
## Why the order of the four steps settles the question
Each step reads only state that the steps before it have already finalised, so the move is a well defined function of the state before it.
Step 1 reads the moving token's square and the roll. Step 2 writes the moving token's square. Step 3 reads the square just written and rewrites it. Step 4 reads both tokens' squares, both now final for this move, and may rewrite the other token's. Nothing is read after it is overwritten and the resident's position is never used to decide the mover's, so swapping any two of these steps genuinely changes the answer rather than merely the code. That is why a specification like this one has to be numbered, and why "the players collide" on its own is not a specification at all.
## The boundary that breaks a careless implementation
A token may be sent back to square 1 and then meet the other token there. Nothing happens, because step 4 excludes square 1 explicitly. Without that exclusion the two tokens would send each other back from the start square every time one of them failed to move, which would be counted as a send-back and inflate the answer.
If n is 1 both tokens sit on square 1 and every roll overshoots, so the
answer is 1 1 0. That is a declared test.
## Cost
O(n + m) to build the jump destinations and O(1) per roll, so
O(n + m + k) overall, with O(n) memory.