×

# MCOINS - Coins Game

 1 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: $i = 0$ : since the person whose chance it is has no coins to take, he/she loses. Hence, $dp[0] = 0$. $i = 1$ : only one coin, the person whose chance it is can take it and win the game. So, $dp[1] = 1$. $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$. $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 answered 01 Dec '18, 01:05 5★preet_t 11●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,169

question asked: 30 Oct '18, 09:16

question was seen: 253 times

last updated: 14 Jan, 20:33