III Olimpiada Informatyczna 1995/96
|
Zadanie: MON
|
Autor: Piotr Chrząstowski-Wachtel
|
Zawody II stopnia |
Plik źródłowy: | MON.??? (np. pas, c, cpp) |
Plik wykonywalny: | MON.exe |
Plik wejściowy: | MON.in |
Plik wyjściowy: | MON.out |
Mamy pięć monet A, B, C, D, E, których ciężary są parami różne. Dysponując bardzo czułą wagą szalkową, pozwalającą porównać ze sobą ciężary dwóch monet, uszereguj je od najlżejszej do najcięższej. Waga jest delikatnym i kosztownym urządzeniem. Pierwszych siedem porównań możemy wykonać za darmo. Ósme kosztuje 1 złoty, a każde następne porównanie jest 125 razy droższe od poprzedniego. Decyzję o tym, które porównanie wykonać w danej chwili, możemy podejmować w zależności od wyników poprzednich pomiarów. Zaprojektuj algorytm sortujący monety, tak aby koszt ważenia był jak najmniejszy.
Kod źródłowy programu jest zapisany w następujących plikach:
UMONETA.PAS - definicja typu Tmoneta,
UWAGA.PAS - funkcja lzejsza i procedura wynik,
USORT.PAS - miejsce na Twoje rozwiązanie,
MONETY.PAS - główna część programu
Procedura sortujMonety powinna korzystać z typu TMoneta, zdefiniowanego w pliku UMONETA.PAS:
unit UMoneta; interface type TMoneta = (A, B, C, D, E); {Z pozostałych deklaracji, zawartych w tym pliku, korzystać nie wolno.} implementation {...}Do porównywania monet oraz podawania rozwiązania służą funkcja lzejsza i procedura wynik zadeklarowane w pliku UWAGA.PAS:
unit UWaga; interface uses UMoneta; function lzejsza(m1,m2:TMoneta):boolean; {Przyjmuje wartość true jeśli moneta m1 jest lżejsza od monety m2, w przeciwnym przypadku przyjmuje wartość false.} procedure wynik(m1,m2,m3,m4,m5:TMoneta); {Gdy monety zostaną już uszeregowane od najlżejszej do najcięższej, należy wywołać procedurę wynik . Parametry m1, m2, m3, m4, m5 oznaczają monety uszeregowane od najlżejszej do najcięższej. Zwróć uwagę, że ta procedura musi być wywołana dokładnie jeden raz w trakcie działania sortujMonety.} implementation {...}Rozwiązanie zapisz w pliku USORT.PAS:
unit USort; interface uses UMoneta,UWaga; procedure sortujMonety; implementation {Poniżej jest miejsce na kod Twojego rozwiązania. Typy, zmienne, funkcje oraz procedury, które zadeklarujesz muszą być lokalne dla tego modułu.} procedure sortujMonety; begin end;Spośród funkcji, procedur, typów oraz zmiennych zadeklarowanych w innych plikach wolno Ci korzystać tylko z funkcji lzejsza, procedury wynik i typu Tmoneta. Nie wolno zmieniać czegokolwiek poza implementacją modułu USORT.PAS. Ocenie podlega tylko plik USORT.PAS, który zostanie skompilowany z innym programem sprawdzającym poprawność rozwiązania, dlatego interfejs modułu musi pozostać nie zmieniony.
Kod źródłowy programu jest zapisany w następujących plikach:
UMONETA.H, UMONETA.C - definicja typu: Tmoneta,
UWAGA.H, UWAGA.C - funkcja lzejsza i procedura wynik,
USORT.H, USORT.C - miejsce na Twoje rozwiązanie,
MONETY.C - główna część programu
Procedura sortujMonety powinna korzystać z typu TMoneta, zdefiniowanego w pliku UMONETA.H:
typedef enum {A, B, C, D, E} TMoneta; /* Z pozostałych deklaracji, zawartych w tym pliku, korzystać nie wolno. */Do porównywania monet oraz podawania rozwiązania służą funkcja lzejsza i procedura wynik zadeklarowane w pliku UWAGA.H:
extern int lzejsza (TMoneta m1, TMoneta m2); /* Przyjmuje wartość 1 (prawda) jeśli moneta m1 jest lżejsza od monety m2, w przeciwnym przypadku przyjmuje wartość 0 (fałsz). */ extern void wynik (TMoneta m1, TMoneta m2, TMoneta m3, TMoneta m4, TMoneta m5); /* Gdy monety zostaną już uszeregowane od najlżejszej do najcięższej, należy wywołać procedurę wynik . Parametry m1, m2, m3, m4, m5 oznaczają monety uszeregowane od najlżejszej do najcięższej. Zwróć uwagę, że ta procedura musi być wywołana dokładnie jeden raz w trakcie działania sortujMonety. */Rozwiązanie zapisz w pliku USORT.C:
#include "usort.h" /* Tu mogą być umieszczone zmienne i funkcje pomocnicze */ void sortujMonety() { /* To jest miejsce na twoje rozwiązanie */ /* Można wywołać tylko funkcje lzejsza(...) i wynik(...) oraz własne funkcje z tego modułu. */ }Spośród funkcji, procedur, typów oraz zmiennych zadeklarowanych w innych plikach wolno Ci korzystać tylko z funkcji lzejsza, procedury wynik i typu Tmoneta. Nie wolno również zmieniać czegokolwiek poza implementacją modułu USORT.C. Ocenie podlega tylko plik USORT.C, który zostanie skompilowany z innym programem sprawdzającym poprawność rozwiązania, dlatego interfejs modułu musi pozostać nie zmieniony.