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.
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.