Time limit 4000/4000/4000/4000 ms. Memory limit 3500/25000/65000/65000 Kb.
Question by Sidrit Reka (Adapted from Algorithms, 4th Edition).
Top M Customers
E-304 is the newest bank that is operating in Albania.
In order to get some immediate popularity in the market,
the bank director decided to make a special offer. He
decided that all the customers of the bank that will make
deposits on January 10th 2015 in the main office that is
located in Berxulle, will get 10% of their deposit amount
as a bonus at the same day.
When people heard about this special offer, they went
directly to the main office in order to benefit from it.
There were so many people in the office so the director
decided to put some limit to the offer. He said that the
bank personnel were not able to handle all of the requests
that came, so that they would accept only the top m
customers that will make a deposit with a higher amount
of money. In case there are 2 customers with same amount
of money, the customer whose name is higher in
alphabetical order will be selected.
This decision brought a problem to the computer engineers
of the bank. In order to calculate the top m customers
from all the people that came, the engineers decided to
use the only computer that was found in the office, but
that computer is very old and its memory cannot even hold
the whole list of the customers. Can you help them to
solve this problem considering the memory limitations?
Question:
Write a program that will get the whole list of the
customers and their deposit amounts as an input
and should output the top m customers (sorted in
increasing order) based on their deposit amounts
(and sorted in decreasing order based on their names
if their amounts are equal) .
Input specification
You will be given a number (4 <= n <= 200000) which
represents the number of customers that want to make
a deposit. Then you will get on another line a number
(1 <= m <= n/4) which is the number of the top
customers that the bank will choose. Then you will
get a list of n customers on separate lines represented
by their name (a String of at most 10 alphanumeric
characters) and their deposit amount (an integer 1
<= k <= 10000).
Output specification
Show the names of the top m customers sorted in
increasing order based on their deposit amounts
(and sorted in decreasing order based on their
names if their amounts are equal).
|
Sample Input I |
Sample Input II |
4
1
Arber 50
Agim 75
Ermira 66
Beni 24
|
9
2
Arber 50
Agim 75
Ermira 66
Beni 24
Denis 33
Ina 10
Iris 55
Marvin 43
Lori 81
|
|
Sample Output I |
Sample Output II |
Agim
|
Agim
Lori
|
Для отправки решений необходимо выполнить вход.
|