Sharing is caring!
Problem Statement
A and B are playing a game. At the beginning there are n coins. Given two more numbers x and y. In each move a player can pick x or y or 1 coins. A always starts the game. The player who picks the last coin wins the game. For a given value of n, find whether A will win the game or not if both are playing optimally.
Solution
We use dynamic programming (DP). If A lost in the game with i-1 (dp[i-1] == false), it means that B could come up with a strategy that leaves a value V with max(1,x,y)<V<=min(1,x,y) + max(1,x,y) in the second-to-last move for A. That way even if A would pick the least amount of coin (min(1,x,y)) in order to leave a maximum leftover for B, the leftover for B would be smaller than 1 or x or y, making B the winner. Now, if we consider i (one unit greater than i-1) this means that B would not be able to perform the above mentioned move in the second-to last step, thus letting A win.
public class CoinInLine {
public static boolean solve(int n, int x, int y) {
boolean[] dp = new boolean[n+1];
dp[0] = false;
dp[1] = true;
for (int i=2; i<=n; i++) {
if (i-1>=0 && dp[i-1] == false) {
dp[i] = true;
} else if (i-x>=0 && dp[i-x] == false) {
dp[i] = true;
} else if (i-y>=0 && dp[i-y] == false) {
dp[i] = true;
} else {
dp[i] = false;
}
}
return dp[n];
}
public static void main(String[] args) {
System.out.println(solve(5, 3, 4));
}
}