Two friends play a game with two jars of marbles, holding a and b marbles. They take turns. On
a turn a player either
- takes between 1 and
kmarbles from one jar (at most as many as it holds), or - takes exactly one marble from each jar (only when both jars are non-empty).
The player who takes the last marble wins, so a player facing two empty jars has lost.
Return 1 if the player about to move can force a win, whatever the other player does, and -1
if the other player can force a win.
Examples
Input: a = 2, b = 1, k = 2
Output: -1
Explanation: the moves lead to (1, 1), (0, 1), (2, 0) and (1, 0). From each of them the
opponent empties both jars in one move, so every move loses.
Input: a = 4, b = 4, k = 3
Output: 1
Explanation: taking three from one jar leaves (1, 4), from which the opponent cannot win.
Input: a = 3, b = 3, k = 3
Output: -1
Constraints
0 <= a, b <= 601 <= k <= 6
Goals
- Define the value of a game position recursively from the positions after each move
- Memoise the recursion so every position is solved once
- Treat the position with no legal move correctly