Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.
Products in store
Question:
In order to follow the products in store,
a whole sale company needs a program.
You're first given the ids and amounts of m products
from the report for last year.
Then, you are given information for m instructions.
Find the top k items which have the most number (amount)
in the store. Note: Pay attention that
the second list may contain new products which was not
in the list before.
Input specification:
You will be given three integers in the beginning:
- The number of items existing in the
store (n): an integer not greater than 10,000,
- The number of instructions (m):
an integer not greater than 10,000,
- The number of top products to list (k).
Then, the following n lines contain two information:
the product ID and existing amount in the store.
Product ID is at most 10 char long alpha-numeric
sequence and the amount
is a floating point number not greater than 1e6.
Then in the following m lines, you will be given
m instructions. Each instruction contains three
information: a char (E or S), a product ID,
and a number where
- 'E ID N' means N items (of product ID) have
entered to the store.
- 'S ID N' means N items (of product ID) have
been sold from the store.
Output specification:
Show top k products existing in the store
(in descending order). If there are two items
with the same amount, show in ascending order
according to product IDs.
Sample Input
4 5 2
OMVA61 32
ICKX42 50
WPPZ49 34
EUGO62 52
E OMVA61 51
S EUGO62 13
S ICKX42 34
S OMVA61 56
E GCGW69 56.4
|
Sample Output
GCGW69
EUGO62
|
Explanation:
There are 4 products in the store. Then, we are
given 5 instructions. Here is the list of items
and their total amounts after processing m
instructions.
| Product Code |
Amount in the store |
| EUGO62 |
39 |
| GCGW69 |
56.4 |
| ICKX42 |
16 |
| OMVA61 |
27 |
| WPPZ49 |
34 |
Thus, the top two items are GCGW69 and EUGO62.
Для отправки решений необходимо выполнить вход.
|