murdocc007's blog

By murdocc007, history, 9 years ago, In English

Can anyone give an idea on how to solve this a2oj problem. I already read it's solution here but)I can't seem to get it.

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
7 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Lets simulate some possible game outcomes to better understand how the game works.

Suppose we have 2 players. On the first turn, player 1 can decide to take one stone or zero. I'll denote these options as 1−>1 and 1−>0, respectively.

On the second turn, we have 4 possibilities.

After 1−>0, we must take one stone and decide whether to take one stone or not. After 1−>1, we decide whether to take one stone or not. Note that after any of these possibilities in the second turn, there are only 2 possible number of stones removed from the pile: 1 or 2.

If you repeat this process for the third turn, you'll realise that either 2 or 3 stones are taken from the pile.

Hence, after turn t, either t or t−1 were taken off the pile of stones. Since we must check for victory regardless the other players strategies, we should discard t−1 because the previous player will choose to pick this if it wins the game.

So, the answer is YES if N=X, and NO otherwise. If N > M, remove the necessary turns for all players to put N in the range [1, M].