Polish version    English version  
  O olimpiadzie -> Zadania -> VII OI 1999/2000


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 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
VII Olimpiada Informatyczna 1999/2000

Zadanie: JAJ
Autor: Marcin Mucha
Jajka

Zawody III stopnia, dzień pierwszy 12 kwietnia 2000
Plik źródłowy: JAJ.??? (np. pas, c, cpp)
Plik wykonywalny: JAJ.exe
Plik wejściowy: JAJ.in
Plik wyjściowy: JAJ.out

Wiadomo, że jajko zrzucone z wystarczająco dużej wysokości brzydko się rozbija. Dawniej wystarczyła wysokość jednego piętra, ale genetycznie podrasowane kury znoszą jajka nie tłukące się nawet po zrzuceniu z wysokości 100000000 pięter. Badania nad wytrzymałością jajek prowadzi się wykorzystując drapacze chmur. Opracowano specjalną skalę wytrzymałości jajek: jajko ma wytrzymałość k pięter, jeśli zrzucone z k-tego piętra nie rozbija się, ale zrzucone z k+1-ego już tak. W przypadku gdy drapacz chmur, którym dysponujemy, ma n pięter przyjmujemy, że jajko rozbija się, gdy zrzucimy je z n+1-ego piętra. Przyjmujemy też, że każde jajko zrzucone z piętra o numerze 0 nie rozbija się.

Kierownik laboratorium postanowił wprowadzić oszczędności w procesie badawczym. Ograniczył on liczbę jajek, które wolno rozbić w trakcie eksperymentu mającego na celu ustalenie wytrzymałości jajek danego gatunku. Dodatkowo należy zminimalizować liczbę zrzutów jajek. Oznacza to, że mając do dyspozycji pewną liczbę jajek danego gatunku i drapacz chmur należy w jak najmniejszej liczbie prób stwierdzić, jaka jest wytrzymałość jajek danego gatunku.

Zadanie

Twoim zadaniem jest napisanie modułu zawierającego trzy procedury (funkcje w przypadku języka C/C++):

  • nowy_eksperyment - ta procedura będzie wywoływana na początku każdego nowego eksperymentu (może być ich więcej niż jeden);
  • daj_pytanie - ta procedura służy do zadawania pytania, czy jajko wytrzyma zrzucenie z określonego piętra, czy też rozbije się; w tym celu należy w opisanej dalej zmiennej globalnej pietro umieścić numer piętra, z którego ma być zrzucone jajko,
  • analizuj_odpowiedz - ta procedura powinna odczytać wartość zmiennej globalnej {\tt odpo\-wiedz}, która zawiera odpowiedź na ostatnio zadane pytanie (opis tej zmiennej znajduje się w kolejnym paragrafie) i dokonać analizy tej odpowiedzi - jeśli w wyniku tej analizy zostanie określona wytrzymałość jajka, to procedura ta powinna ten fakt zasygnalizować poprzez nadanie odpowiednich wartości zmiennym globalnym x oraz wiem (szczegóły znajdują się w kolejnym paragrafie).

Program nadzorujący przebieg eksperymentów wywoła napisaną przez Ciebie procedurę nowy_eksperyment na początku każdego nowego eksperymentu, po czym cyklicznie będzie wykonywał następujące czynności:

  • wywołanie procedury daj_pytanie,
  • odpowiadanie na pytanie,
  • wywołanie procedury analizuj_odpowiedz,

aż do momentu, gdy Twój program stwierdzi, że zna wytrzymałość jajek gatunku używanego w danym eksperymencie (tzn. procedura analizuj_odpowiedz umieści odpowiednią wartość w zmiennej globalnej tt wiem).

Uwaga: Nie zakładaj, że program nadzorujący przebieg eksperymentów faktycznie ustala pewną wytrzymałość jajka przed rozpoczęciem danego eksperymentu. Może on dobierać ją w trakcie trwania eksperymentu w taki sposób, aby pasowała do wszystkich wcześniej udzielonych odpowiedzi oraz aby zmusić Twój program do zadania jak największej liczby pytań. Tak więc, powinieneś dążyć do tego, aby liczba pytań, jakie Twój program będzie musiał zadać w najgorszym przypadku, była jak najmniejsza.

Komunikacja

Komunikacja pomiędzy napisanym przez Ciebie modułem a programem nadzorującym przebieg eksperymentów odbywa się poprzez zmienne globalne. Liczba pięter drapacza zapisana będzie w zmiennej globalnej wysokosc typu Longint (w przypadku języka C/C++ jest to typ long int). Będzie to dodatnia liczba całkowita, nie większa niż 100000000. Maksymalna liczba jajek, które można stłuc w trakcie trwania eksperymentu zapisana będzie w zmiennej globalnej jajka typu Integer (w przypadku języka C/C++ jest to typ int). Będzie to dodatnia liczba całkowita, nie większa niż 1000. Zadanie pytania, czy jajko wytrzyma zrzucenie z k-tego piętra, w procedurze daj_pytanie polega na przypisaniu zmiennej globalnej pietro typu Longint (w przypadku języka C/C++ jest to typ long int) liczby k. Odpowiedź na zadane pytanie jest umieszczana w zmiennej globalnej odpowiedz typu Boolean (w przypadku języka C/C++ jest to typ int). Twierdzącej odpowiedzi na zadane pytanie (tzn. jajko wytrzyma) odpowiada wartość TAK, a przeczącej (tzn. jajko rozbije się) odpowiada NIE, gdzie TAK i NIE są stałymi o wartościach odpowiednio true i false (w przypadku języka C/C++ są to makra o wartościach odpowiednio 1 i 0). W przypadku znalezienia wytrzymałości jajka Twój program powinien w procedurze analizuj_odpowiedz zapisać do zmiennej globalnej wiem typu Boolean (w przypadku języka C/C++ jest to typ int) TAK oraz w zmiennej globalnej x typu Longint (w przypadku języka C/C++ jest to typ long int) znalezioną wytrzymałość jajka.

Katalogi i pliki

Programujący w Pascalu powinni przygotowywać swoje rozwiązanie w katalogu JAJPAS, natomiast programujący w C i C++ w katalogu JAJC. W katalogu JAJPAS (odpowiednio JAJC) znajdziesz następujące pliki:

  • JAJmod.pas (odpowiednio JAJmod.h i JAJmod.c) - moduł zawierający definicje stałych TAK i NIE oraz deklaracje zmiennych globalnych,
  • JAJ.pas - szkielet modułu znajdującego wytrzymałość jajka; powinieneś uzupełnić ten plik definicjami funkcji nowy_eksperyment, daj_pytanie i analizuj_odpowiedz (dla piszących w C lub C++ nagłówki powyższych funkcji znajdują się w pliku JAJ.h, musisz napisać plik JAJ.C lub JAJ.cpp z definicjami tych funkcji),
  • test.pas (odpowiednio test.c) - przykładowy program nadzorujący przebieg eksperymentów i korzystający z Twojego modułu.

Wyjście

Wynikiem Twojej pracy powinien być zapisany na dyskietce tylko jeden plik: JAJ.pas, JAJ.C lub JAJ.cpp.




Wersja do druku