You are not logged in. Please login at www.codechef.com to post your questions!

×

MCOINS - Coins Game

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

asked 30 Oct '18, 09:16

sonuexpc_'s gravatar image

1★sonuexpc_
1
accept rate: 0%


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

link

answered 01 Dec '18, 01:05

preet_t's gravatar image

5★preet_t
112
accept rate: 0%

edited 14 Jan, 20:33

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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