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


Regulations

Schedule

Organising
Team

Cluj&Romania

Sponsors

Secretariat

Internet Contest

Links


___________
Web design: Vivi

[ The rules | Read the problems | Submit solutions | Results | Downloads ]

Day one problems are available here.

Day 2
[ 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.

Task
Write a program that implements a winning strategy, playing against a cyber-opponent.

Input
File name: STICKS.IN
Line 1: N
  • An integer, the number of stick rows (1 <= N <= 10).
    Line 2: S1 S2 ... SN
    N integers, separated by blanks, the number of sticks in each row (1 <= Si <= 10).
    Line 3: X
  • The only possible values for X are 0 and 1. If X=0, your program will make the first move; otherwise, the cyber-opponent will make the first move.

    Remark
    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:
  • Pascal: STICKS unit
  • C/C++: sticks.h header
    with the following routines:

    procedure putMove(nr,label1,label2:Integer); (Pascal)
    void putMove(int nr, int label1, int label2); (C/C++)
  • called to announce your program's move, that is, "eliminate from row nr the sticks labeled with numbers from label1 to label2 inclusively"

    procedure getMove(var nr,label1,label2:Integer); (Pascal)
    void getMove(int *nr, int *label1, int *label2); (C/C++)
  • called to obtain your opponent's move, in the same format as above;
  • C/C++ only: pass pointers to the variables in which you want to obtain the data

    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:
    •