MCOINS - Coins Game

general
1

question->https://www.spoj.com/problems/MCOINS/
anyone please share your approach

2

Consider only one stack. Let dp[i] store a boolean denoting whether the person whose turn it is will win when there are i coins remaining in the stack.

Following are the base cases:

  1. i = 0 : since the person whose chance it is has no coins to take, he/she loses. Hence, dp[0] = 0.
  2. i = 1 : only one coin, the person whose chance it is can take it and win the game. So, dp[1] = 1.
  3. i = k : the person whose chance it is can select all the k coins and win since the other cannot take any more. Hence, dp[k] = 1.
  4. i = l : similarly, dp[l] = 1.

Now at each turn a person picks either 1, k, or l coins. To win, one would try to take coins in such a way that with the remaining coins the opponent cannot win. In our case, if either of dp[i-1] , dp[i-k] , dp[i-l] is 0 then dp[i] will be 1 as we can take that may number of coins such that dp[rem] = 0 . But if all of dp[i-1] , dp[i-k] , dp[i-l] are 1 then in all the three possible options, the the game goes to a state where the opponent wins making dp[i] = 0 .
Hence, dp[i] = !(dp[i-1]\&dp[i-k]\&dp[i-l]).
Here is my code: LINK

1 Like