Polish version    English version  
 


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
X Olimpiada Informatyczna 2002/2003

Zadanie: gra
Autor: Krzysztof Onak
Gra w dzielniki

Zawody III stopnia, dzień próbny  
Plik źródłowy: gra.xxx (xxx=pas,c,cpp)

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




Wersja do druku