Alternatywne formaty: PostScript | PDF

Pszczółka Maja i Gucio czasami grają w następującą grę. Maja wymyśla liczbę naturalną k z przedziału od 1 do pewnej ustalonej liczby naturalnej n. Następnie Gucio zadaje pytania postaci "Czy k jest podzielne przez m?", gdzie m to dodatnia liczba całkowita. Maja po każdym takim pytaniu odpowiada TAK lub NIE. Gucio chce w jak najmniejszej liczbie pytań dowiedzieć się, jaką liczbę Maja miała na myśli.

Zadanie

Napisz program, który po skompilowaniu razem z odpowiednim modułem grającym będzie grał jako Gucio. Na potrzeby tego zadania otrzymasz uproszczony moduł grający, który pozwoli Ci przetestować swoje rozwiązanie.

Opis interfejsu modułu grającego w Pascalu / C

Twój program powinien komunikować się ze "światem zewnętrznym" tylko i wyłącznie poprzez wywołania funkcji i procedur modułu grającego (maja.pas w Pascalu, maja.h w C/C++). Oznacza to, że nie wolno otwierać żadnych plików ani też korzystać ze standardowego wejścia/wyjścia.

        (* 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); 

Twój program powinien być zdolny rozegrać z Mają wiele partii podczas jednego uruchomienia. Aby zainicjować rozgrywkę, należy użyć funkcji gramy_dalej(), której wynikiem jest n - górne ograniczenie na wymyśloną przez Maję liczbę. Liczba n spełnia ograniczenia 1 <= n <= 1000000. Jeśli nie ma już więcej rozgrywek do rozegrania, wynikiem funkcji jest 0.

Następnie twój program może zadawać pytania za pomocą funkcją czy_podzielna_przez(m). Parametr m musi spełniać 1 <= m <= n.

Aby zakończyć rozgrywkę trzeba spróbować zgadnąć sekretną liczbę Mai za pomocą procedury zgaduj(k). Parametr k powinien spełniać 1 <= k <= n. Można próbować tylko raz; po próbie odgadnięcia liczby Mai można zainicjować następną rozgrywkę.