[naglowek]

wersja PS     wersja PS.ZIP
Wstęp
Sprawozdanie z przebiegu VII OI
Regulamin
Zasady organizacji zawodów
Informacja o IOI'99
Etap I
Etap II
Etap III
 
Lollobrygida
Jajka
Po-łamana
Agenci
Powtórzenia
Promocja
IOI
Literatura

Spis treści
O wersji online

Niebieskie książeczki
 
Olimpiada Informatyczna
Kącik zadań
Archiwum zadań
CEOI'97
 
   Tomasz Waleń (treść, opracowanie)    Marcin Sawicki (program wzorcowy)

Promocja

Wielka bajtocka sieć supermarketów poprosiła Cię o napisanie programu symulującego koszty właśnie przygotowywanej promocji.

Przygotowywana promocja ma mieć następujące zasady:

  • klient, który chce wziąć udział w promocji, wpisuje na zapłaconym przez siebie rachunku swoje dane i wrzuca go do specjalnej urny,
  • pod koniec każdego dnia promocji z urny wyciągane są dwa rachunki:
    • najpierw wybierany jest rachunek opiewający na największą kwotę,
    • następnie wybierany jest rachunek opiewający na najmniejszą kwotę;

       klient, który zapłacił największy rachunek otrzymuje nagrodę pieniężną równą różnicy pomiędzy wysokością jego rachunku, a wysokością rachunku opiewającego na najmniejszą kwotę,
  • aby uniknąć kilkukrotnych nagród za jeden zakup, oba wybrane wg reguł z poprzedniego punktu rachunki nie wracają już do urny, ale wszystkie pozostałe rachunki dalej biorą udział w promocji.

Obroty supermarketu są bardzo duże, możesz więc założyć, że pod koniec każdego dnia, przed wyciągnięciem rachunków opiewających na największą i najmniejszą kwotę, w urnie znajdują się co najmniej 2 rachunki.

Twoim zadaniem jest obliczenie na podstawie informacji o wysokościach rachunków wrzucanych do urny w poszczególnych dniach promocji, jaki będzie łączny koszt nagród w całej promocji.

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego PRO.IN listę wysokości rachunków wrzucanych do urny w poszczególnych dniach promocji,
  • obliczy łączny koszt nagród wypłacanych w kolejnych dniach promocji,
  • zapisze wynik w pliku tekstowym PRO.OUT.

Wejście

W pierwszym wierszu pliku tekstowego PRO.IN znajduje się jedna dodatnia liczba całkowita n, gdzie 1 leq n leq 5000, oznaczająca czas trwania promocji w dniach.

W każdym z kolejnych n wierszy znajduje się ciąg nieujemnych liczb całkowitych pooddzielanych pojedynczymi odstępami. Liczby w (i+1)-szym wierszu pliku określają wysokości rachunków wrzuconych do urny w i-tym dniu promocji. Pierwsza w wierszu liczba k0leq kleq 10^5, jest liczbą rachunków z danego dnia, a kolejne k liczb to dodatnie liczby całkowite będące wysokościami poszczególnych rachunków, każda z tych liczb jest nie większa niż 106.

Łączna liczba rachunków wrzuconych do urny podczas całej promocji nie przekracza 106.

Wyjście

Plik tekstowy PRO.OUT powinien zawierać dokładnie jedną liczbę całkowitą równą łącznemu kosztowi nagród wypłacanych podczas całej promocji.

Przykład

Dla pliku wejściowego PRO.IN
5
3 1 2 3
2 1 1
4 10 5 5 1
0
1 2
poprawną odpowiedzią jest plik wyjściowy PRO.OUT
19

Rozwiązanie

Przy rozwiązaniu tego zadania bardzo pomocna będzie struktura danych umożliwiająca wykonywanie następujących operacji:

  ADD(x) - dodanie elementu x do struktury;   MIN - podanie wartości minimalnego elementu w strukturze;   MAX - podanie wartości maksymalnego element w strukturze;   ExtractMin - usunięcie minimalnego elementu;   ExtractMax - usunięcie maksymalnego elementu.

Zwykły kopiec (zob. [13]) oferuje efektywną implementację trzech z tych operacji: ADD, MIN, ExtractMin (lub ADD, MAX, ExtractMax). Rozwiązaniem może być struktura składającą się z dwóch połączonych kopców, jeden z nich udostępnia operacje ADD, MIN, ExtractMin, natomiast drugi ADD, MAX, ExtractMax. W takim rozwiązaniu decydujemy się na pewną rozrzutność i każdy element należący do struktury będziemy pamiętać podwójnie: w pierwszym i drugim kopcu, dodatkowo z każdym elementem jest związany wskaźnik do bliźniaczego elementu w drugim kopcu. Operacje MIN, MAX odwołują się do odpowiednich kopców i wymagają stałego czasu. Operacja ADD wymaga dodania elementu do obu kopców, oraz uaktualnienia wskaźników, i tak jak w zwykłym kopcu wymaga czasu O(logn). Operacje ExtractMin, ExtractMax sprowadzają się do wykonania odpowiedniej operacji na odpowiednim kopcu (tym który oferuje tę operację), oraz usunięciu elementu bliźniaczego z drugiego kopca (ponieważ pamiętamy wskaźnik do tego elementu, możemy wykonać i tę operację w czasie O(logn)). Zatem całość również wymaga czasu O(logn). Przy wszystkich modyfikacjach, należy zwracać baczną uwagę na uaktualnianie wskaźników między oboma kopcami.

Rys. 1. Przykład podwójnego kopca

 epsffilepro.1

Rozwiązanie 1

Mając do dyspozycji powyższą stukturę danych, schemat algorytmu jest już oczywisty. Dla każdego dnia dodajemy do struktury rachunki, a następnie wyjmujemy z niej jeden największy i jeden najmniejszy, oraz odpowiednio zwiększamy całkowity koszt promocji.

Niestety takie rozwiązanie, ze względu na bardzo dużą liczbę rachunków, które mogły pojawić się w promocji, nie jest akceptowalne ze względu na ogranicznia pamięciowe. Należy zastanowić się, jakie rachunki na pewno nie mają szans na wyjęcie z urny. Można spostrzec, że gdy mamy w strukturze więcej niż 2n rachunków, to szanse na wyciągnięcie z urny ma jedynie n największych i n najmniejszych, natomiast wszystkie pozostałe, "środkowe" rachunki, nie mają już takiej szansy i można je pominąć. To spostrzeżenie prowadzi już do ulepszonego rozwiązania, które będzie wymagać jedynie pamięci rzędu O(n).

Rozwiązanie 2

  • Dopóki liczba rachunków w strukturze S nie przekracza 2n stosuj rozwiązanie 1.
  • Jeśli liczba rachunków osiągnie 2n, przepisz n najmiejszych do struktury Smin, natomiast n największych do struktury Smax. Strukturę S można już usunąc, natomiast wszystkie dalsze operację będą wykonywane na Smin i Smax. Dodawanie nowego rachunku x wygląda następująco:
    • jeśli x<S_min.MAX, to usuwamy z Smin element S_min.MAX (operacja S_min.ExtractMax) i dodajemy x do Smin;
    • jeśli x>S_max.MIN, to postępujemy symetrycznie jak w poprzednim przypadku (zamieniając MAX na MIN i Smin na Smax);
    • w przeciwnym przypadku możemy zapomnieć o tym rachunku.
    Chcąc wydobyć rachunek o najmniejszej wartości wykonujemy operację ExtractMin na Smin i analogicznie, chcąc otrzymać rachunek o największej wartości wykonujemy operację ExtractMax na Smax.

Testy

Do sprawdzania rozwiązań zawodników użyto 10 testów opisanych poniżej:

  • PRO1-6.IN - proste testy poprawnościowe,
  • PRO7.IN - trudny test wydajnościowy, n=5000, K=100006,
  • PRO8.IN - prosty test, prawie każdego dnia dwa rachunki, n=5000, K=210004,
  • PRO9.IN - duży test wydajnościowy, n=5000, K=1000000,
  • PRO10.IN - duży, losowy test wydajnościowy, n=5000, K=999800.