2151. The Standings On a Circular Track

A circular track has n cells, numbered 0 to n - 1. Cell 0 is the start. p tokens all begin on cell 0 having completed 0 laps.

There are k rolls, taken in order. Roll i, counting from 0, belongs to token i mod p. A roll of r advances that token r cells forward along the circle. Every time a token arrives at cell 0, it has completed one more lap, including when it arrives there by passing the start several times in one roll.

Print the standings: one line per token, ordered by laps completed from most to fewest; ties broken by the higher cell number; remaining ties broken by the lower token number. Each line holds the token number, its laps and its cell.

``` n = 5, p = 2, rolls 1 2 3 4 5 6

token 0 takes rolls 1, 3 and 5, a total of 9 cells: 1 lap and cell 4 token 1 takes rolls 2, 4 and 6, a total of 12 cells: 2 laps and cell 2

1 2 2 0 1 4 ```

## What most people try first

Keeping only the current cell and adding a lap when the new cell is smaller than the old one. That is right for rolls shorter than the track and wrong as soon as a roll is longer: a token on cell 4 of a track of 5 that rolls 11 ends on cell 0 having passed the start three times, and "the cell went down" counts one of those.

## Total distance, then divide once

Keep each token's TOTAL distance travelled rather than its cell. Then:

laps = total / n integer division cell = total mod n

One division at the end, nothing to get wrong per roll, and arbitrarily long rolls handled for free.

## Why that is the same thing

Define the token's position after travelling total cells as the cell it sits on, and a lap as an arrival at cell 0. Advancing one cell at a time from cell 0, the cell after t single steps is t mod n, since the sequence of cells is 0, 1, ..., n - 1, 0, 1, ..., which is exactly the remainder cycle. An arrival at cell 0 happens precisely at those t that are positive multiples of n, and the number of positive multiples of n that are at most total is total / n rounded down. So laps and cell are the quotient and the remainder of the same division, and the step-by-step count agrees with it. That equivalence is what the two implementations verifying this problem check, one walking single cells and one subtracting whole laps in doubling chunks, neither using the division operator.

## Overflow

A roll reaches 10^9 and there are up to 50000 rolls, so one token can travel as far as 5 * 10^13 cells. The signed 32 bit limit is 2147483647, so the running total must be held in a 64 bit type; 5 * 10^13 is comfortably inside signed 64 bit, which reaches about 9.2 * 10^18. In JavaScript a plain Number is exact below 2^53, which is about 9.007 * 10^15, so 5 * 10^13 is exact as a Number and no BigInt is needed; what must be avoided there is any bitwise operator on the total, since those truncate to 32 bits.

A declared test sends one token three rolls of 10^9, a total of exactly 3 * 10^9. A 32 bit accumulator wraps that to -1294967296 and reports -129496729 laps on cell -6 instead of 300000000 laps on cell 0.

## Order is part of the answer

The three-key ordering is stated because any other reading gives a different set of lines, and a program cannot guess it. Note the middle key runs the other way from the last: higher cell beats lower, then LOWER token number beats higher.

## Cost

O(k) to accumulate and O(p log p) to sort, so O(k + p log p), with O(p) memory.

Constraints - `1 ≤ n ≤ 1000` - `1 ≤ p ≤ 1000` - `1 ≤ k ≤ 50000` - `1 ≤ each roll ≤ 10^9` - every token starts on cell 0 with 0 laps - a token completes a lap on every arrival at cell 0, including several in one roll - the standings order is laps descending, then cell descending, then token number ascending