NIMGAME - Special Nim Game

no tags 

In this variant of the Nim game, a pile of N stones is placed between two players. The players take alternating turns and remove some stones. The player who takes the last stone wins.

There are two restrictions however:

  1. The first player has to remove between 1 and N-1 stones.
  2. After the first move, the next player has to remove between 1 and 2·k stones, where k is the number of stones removed in the last move.

If both players play perfectly, then it is possible to determine which player will win the game. Note that during the game the game state can be described by the number of remaining stones and the number of stones which can be taken in the next move. Each game state is either a winning position or a losing position.

You have to determine for which values of N (2 ≤ N ≤ 2000) the second player has a winning strategy.


There is no input for this problem.


Print the values N for which the second player has a winning strategy.



Obviously, the example output is incomplete and shows only the first three values and the last value to be printed.

hide comments
ALi Ibrahim: 2017-04-17 19:05:36

Awesome problem, really really enjoined solving it :D
Big Thanks for the problem setter :V

b_aditya: 2017-01-02 06:47:49

Last edit: 2017-01-02 06:50:43
jkelava6: 2015-06-29 12:55:18

Last edit: 2015-06-29 13:02:24

Added by:Adrian Kuegel
Time limit:0.833s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET