News About Olympic History of OI OI books National team Olympic camps Photo gallery Links SIO MAIN

 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;

/* C/C++ */
int gramy_dalej();
int czy_podzielna_przez(int m);
```
("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