328. Coin Game Winner Where Every Player Has Three Choices

Two players, A and B, alternately remove coins from a pile of n coins, with A moving first. On each turn a player must remove exactly 1, x, or y coins (a fixed x and y, valid only if the pile has at least that many coins). The player who cannot make a move (the pile is empty on their turn) loses. Assuming both play optimally, print 'A' if the first player wins, otherwise print 'B'.

Input: Three lines: n (pile size), x, and y (the two special move sizes). Output: Print a single character - "A" if the first player wins with optimal play, otherwise "B".

0 <= n <= 10^4, 1 <= x, y <= 10^4

This is a classic 'Nim-like' combinatorial game DP - the recurrence structure (win[i] true if some move leads to a false state) is a template reused across a WHOLE family of two-player optimal-play games, not just this specific coin variant.

Determine who wins a coin-removal game where each player removes 1, x, or y coins per turn, both playing optimally. Brute force: Try every possible sequence of moves for both players directly, exploring the full game tree - this is exponential without memoization, since the same pile-size sub-game recurs across many different move sequences. Optimised: Since win[i] only depends on whether ANY reachable smaller state is a LOSS for the opponent, and this only depends on the pile SIZE (not the specific history of moves that led there), memoizing win[] by pile size directly avoids recomputing the same game-theoretic sub-question repeatedly.

Recursively simulate the game: from a pile of size n, the current player wins if removing 1, x, or y coins (whichever are valid, i.e. the pile has at least that many) ever leaves the opponent facing a position where the opponent loses. This directly encodes the rules of the game and optimal play, but without any caching, evaluating win(n) branches into up to three recursive calls at every level, causing the number of evaluations to blow up exponentially with n. Time: O(3^n) Space: O(n)

Use the same win(n) recursion as brute force, but cache the result for each value of n the first time it is computed, since win(n) only ever depends on win(n-1), win(n-x), and win(n-y). Because there are only n+1 distinct subproblems, memoization turns the exponential branching of brute force into a linear number of unique evaluations, each doing O(1) work given its cached dependencies. Time: O(n) Space: O(n)

Fill in win[0], win[1], ..., win[n] iteratively from smallest to largest, where win[i] is true if any of win[i-1], win[i-x] (if i >= x), or win[i-y] (if i >= y) is false. Since win[i] only ever depends on the at most max(x, y) most recent values, only that many previous results ever need to be kept in a small rolling buffer instead of a full array covering every value from 0 to n, and the iterative bottom-up order also avoids any recursion depth concerns for n up to 10^4. The first player wins if win[n] is true, otherwise the second player wins. Time: O(n) Space: O(max(x,y))

1. win[i] = true if the player about to move, with i coins remaining, can FORCE a win. win[0]=false (no move possible, so the player to move loses). 2. win[i] = true if ANY legal move leads to a state where the OPPONENT loses: win[i-1]==false, or (i>=x and win[i-x]==false), or (i>=y and win[i-y]==false). 3. The overall answer is 'A' if win[n] is true (the first player, facing the full pile, can force a win), otherwise 'B'.

Time: O(n) - building win[] bottom-up, with O(1) work checking the (at most 3) possible moves at each pile size. Space: O(n), for the win[] array.

Test n = 0 (the pile starts empty, so the first player can't move and loses, printing "B") and n as large as 10^4 for the O(n) DP's performance.

Be ready to explain the general game-theory DP pattern here: 'the current player wins if THEY CAN move to ANY state where the opponent LOSES' - this exact template (checking for at least one losing-for-opponent successor) generalizes to many other combinatorial game problems.