NIM (25 points)
The rules of the
- NIM is a strategy game played by two
partners on a table with n heaps of small sticks.
- The two partners are your program and the evaluation library.
- Your program always makes the first move.
- The partners alternatively make one move each. A move consists in taking
out an arbitrary number (>0) of sticks from one of the heaps.
- A player loses if he can't move any more, i.e. if all the heaps on the
table contain exactly zero sticks.
- Write a program that plays NIM.
- The goal of the first player (your program) is to leave the table empty,
that is to win.
- The other player (the evaluation library) tries, at its turn, to win.
- If your program plays well, it will win in all the tests supplied for the
Input and Output
Your program doesn't use any file for reading or writing; it will also
neither read something from the keyboard, nor display anything on the screen.
It will receive all the input data from the NimLib library.
- All the numbers given back by the NimLib library will be integer, in the interval
- A game is over when one of the players wins.
- A game has to be finished in 2 seconds (on a Pentium/166Mhz).
We guarantee that the evaluation library finishes its moves in one second.
A library called NimLib can and has to be used by your program:
in Pascal : Uses NimLib;
In C : #include
The functions and the procedures in NimLib are (in Pascal and then in C):
function NumberOfHeaps : Integer;
int NumberOfHeaps (void);
- Returns the number of heaps on the table.
function NumberInHeap (Heap : Integer) :
int NumberInHeap (int Heap);
- Returns the number of sticks in the Heap heap.
procedure MyMove (Heap, Number :
void MyMove (int Heap ; Int Number);
- Calling the procedure means that your program extracts a number of sticks
equal with Number from the Heap heap. If the procedure doesn't
stop your program, it will return in the variables
ComputerMoveHeap and ComputerMoveNumber the
move of the evaluation library that succeeds your move.
- This procedure stops your program if:
Your program won the game.
The evaluation library won the game.
The move of your program is not correct.
The variables in NimLib are (in Pascal and then in C):
ComputerMoveHeap : Integer;
- the heap that the evaluation library extracts from, on its turn succeding
the move of your program.
ComputerMoveNumber : Integer;
- the number of sticks that the evaluation library extracts, on its turn
succeeding the move of your program.
- If your program wins a game you get the highest number of points for that
- If your program loses a game, you get 20% of the score of that test.
- If your program makes an incorrect move or it outruns the time limit, you
get 0 points.
- Attention: Only the MyMove procedure has to stop
your program, don't stop it after 2 seconds have elapsed.
- Because you don't have access to the NimLib library in order to test your program, you'll
have to build one alike on your computer.
- Do not send your own library for the evaluation; your program will be
evaluated with the our library.
Problem 3: Santa
Claus is Coming!... (20 points)
In the frozen land, the plans for Christmas' Eve are already made. Santa
knows what gifts he will give to the children. And between his short trips and
the number of the toys in his knap there's a very well-established
relationship. To help him, Santa's counsellors made a rectangular board with
100 lines and 100 columns, including 10,000 pawns. These
pawns have two sides, a black side and a red side. At first they are all with
the black side up (that is you can only see their black side). Before Santa's
departure, the counsellors turn the pawns so that, with a minimum number of
turnings, a certain number of pawns with the red side up appear. The number of
turnings represents the number of trips Santa makes in order to give as many
toys as the number of the red pawns on the board.
A pawn cannot be turned upside down unless the whole line (horizontal or
vertical) that includes that specific pawn is turned. We can turn any line we
want and the number of times we want.
Find the minimum number of (horizontal or vertical) line turnings so that
N red pawns appear on the board.
The file NOEL.IN has on each line an integer number:
, where N1, N2, ... ,Nk are the numbers of red pawns (the
number of toys).
The file NOEL.OUT has on each line a number:
, where P1, P2, ... ,Pk are the minimum number of turnings
so that N1, N2, ... ,Nk red pawns appear on the board; if there
is no solution you will write NU.
Example Input and
Execution Time: 1
second for every N on a 586/133 MHz.