Who Takes the Last Stone
There are p piles of stones. Two players, A and B, take turns, A first.
Neither of them is playing well: both follow a strategy that is written down
here, so there is nothing to work out about optimal play and the answer is
whatever the two strategies produce.
A's move: take the WHOLE of the largest pile
B's move: take ONE stone from the largest pile
In both cases, if several piles are tied for largest, the one with the SMALLEST index is chosen. Piles are indexed from 0.
The player who takes the last stone on the board wins, and the game ends at
that moment. Print the winner, A or B, and the total number of moves made,
separated by a space.
``` p = 2, piles 2 2 -> A 3
move 1 A empties pile 0, leaving 0 2 move 2 B takes one from pile 1, leaving 0 1 move 3 A empties pile 1, leaving 0 0, and takes the last stone ```
``` p = 2, piles 1 1 -> B 2
move 1 A empties pile 0, leaving 0 1 move 2 B takes the one stone in pile 1, which is the last stone ```
The second example is the point of the problem: B's strategy of taking a single stone takes the last stone too, when the last stone is all that is left.
## What most people try first
Reasoning about parity: A removes a whole pile each move, so surely A makes p
moves and the winner follows from whether p is odd. That is wrong in both
directions. B's single-stone moves can empty a pile as well, which reduces the
number of piles A gets to clear, and the examples above have the same p and
different winners. The specification has to be carried out, not summarised.
## Why the game always ends, and quickly
Every move removes at least one stone, so the game ends. The sharper bound is
what makes a direct simulation cheap: each of A's moves empties a pile, so A
makes at most p moves, and B moves only between A's moves, so B makes at most
p + 1. The total number of moves is therefore at most 2p + 1, whatever the
pile sizes are. A pile of a billion stones does not cost a billion moves,
because A takes all of it at once and B only ever faces it when it is the
largest, which is at most a handful of times.
So the loop runs O(p) times, and finding the largest pile by scanning costs
O(p) each time, giving O(p^2) with p at most 1000. That is a million
operations.
## The method
moves = 0
turn = A
while some pile is non-empty:
at = the index of the largest pile, smallest index on a tie
if turn is A: pile[at] = 0
else: pile[at] = pile[at] - 1
moves = moves + 1
if every pile is now empty: this player took the last stone, stop
switch turn
The order of the last three lines is the whole specification. The move is counted, then the board is tested for being empty, and only then does the turn change. Testing for empty after switching the turn reports the wrong winner on every input.
## Why the tie-break has to be stated
Two piles tied for largest are genuinely different choices with different
futures. On 1 5 with the tie-break as given, A empties pile 1, the larger
one, and B then takes the single stone of pile 0 and wins. Pick the other pile
and the game runs differently. "Take the largest pile" is not a specification
while ties are possible, which is why the smallest index is pinned here, and
why the second implementation used to verify this problem keeps the piles in a
sorted container and has to reconstruct that same tie-break from the stored
index rather than finding it by a left to right scan.
## Cost
O(p) moves, each O(p) to find the largest, so O(p^2) time and O(p)
memory. Pile sizes reach 10^9 and are only ever compared and decremented, so
nothing overflows a signed 32 bit integer, whose limit is 2147483647.