PizzaEatingGame
TCO20 Wildcard Parallel · 2020-10-06 · by misof
Problem Statement
Adam and Becky have a pizza. The pizza is cut into N slices, numbered from 0 to N-1 in order. (For each i, slice i is adjacent to slices (i-1) mod N and (i+1) mod N.) Slice i contains olives[i] olives.
Adam and Becky both love olives and so they each want to get as many olives as possible. They are going to divide their pizza in a competitive way. They will take alternating turns. Adam goes first. In each turn, the active player must take exactly one slice from each contiguous segment of slices. Below are two example beginnings of the game for N = 10.
- Adam takes slice 7. The remaining nine slices still form one contiguous segment, so Becky will now take any one of those slices. She takes slice 6. The remaining eight slices still form one contiguous segment, so Adam will pick just one slice in his next move.
- Adam takes slice 7. Becky takes slice 3. This divides the remaining eight slices into two contiguous segments: {8,9,0,1,2} and {4,5,6}. Adam will now take one slice from each of these segments. E.g., he might take slices 9 and 4, or slices 0 and 5 (but not slices 0 and 1).
Compute and return the number of olives Adam will have at the end of the game.
Constraints
- olives will have between 3 and 500 elements, inclusive.
- Each element of olives will be between 0 and 1000, inclusive.
{1, 2, 1, 100, 1, 2, 1, 50}
Returns: 104
The optimal strategy for both players is clear: Adam must take 100, Becky must take 50, then Adam will take both 2s, and finally Becky takes all four 1s.
{99, 5, 6, 5, 100}
Returns: 110
{0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0}
Returns: 2
{0, 0, 0}
Returns: 0
{1, 2, 3}
Returns: 4
Submissions are judged against all 139 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PizzaEatingGame with a public method int eat(vector<int> olives) · 139 test cases · 2 s / 256 MB per case