question->https://www.spoj.com/problems/MCOINS/ anyone please share your approach asked 30 Oct '18, 09:16 ![]()
|
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:
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$ . answered 01 Dec '18, 01:05 ![]()
|