2154. 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.

Constraints - `1 ≤ p ≤ 1000` - `0 ≤ stones in a pile ≤ 10^9` - at least one pile holds at least one stone - A moves first and takes the whole of the largest pile - B takes one stone from the largest pile - ties for largest are broken by the smallest index - the player who takes the last stone wins and the game ends there