PROBLEM LINKS
DIFFICULTY
EASY
PROBLEM
To solve this challenge, you need to consider each possible value of n as a winning or losing position. For example:
n = 3 is a winning position for the current player, because the player can take 3 gems and win the game.
n = 2 is a losing position for the current player, because he cannot make a move (the minimum number of gems that must be removed during a move is 3).
EXPLANATION
Moving Optimally
For n = 13, the current player (we’ll call them P1) can make either of the following moves:
Remove 7 gems, leaving 6 gems on the game board. This allows the next player, P2, to take 4 gems and win the game since P1 cannot make any more valid moves. This move is not an optimal one for P1 to make, because it causes P1 to lose the game.
Remove 4 gems, leaving 9 gems on the game board. Then the next player, P2, can win the game by optimally taking 7 gems. This move is also not optimal for P1.
Remove 3 gems, leaving 10 gems on the game board. Then, P2 can take 3, 4 or 7 gems and would still lose as P1 would have valid moves in each case. This move is optimal for P1, because P1 is the one making the move and it will result in winning the game.
As we assume that both players are moving optimally by always choosing whichever move will put their opponent in a losing position, we consider to be a winning position.
If no possible move results in the next state being a losing position, then the player loses. In other words, if a player cannot make a move from their current state that results in the next state being a losing position, the player is in a losing position!
This realisation leads to the following recursive formula:
dp[0] = 0
dp[1] = 0
dp[2] = 0
dp[3] = 1
dp[4] = 1
dp[5] = 1
dp[6] = 1
dp[7] = 1
for i > 7,
dp[i] = 1 if dp[i-7]==0 or dp[i-4]==0 or dp[i-3]==0
dp[i] = 0 otherwise
Solution:
t = int(raw_input())
for tc in range(t):
n = int(raw_input())
dp = [0,0,0,1,1,1,1,1]
for i in range(8,n+1):
dp.append(1 if (dp[i-7]==0 or dp[i-4]==0 or dp[i-3]==0) else 0)
print "A" if dp[n]==1 else "B"