Show problems as
Classic problem #1140MediumArrayMathDynamic ProgrammingMinimaxPrefix SumGame TheoryZero-Sum Game

Stone Game II

Real-world version: Front Loaded Tray Haul
Tracked in this browser only
Read Stone Game II on LeetCode(opens in a new tab)

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

A belt presents piles trays in a fixed order, piles[0] nearest the loading bay. Tray i holds piles[i] blanks. Two crews, Rhea first and then Tomas, take turns clearing trays off the front of the belt.

An allowance m starts at 1. On a turn the crew takes the first x trays that are still on the belt for any x with 1 <= x <= 2 * m, and x may not exceed the number of trays remaining. Every blank on a taken tray goes to that crew. Once the turn is over the allowance becomes max(m, x), and it carries over to the other crew as well. Play stops when the belt is empty.

Both crews want as many blanks as they can get for themselves. Return the number of blanks Rhea ends up with when neither crew ever plays worse than it has to.

Examples

Example 1

Input
piles = [3, 9, 1, 2]
Output
12

The reported figure is the total on Rhea's side of the table at the end of a run in which each crew always chooses the batch size that serves it best.

Example 2

Input
piles = [8]
Output
8

One tray is on the belt and the opening allowance already covers it, so Rhea clears the belt on the first turn.

Example 3

Input
piles = [5, 5]
Output
10

The opening allowance permits up to two trays, so Rhea can clear both and Tomas never gets a turn.

Example 4

Input
piles = [1, 1, 1, 1, 1, 1, 1]
Output
4

Seven trays each hold one blank and the figure returned is Rhea's share of the seven.

Constraints

  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 10^4

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 best_first_haul(trays: list[int]) -> int:
Java
public int bestFirstHaul(int[] trays)

More on the same topics