Polish version    English version  
  O olimpiadzie -> Zadania -> VII OI 1999/2000


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
VII Olimpiada Informatyczna 1999/2000

Zadanie: PRO
Autor: Tomasz Waleń
Promocja

Zawody III stopnia, dzień drugi 13 kwietnia 2000
Plik źródłowy: PRO.??? (np. pas, c, cpp)
Plik wykonywalny: PRO.exe
Plik wejściowy: PRO.in
Plik wyjściowy: PRO.out

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<=n<=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 k, 0<=k<=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ż 10^6.

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

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



Wersja do druku