X Olimpiada Informatyczna 2002/2003
|
Zadanie: gra
|
Autor: Krzysztof Onak
|
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.
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.
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ę.