SPOJ Problem Set (domowe) 4104. Lokaty
Problem code: ASD09L2
Jasio rozpoczął swoją pierwszą pracę. Pracodawca zna jednak niefrasobliwe podejście Jasia do pieniędzy, więc wynagrodzenie będzie otrzymywał w postaci lokat i co miesiąc może zamknąć tylko jedną z nich. W ramach zaliczki (i zachęty do starannej pracy) w momencie rozpoczęcia pracy otrzymuje także pewną ilość lokat. Ponieważ czasy są burzliwe i oprocentowanie lokat zmienia się z miesiąca na miesiąc, każda kolejna otrzymana lokata jest inaczej oprocentowana (ale oprocentowanie pojedynczej lokaty nie zmienia się w czasie). Jasio wie, że nie będzie potrafił się powstrzymać przed wydaniem wszystkich pieniędzy z lokaty, chce jednak zarobić jak najwięcej. W każdym miesiącu musi zatem zamknąć najniżej oprocentowaną spośród posiadanych lokat (przy czym zamyka lokatę zanim otrzyma wynagrodzenie za kolejny miesiąc). Napisz program, który podpowie Jasiowi, które lokaty należy zamykać w kolejnych miesiącach.
Wejście
Na początku zostaną podane dwie liczby: n i m. n to ilość lokat otrzymanych w ramach zaliczki, zaś m to liczba miesięcy, przez które Jaś będzie pracował. Następnie zostanie podane n liczb - będzie to oprocentowanie lokat otrzymanych w ramach zaliczki. Po nich wystąpi m liczb - będą to oprocentowania lokat otrzymanych za kolejne przepracowane miesiące. Wszystkie liczby będą całkowite i dodatnie. 1 <= n, m <= 100000, pozostałe liczby nie będą większe niż milion.
Wyjście
Na wyjściu powinno pojawić się n + m liczb - wartości oprocentowania zamykanych lokat w kolejnych miesiącach (lokat wystarczy Jasiowi jeszcze na n miesięcy po zakończeniu pracy).
Przykład
Wejście
3 4
5 4 3
1 2 7 6
Wyjście
3
1
2
4
5
6
7
1
Krzysztof M. Ocetkiewicz
Date:
2009-03-22
Time limit: 3s
Source limit:50000B
Languages: C C99 strict C++ 4.0.0-8 C++ 4.3.2
2