Polish version    English version  
  Historia OI -> III OI 1995/1996 -> 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
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
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
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
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