Polish version    English version  

 About Olympic
 History of OI
 OI books
 National team
 Olympic camps
 Photo gallery
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.


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