Polish version    English version  
  History of OI -> XI OI 2003/2004 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Stage III
Rules
For contestants
Helpful resources
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
XI Olympiad in Informatics 2003/2004

Zadanie: MIS

Pooh-Eeyore-sticks

III stage competition (national finals), day I  
Source file: mis.*
Memory limit: 32 MB

Bolek and Lolek are playing a game known under a familiar name of Pooh-Eeyore-sticks. To play Pooh-Eeyore-sticks only some poohsticks and just as indefinite number of eeyoresticks are necessary. All the sticks, both poohsticks and eeyoresticks, form together the game pool. It is also necessery to choose an arbitrary (positive) integer, traditionally called the PE-bound.
Bolek moves first and can thus remove a certain positive number of poohsticks or eeyoresticks from the game pool. He can also remove both poohsticks and eeyoresticks at once, provided that he picks the same positive number of poohsticks and eeyoresticks. Obviously, he may not pick more poohsticks nor eeyoresticks than there are in the pool. Moreover, neither the number of poohsticks nor eeyoresticks taken away may be greater than the PE-bound.
Subsequent moves are made in turns according to the same rules. The player who first empties the game pool is the winner. Help Bolek prevail against Lolek!

Task

Your task is to write a module that will play as Bolek after being compiled with another playing programme. You will be given a simplified playing programme, so that you will able to test your solution. Your module should contain the following two procedures (functions):

  • procedure poczatek (p, e, peb : LongInt) or
    void poczatek (int p, int e, int peb)
    This procedure (function), whose name means beginning in Polish, will be called only once, at the beginning of a game. You may use it to initialize variables or data structures used during the game. Parameters p, e and peb are the numbers of poohsticks and eeyoresticks in the game pool and the PE-bound respectively. The numbers of poohsticks and eeyoresticks in the pool shall be positive and shall not exceed 10^7. PE-bound shall also be positive and shall not exceed 10^6.

  • procedure ruch_bolka (p, e : LongInt; var bm, bp : LongInt) or
    void ruch_bolka (int m, int p, int *bp, int *be)
    This procedure (function) should determine next move of Bolek, as its name in Polish means exactly Bolek's move. The parameters passed, p and e, are the numbers of poohsticks and eeyoresticks respectively left in the game pool after last Lolek's move. The values of the parameters passed to the procedure (function) ruch_bolka in its first call are the same as the values passed to the procedure (function) poczatek. Before termination of the procedure call the values of variables bp, be (*bp i *be in C/C++) should be the numbers of poohsticks and eeyoresticks removed from the pool by Bolek.
Your module may not open any files nor use the standard input / output. Should your programme make an illegal operation, e.g. the procedure ruch_bolka returns an illegal (inconsistent with game rules) move, it shall be immediately terminated and you will receive 0 points for the test. If your programme loses the game, you will be given 0 points for the test as well. If it wins however, you will be given the maximum number of points allocated for the test. In each test your programme is going to receive, Bolek can win, no matter what moves Lolek makes.

Files (Pascal)

In the directory mis_pas you will find the following files:

  • mis.pas - a skeleton of the playing module, containing empty procedures poczatek i ruch_bolka. You should fill the code of these procedures.

  • graj.pas - a simplified game-generating programme. Moves of Lolek are made according to a very straightforward strategy, while moves of Bolek are determined by calling the procedures of the playing module mis.pas. You may use this programme to test your playing module.

Files (C / C++)

In the directory mis_c / mis_cpp you will find the following files:

  • mis.h - a file containing headers of the functions poczatek and ruch_bolka.

  • mis.c / mis.cpp - a skeleton of the playing module, containing empty definitions of the functions declared in the header file mis.h. You should fill the code of these functions.

  • graj.c / graj.cpp - a simplified game-generating programme. Moves of Lolek are made according to a very straightforward strategy, while moves of Bolek are determined by calling the procedures of the playing module mis.c / mis.cpp.
    You may use this programme to test your playing module.

Solution

As a result of your work you should present only one file: either mis.c, or mis.cpp or mis.pas, no more.

Example

This is a sample course of the game:
Call
Description
poczatek(7, 2, 3);there are 7 Poohsticks, 2 Eeyoresticks, and PE-bound=3
ruch_bolka (7, 2, bp, be); or
ruch_bolka (7, 2, &bp, &be);
first move
Bolek removes 1 poohstick and 1 eeyorestick from the pool; 6 poohsticks and 1 eeyorestick remain
ruch_bolka (3, 1, bp, be); or
ruch_bolka (3, 1, &bp, &be);
Lolek removed 3 poohsticks from the pool; 3 poohsticks and 1 eeyorestick remain
Bolek picks 1 poohstick; 2 poohsticks and 1 eeyorestick remain
ruch_bolka (1, 0, bp, be); or
ruch_bolka (1, 0, &bp, &be);
Lolek picks 1 poohstick and 1 eeyorestick; 1 poohstick and no eeyorestick remain
Bolek removes the final poohstick from the pool and thus wins



Print friendly version