Promocja
Limit pamięci: 32 MB
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 ze standardowego wyjścia listę wysokości
rachunków wrzucanych
do urny w poszczególnych dniach promocji,
- obliczy łączny koszt nagród wypłacanych w kolejnych
dniach promocji,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia
znajduje się jedna dodatnia liczba całkowita , gdzie
,
oznaczająca czas trwania promocji w dniach.
W każdym z kolejnych wierszy znajduje się ciąg nieujemnych liczb
całkowitych pooddzielanych pojedynczymi odstępami.
Liczby w -szym wierszu pliku określają wysokości
rachunków wrzuconych do urny w -tym dniu promocji.
Pierwsza w wierszu liczba , ,
jest liczbą rachunków z danego dnia, a kolejne
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ż .
Łączna liczba rachunków wrzuconych do urny podczas
całej promocji nie przekracza .
Wyjście
Standardowe wyjście powinno zawierać dokładnie jedną liczbę
całkowitą równą łącznemu kosztowi nagród wypłacanych podczas całej
promocji.
Przykład
Dla danych wejściowych:
5
3 1 2 3
2 1 1
4 10 5 5 1
0
1 2
poprawną odpowiedzią jest:
19
Autor zadania: Tomasz Waleń.