<Wyślij rozwiązanie> [0/100]

Architekci

Limit pamięci: 32 MB

Król Bajtazar postanowił wybudować sobie nowy pałac. Ogłosił więc konkurs na najlepszy projekt architektoniczny pałacu. Chcąc zmotywować architektów do spiesznej pracy, ogłosił też, że projekty będzie rozpatrywał w takiej kolejności, w jakiej będą nadsyłane.

Z tym zleceniem wiąże się ogromny prestiż, dlatego też architekci z całego świata nadsyłają swoje propozycje do królewskiej kancelarii. Projektów nadchodzi bardzo dużo, a Bajtazar nie ma czasu ich wszystkich przeglądać. Zrezygnował zatem z samodzielnego wykonywania tej czynności i poprosił swojego kanclerza o to, by wstępnie przejrzał nadchodzące projekty zgodnie z następującymi zasadami:

• kanclerz ma wybrać projektów, odrzucając resztę od razu - Bajtazar wie, że więcej niż projektów i tak nie będzie w stanie przejrzeć;
• projekty mają zostać przedstawione Bajtazarowi w takiej kolejności, w jakiej zostały nadesłane - w takiej też kolejności Bajtazar będzie je przeglądał, zgodnie z tym co ogłosił;
• spośród wszystkich ciągów projektów spełniających powyższe warunki, kanclerz ma wybrać ciąg najlepszy, zgodnie z poniższą definicją.
  Powiemy, że ciąg projektów jest lepszy od ciągu , jeśli dla pewnego pierwszych projektów w obu ciągach jest równie dobrych, zaś -ty projekt w ciągu jest lepszy od -tego projektu w ciągu (czyli dla i ).

Projekty cały czas nadchodzą i nie wiadomo, do kiedy Bajtazar rozkaże je przyjmować. Kanclerz nie chce zostawiać wyboru projektów na ostatni moment, jednak bardzo boi się popełnić błąd i narazić na gniew króla. Dlatego poprosił Cię o pomoc.

Napisz program, który:

• pobierze za pomocą dostarczonej biblioteki liczbę oraz ciąg liczb reprezentujących jakość kolejnych projektów,
• wyznaczy najlepszy ciąg projektów, zgodnie z podanymi zasadami,
• zwróci jakości wybranych projektów za pomocą biblioteki.

Opis użycia biblioteki

Aby użyć biblioteki, należy wpisać w swoim programie:

• C/C++: #include "carclib.h"
• Pascal: uses parclib;

Biblioteka udostępnia trzy procedury, funkcje lub metody statyczne:

• inicjuj - zwraca liczbę całkowitą (), określającą, jak wiele projektów ma zawierać ciąg wynikowy. Powinna być użyta dokładnie raz, na samym początku działania programu.
  • C/C++: int inicjuj();
  • Pascal: function inicjuj(): longint;

• wczytaj - -te wywołanie zwraca liczbę całkowitą () oznaczającą jakość -tego projektu (im większa liczba, tym lepszy projekt), albo , co oznacza, że nie ma już więcej projektów. Liczba projektów nie jest znana przed wczytaniem danych, jednak możesz założyć, że wszystkich projektów jest przynajmniej , a co najwyżej . Funkcja ta powinna być wywoływana do momentu, aż skończą się projekty, i ani razu więcej.
  • C/C++: int wczytaj();
  • Pascal: function wczytaj(): longint;

• wypisz - za pomocą tej procedury/funkcji wypisujesz jakości kolejnych projektów, które kanclerz przedstawi królowi. Powinna być ona użyta dokładnie razy; w -tym wywołaniu należy podać jakość -tego w kolejności projektu. -te wywołanie tej procedury/funkcji zakończy działanie Twojego programu.
  • C/C++: void wypisz(int jakoscProjektu);
  • Pascal: procedure wypisz(jakoscProjektu: longint);

Twój program nie może otwierać żadnych plików ani używać standardowego wejścia i wyjścia. Rozwiązanie będzie kompilowane wraz z biblioteką za pomocą następujących poleceń:

• C: gcc -O2 -static carclib.c arc.c -lm
• C++: g++ -O2 -static carclib.c arc.cpp -lm
• Pascal: ppc386 -O2 -XS -Xt arc.pas, a plik biblioteki parclib będzie znajdował się w tym samym katalogu.

W tym archiwum możesz znaleźć przykładowe pliki bibliotek i przykładowe rozwiązania ilustrujące sposób ich użycia. Przykładowa biblioteka wczytuje scenariusz testowy ze standardowego wejścia w następującym formacie:

• Pierwszy wiersz wejścia zawiera jedną dodatnią liczbę całkowitą .
• Kolejne wiersze wejścia zawierają po jednej dodatniej liczbie całkowitej; -szy wiersz zawiera liczbę , oznaczającą jakość -tego zgłoszonego projektu.
• Ostatni wiersz wejścia zawiera liczbę , oznaczającą koniec listy projektów.

Przykładowa biblioteka wypisuje na standardowe wyjście wierszy - jakości projektów zgłoszone przez program.

Przykładowy przebieg programu

C/C++	Pascal	Zwracane wartości i wyjaśnienia
k = inicjuj();	k := inicjuj();	Od tego momentu .
wczytaj(); wczytaj(); wczytaj(); wczytaj(); wczytaj(); wczytaj(); wczytaj();	wczytaj(); wczytaj(); wczytaj(); wczytaj(); wczytaj(); wczytaj(); wczytaj();	Wczytywanie jakości kolejnych projektów. 12 5 8 3 15 8 0 - oznacza koniec ciągu projektów
wypisz(12); wypisz(15); wypisz(8);	wypisz(12); wypisz(15); wypisz(8);	Wypisujemy rozwiązanie, czyli 3-elementowy ciąg: 12 15 8

Autor zadania: Jakub Onufry Wojtaszczyk.

<Wyślij rozwiązanie> [0/100]