Show problems as
Classic problem #1406HardArrayMathDynamic ProgrammingMinimaxGame TheoryZero-Sum Game

Stone Game III

Real-world version: Clearing The Salvage Row
Tracked in this browser only
Read Stone Game III on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Two graders, Iris and Otto, clear a row of salvaged crates. merits[i] is the signed merit of the crate standing i places from the head of the row: a damaged crate carries a negative merit and still counts against whoever takes it.

Iris goes first and the two then alternate. On a turn the grader on duty takes the first one, two or three crates still standing, in a single block from the head of the row, and adds their merits to a personal score. A turn must take at least one crate, and the row shortens as it goes, so the last grader to move may have fewer than three left to choose from. Play ends when the row is empty.

Both graders know the whole row from the start and both play to finish with the largest personal score they can force, caring about nothing else.

Return "Iris" if she ends with the larger score, "Otto" if he does, and "Draw" if the two scores are level.

Examples

Example 1

Input
merits = [5, -2, 8, 40, -6]
Output
"Otto"

One line runs: Iris clears 5, -2 and 8, Otto clears 40, and Iris is left with the crate at -6. That ends 5 against 40, so the second grader has the larger score.

Example 2

Input
merits = [7, 7, 7, 7]
Output
"Iris"

Iris clears three crates for 21 and the single crate left hands Otto 7.

Example 3

Input
merits = [-11, -11, 22]
Output
"Draw"

Iris clears all three crates in one turn and finishes on 0, and Otto never gets a move, so he finishes on 0 too.

Constraints

  • 1 <= merits.length <= 5 * 10^4
  • -1000 <= merits[i] <= 1000

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def salvage_winner(merits: list[int]) -> str:
Java
public String salvageWinner(int[] merits)

More on the same topics