|Home||I n t e r n e t C o n t e s t||i n t e r n e t
c o n t e s t
|C E O I
2 0 0 0
Day one problems are available here.
[ Problem 4 | Problem 5 | Problem 6 ]
Problem 5 : Sticks
Consider the following game between two players:
N rows of sticks lie on a table with Si sticks in row i (1 <= i <= N). The sticks in each row i are labeled sequentially from 1 to Si. The players alternately make a move. Each move consists of eliminating one, two or three sticks from the same row. These sticks must be labeled sequentially, i.e., they must be contiguous in the row.
For example, if there is a row with 10 sticks and the first player eliminates the sticks labeled 4, 5, 6, only sticks 1, 2, 3, 7, 8, 9, and 10 remain. The second player, on his turn, has the possibility to eliminate the sticks 1, 2, 3 but not 3, 7, 8 since they are not numbered sequentially (of course, there are other valid moves).
The winner is the player performing the last move, i.e., eliminating the last stick(s) from the table.
Write a program that implements a winning strategy, playing against a cyber-opponent.
File name: STICKS.IN
Line 1: N
Line 2: S1 S2 ... SN
N integers, separated by blanks, the number of sticks in each row (1 <= Si <= 10).
Line 3: X
The test input data guarantees that a winning strategy exists for your program.
Your program will play against a machine. The interaction between your program and its opponent will be made possible by the following software interface:
with the following routines:
procedure putMove(nr,label1,label2:Integer); (Pascal)
void putMove(int nr, int label1, int label2); (C/C++)
procedure getMove(var nr,label1,label2:Integer); (Pascal)
void getMove(int *nr, int *label1, int *label2); (C/C++)
Your program should alternately call these two routines until there are no more sticks on the table. Our module will terminate the game if your program makes an invalid move (of course you will get no points in this case).
Example possible call succession in PASCAL STICKS.IN getMove(nr, k1, k2); -> nr=2, k1=2, k2=2 2 putMove(1, 1, 1); 1 3 getMove(nr, k1, k2); -> nr=2, k1=1, k2=1 1 putMove(2, 3, 3); **** your program wins ****
You can download from here a demo version of the Unit, but you must keep in mind that this is only a demo version, and it will not play at it's best: