Polish version    English version  
  Historia OI -> XI OI 2003/2004 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodnikow
Przydatne zasoby
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
XI Olimpiada Informatyczna 2003/2004

Zadanie: MIS

Misie-Patysie

Zawody III stopnia, dzien I  
Plik źródłowy: mis.*
Limit pamięci: 32 MB

Alternatywne formaty: PostScript PDF

Bolek i Lolek bawią się w grę o swojsko brzmiącej nazwie misie-patysie. Aby zagrać w misie-patysie wystarczy mieć trochę misiów oraz równie nieokreśloną liczbę patysiów, które tworzą razem pulę gry. Trzeba też wybrać dowolną liczbę naturalną, którą zgodnie z tradycją nazywa się MP-ograniczeniem.
Pierwszy ruch należy do Bolka, który może zabrać z puli pewną dodatnią liczbę misiów albo patysiów. Może też jednocześnie wziąć i misie, i patysie, ale tylko jeśli jednych i drugich bierze tyle samo i więcej od zera. Oczywiście nie można zabrać więcej misiów niż jest ich w puli - podobnie z patysiami. Co więcej ani jednych, ani drugich nie można wziąć więcej niż wynosi MP-ograniczenie.
Kolejne ruchy wykonywane są na przemian według tych samych reguł. Wygrywa ten z graczy, po którego ruchu pula pozostanie pusta. Twoim celem jest pomóc Bolkowi w odniesieniu zwycięstwa nad Lolkiem.

Zadanie

Zadanie polega na napisaniu modułu, który po skompilowaniu z odpowiednim programem grającym będzie grał jako Bolek. Na potrzeby tego zadania otrzymasz uproszczony program grający, który pozwoli Ci przetestować rozwiązanie. Twój moduł powinien zawierać następujące dwie procedury (funkcje):

  • procedure poczatek (m, p, mpo : LongInt) lub
    void poczatek (int m, int p, int mpo)
    Ta procedura (funkcja) będzie wywołana tylko raz, na początku rozgrywki. Możesz jej użyć by zainicjalizować zmienne lub struktury danych potrzebne podczas rozgrywki. Parametry m, p oraz mpo zawierają odpowiednio liczbę misiów i patysiów w puli gry oraz MP-ograniczenie. Liczby Misiów i Patysiów w puli będą zawsze dodatnie i niewiększe niż 10^7. MP-ograniczenie będzie dodatnie i niewiększe niż 10^6.

  • procedure ruch_bolka (m, p : LongInt; var bm, bp : LongInt) lub
    void ruch_bolka (int m, int p, int *bm, int *bp)
    Ta procedura (funkcja) powinna wyznaczyć kolejny ruch Bolka. Przekazane jej parametry m i p zawierają odpowiednio liczbę misiów i patysiów w puli gry pozostałych po ostatnim ruchu Lolka. Wartości parametrów przekazanych przy pierwszym wywołaniu procedury (funkcji) ruch_bolka są takie same jak odpowiednie wartości parametrów przekazanych do procedury (funkcji) poczatek. Przed zakończeniem wykonania procedury zmienne bm, bp (*bm i *bp w języku C/C++) powinny zawierać, odpowiednio, liczbę misiów i patysiów wziętych przez Bolka z puli.
Twój moduł nie może otwierać żadnych plików ani korzystać ze standardowego wejścia / wyjścia. Jeśli twój program wykona niedozwoloną operację, w tym np. procedura ruch_bolka zwróci ruch niezgodny z zasadami gry, jego działanie zostanie przerwane. W tym przypadku dostaniesz 0 punktów za dany test.
Jeśli Twój program przegra rozgrywkę, dostaniesz 0 punktów za test. Jeśli wygra, dostaniesz maksymalną przewidzianą za dany test liczbę punktów. Dla każdego testu, na którym zostanie uruchomiony Twój program, Bolek może wygrać, niezależnie od ruchów Lolka.

Pliki (Pascal)

W katalogu mis_pas znajdziesz następujące pliki:

  • mis.pas - szkielet modułu grającego zawierający puste procedury poczatek i ruch_bolka. Powinieneś napisać kod tych procedur.

  • graj.pas - uproszczony program generujący rozgrywkę. Ruchy Lolka wykonywane są zgodnie z bardzo prostą strategią, natomiast ruchy Bolka wyznaczane są przez wywoływanie procedur modułu grającego mis.pas. Możesz użyć tego programu do testowania swojego modułu grającego.

Pliki (C / C++)

W katalogu mis_c / mis_cpp znajdziesz następujące pliki:

  • mis.h - plik zawierający nagłówki funkcji poczatek i ruch_bolka.

  • mis.c / mis.cpp - szkielet modułu grającego zawierający puste definicje funkcji zadeklarowanych w pliku nagłówkowym mis.h. Powinieneś napisać kod tych funkcji.

  • graj.c / graj.cpp - uproszczony program generujący rozgrywkę. Ruchy Lolka wykonywane są zgodnie z bardzo prostą strategią, natomiast ruchy Bolka wyznaczane są przez wywoływanie procedur modułu grającego mis.c / mis.cpp.
    Możesz użyć tego programu do testowania swojego modułu grającego.

Rozwiązanie

Wynikiem Twojej pracy powinien być tylko jeden plik mis.c, mis.cpp lub mis.pas ale nie kilka równocześnie.

Przykład

Rozgrywka może przebiegać następująco:
Wywołanie
Opis
poczatek(7, 2, 3);jest 7 Misiów, 2 Patysie, a MP-ograniczenie=3
ruch_bolka (7, 2, bm, bp); lub
ruch_bolka (7, 2, &bm, &bp);
pierwszy ruch
Bolek bierze z puli 1 misia i 1 patysia; zostaje 6 misiów i 1 patyś
ruch_bolka (3, 1, bm, bp); lub
ruch_bolka (3, 1, &bm, &bp);
Lolek wziął z puli 3 misie; zostały 3 misie i 1 patyś
Bolek bierze z puli 1 misia; zostają 2 misie i 1 patyś
ruch_bolka (1, 0, bm, bp); lub
ruch_bolka (1, 0, &bm, &bp);
Lolek wziął z puli 1 misia i 1 patysia; został 1 miś i 0 patysiów
Bolek bierze z puli 1 misia i wygrywa



Wersja do druku