NIMGAME - Special Nim Game

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.

Input

There is no input for this problem.

Output

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

Example

Output:
2
3
5
...
1597

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


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

hide comments
2023-03-22 19:04:45 cegprakash
useful read ahead before solving this problem: https://leetcode.com/problems/nim-game/solutions/275817/intuition-behind-minimax-problems-with-detailed-explanation-and-code/
2017-04-17 19:05:36 ALi Ibrahim
Awesome problem, really really enjoined solving it :D
Big Thanks for the problem setter :V
2017-01-02 06:47:49


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


Last edit: 2015-06-29 13:02:24
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.