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

Added by:

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