Olimpiada Informatyczna

O olimpiadzie -> Zadania

SIO

MAIN

III Olimpiada Informatyczna 1995/96

Zadanie: MON

Autor: Piotr Chrząstowski-Wachtel

Pięć monet

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.

Zadanie

Rozwiązanie możesz zapisać w Pascalu lub w języku C.

Pascal

Tutaj jest program, który pozwoli Ci uruchomić Twoje rozwiązanie. Uzupełnij treść procedury sortujMonety z pliku USORT.PAS. Ta procedura powinna, korzystając z funkcji lzejsza, uszeregować monety według ich ciężaru od najlżejszej do najcięższej, a następnie, wywołując procedurę wynik, przekazać znalezioną kolejność. Ocena poprawności rozwiązania dla pewnych dowolnie wybranych ciężarów monet zostanie dokonana na podstawie tego wywołania procedury wynik.

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.

Język C

Tutaj jest program, który pozwoli Ci uruchomić Twoje rozwiązanie. Uzupełnij treść procedury sortujMonety z pliku USORT.C. Ta procedura powinna, korzystając z funkcji lzejsza, uszeregować monety według ich ciężaru od najlżejszej do najcięższej, a następnie, wywołując procedurę wynik, przekazać znalezioną kolejność. Ocena poprawności rozwiązania dla pewnych dowolnie wybranych ciężarów monet zostanie dokonana na podstawie tego wywołania procedury wynik.

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.

Wersja do druku