Krzysztof Diks, Marcin Kubica

Tłumaczenie

Median strength

Zadanie

W nowym eksperymencie kosmicznym wykorzystanych jest N obiektów ponumerowanych od 1 do N. Wiadomo, że N jest liczbą nieparzystą. Każdy obiekt charakteryzuje się inną, ale nieznaną wagą, wyrażaną liczbą naturalną. Dla każdej wag Y mamy . Obiekt o środkowej wadze to taki obiekt, dla którego mamy tyle samo obiektów od niego cięższych, co lżejszych. Napisz program, który wyznaczy obiekt o środkowej wadze. Niestety jedyny sposób na porównywanie wagi obiektów, to użycie narzędzia, które dla zadanych trzech różnych obiektów wyznacza, który spośród tych trzech obiektów ma środkową wagę.

Biblioteka

Dana jest biblioteka device udostępniająca trzy operacjie:

• GetN, bez argumentów, którą należy wywołać raz na początku, dająca w wyniku wartość N,

• Med3, mająca 3 argumenty będące numerami trzech różnych obiektów, dająca w wyniku numer obiektu o środkowej wadze,

• Answer, o jednym argumencie będącym numerem obiektu; wywołując te funkcje przekazuje się numer obiektu o środkowej wadze, funkcja ta kończy (w poprawny sposób) wykonanie programu.

Biblioteka device tworzy dwa pliki tekstowe: MEDIAN.OUT i MEDIAN.LOG. Pierwszy wiersz pliku MEDIAN.OUT zawiera jedną liczbę całkowitą - numer obiektu, który był argumentem Answer. Drugi wiersz jedną liczbę całkowitą - liczbę wywołań funkcji Med3 wykonywanych przez Twój program. Komunikacja pomiędzy Twoim programem i biblioteką jest opisana w pliku MEDIAN.LOG.

Instrukcja dla programujących w Pascalu: Wstaw do kodu źródłowego programu następujące polecenie dołączające bibliotekę:
uses device;

Instrukcja dla programujących w C/C++: W kodzie źródłowym Twojego programu użyj polecenia:
\#include
stwórz projekt MEDIAN.PRJ i dodaj do niego pliki MEDIAN.C ( MEDIAN.CPP) oraz DEVICE.OBJ.

Testowanie

Możesz przetestować swój program tworząc plik tekstowy DEVICE.IN. Plik ten musi zawierać dwa wiersze. W pierwszym wierszu musi być zapisana jedna liczba całkowita: liczba obiektów N. Drugi wiersz musi zawierać liczby całkowite od 1 do N podane w pewnej kolejności - i-ta liczba reprezentuje wagę obiektu nr i.

Przykład

DEVICE.IN:

5
2 5 4 3 1

Powyższy plik DEVICE.IN opisuje 5 danych obiektów o następujących wagach:

Oto poprawna sekwencja 5-ciu wywołań biblioteki:

1. GetN (w Pascalu) lub GetN() (W C/C++), daje w wwyniku 5,
2. Med3(1,2,3), daje w wyniki 3,
3. Med3(3,4,1), daje w wyniki 4,
4. Med3(4,2,5), daje w wyniki 4,
5. Answer(4)

Ograniczenia

• Liczba obiektów N jest nieparzysta oraz .

• Numery obiektów i spełniają .

• Wagi obiektów Y spełniają . Wszystkie wagi są różne,

• Biblioteka dla Pascala znajduje się w pliku device.tpu.

• Deklaracje funkcji i procedur bibliotecznych dla Pascala:

  
  function GetN : integer;
  function Med3 (x, y, z : integer) : integer;
  procedure Answer (m : integer);
  

• Nazwy plików bibliotecznych dla C/C++: device.h, device.obj (używaj modelu pomięci large).

• Deklaracje funkcji bibliotecznych C/C++:

  
  int GetN (void);
  int Med3 (int x, int y, int z);
  void Answer (int m);
  

• W trakcie każdego wykonania Twój program może wywoływać funkcję Med3 co najwyżej 7777 razy.

• Twój program nie może odwoływać się (czytać/pisać) do żadnych plikach.