Polish version    English version  
  History of OI -> X OI 2002/2003 -> 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
X OI 2002/2003
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Rules
For contestants
Helpful resources
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
X Olympiad in Informatics 2002/2003

Problem: Divisor Game
Author: Krzysztof Onak

Maya the Bee and Willy, from time to time, play the following game. Maya chooses a natural number k in the range from 1 to some fixed natural number n. Next Willy ask questions of the form "Does m divide k?", where m is a positive integer. After each such a question Maya answers TAK ("yes" in Polish) or NIE ("no"). Willy intends to know what number Maya bears in mind by asking as few questions as possible.

Task

Write a program which, after being compiled together with an appropriate playing module, will play as Willy. To enable you to test your solution by yourself you will be provided with a simplified module playing as Maya.

Description of Playing Module Interface in Pascal / C

Your program should communicate with "the rest of the world" exclusively by means of calls to the functions and procedures of the playing module (maja.pas in Pascal, maja.h in C/C++; "Maja" = "Maya" in Polish). It means that it is not permitted to open any files nor to use the standard input/output streams.

        (* Pascal *)
        function gramy_dalej: longint; 
        function czy_podzielna_przez(m : longint) : boolean;
        procedure zgaduj(k : longint); 

        /* C/C++ */
        int gramy_dalej();
        int czy_podzielna_przez(int m);
        void zgaduj(int k); 
("gramy_dalej" = "play_again", "czy_podzielna_przez" = "is_divisible_by", "zgaduj" = "guess")

Your program should be able to play many games with Maya on a single run. To initialise a game one should use the function gramy_dalej() which returns n, the upper bound on the number that Maya has in mind. The number n satisfies the limitations 1 <= n <= 1000000. If there are no more games to play the function returns 0.

Next, your program may ask questions calling the function czy_podzielna_przez(m). The parameter m must satisfy 1 <= m <= n.

To end the game one should try and guess Maya's secret number calling the procedure zgaduj(k). The parameter k should satisfy 1 <= k <= n. Only one attempt is allowed. After attempting to guess Maya's number one may initialise next game.




Print friendly version