DAY 2

PROBLEM 1

The game

Two players play the pile game. The pile contains N chips. The players remove any number of chips from the pile with alternate moves. The player who removes the last chip wins the game.

Playing the game you must respect the following rules:

The player who begins the game may remove any number L1 of chips except that he cannot take the whole pile, 1<=L1<=N-1.

From then, the players alternate moves each removing one or more chips but not more than twice as many chips as the preceding player has taken. So the player who has the turn to move may remove from pile L2 chips, where 1<=L2<=2*L1, (L1 is the number of chips removed by the preceding player).

You must write a program to play against the computer and to win.

In case your strategy is an appropriate one, and are you who begin the game, then you always win.

First, you have to read from the file c:\day2\problem1\game.in, the number N of the chips in the pile, after this you have to determine the number L1 of the chips that you remove from the pile.

With these two values you will call the procedure move(N1,L1,N2,L2); which will return two values: the number L2 of the chips removed by the computer and the number N2 of chips remained in the pile after your removal. It seems that N2=N1-L1. At first N1=N.

After this you have to determine the next quantity L1 of chips to be removed and the new value of N1, (N1=N2-L2) and will call the procedure move, and so on.

Your program will terminate when the pile will be empty. The player who removes the last chip wins the game.

Example

N=10

Your move Computer’s move

N1 L1 N2 L2

10 2 8 1

7 2 5 1

4 1 3 1

2 2 0

Congratulations! You won!

Note. Take care your program to respect the restrictions of the game. In the case a move is not allowed one, the program automatically will terminate.

The procedure move controls each of your move. In the case your strategy is not optimal one, then the computer will win.

Input file

Input file c:\day2\problem1\game.in has only one line where is the integer N which denotes the number of chips in the pile, 4<=N<=2000.

Output file

There is no output file. The procedure move will show who will win the game.

Executable file c:\day2\problem1\game.exe

Maximal time per test 1 sec.

Instructions for pascal programmers.

Your program will contain the instruction:

Uses moveun;

The procedure move, is:

Procedure move(N1,L1:Integer;Var N2,L2:Integer);

Where N1 is the number of chips in the pile before your move, L1 is the number of chips that you will remove. N2 is the number of chips remained before the computer’s move, N2=N1-L1, whereas L2 is the number of chips removed by the computer.

First you will call the procedure newgame (only once ) after that you may call as many time as you wish the procedure move.

The procedure newgame is:

newgame;

INSTRUCTIONS FOR C/C++ PROGRAMMERS

Have the following in your source file:

#include “moveun.h”

Include move.obj in project. Have the following in your source file:This will provide the following declarations:

void newgame (void); /* must be called first */

void move (int,int.int &,int &);

Also o create a project called game.prj which should include your program (game.cpp) and the library for interaction named moveun.obj. To do this you need to use the project menu of IDE and choose the open option to create a project, and then use add item to include your source file (game.cpp) and the file moveun.obj.