Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### iamrk's blog

By iamrk, history, 8 months ago, ,

Alice and Bob are playing a game. There are 'n' discs. Alice starts the game. The players play alternatively thereafter. In each turn, the players have to choose a number which is a power of 4, say 'd' and subtract it from 'n'. So 'n' will be 'n-d' now. A player who cannot choose a power of 4 to deduct in his turn will lose the game.

Example: if n = 4, then Alice will choose 4 and end the game for Bob. As he will be left with 0 in his turn and he cannot choose a power of 4.

What will be the optimal strategy for the players in this case? And in general how to find the optimal strategy for players? What are the rules of thumb?

•
• -3
•

 » 8 months ago, # |   0 First, if n is not a multiple of 4, map it to the greatest but smaller than it multiple of 4. Now, player 1 will lose iff or .
•  » » 8 months ago, # ^ |   0 If n = 5, the mapped number will be 4, so 'n' is now 4. and n % 20 => 4 So player 1 should win. But here there are only two choices: player 1 can take out 4 and then player two will take out 1 so player two will win. player 1 can take out 1 and then player two will take out 4 so player two will win. So anyways here player two will win.? Am I missing something? And how did you arrive at this solution?
•  » » » 8 months ago, # ^ |   +5 I forgot the players can use the number 1. With that, you don't need to round n down and the answer should be: player 1 will lose iff or .I just wrote a dp solution and found the pattern by watching the outputs for some inputs.
•  » » » » 8 months ago, # ^ |   0 I got it now. Thanks!
 » 8 months ago, # |   +5 This question is live in one of the hiring challenge on HackerEarth