HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > CEN112 Questions 2016 > problem:


15-FE-2. 50993 - Products in store

CEN112 Questions 2016

Start: Mar.30.2016 at 03:10:22 PM
Finish: Apr.01.2016 at 05:00:00 AM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 15-FE-1. 50992 - Top K Obese Classes
• 15-FE-2. 50993 - Products in store
• 15-FE-3. 50994 - The Most Crowded...
• 15-FE-4. 50995 - Group Average
• 15-FE-6. 50989 - Rectangles and Points
• 15-FE-7. 50990 - Two Neighbors
• 15-FE-8. 50991 - Intersecting Circles
• 15-HW-2. 50932 - Shifting rows and...
• 15-HW-3. 50933 - Sum of the Bigges...
• 15-HW-4. 50934 - Selling Cars

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.



Для отправки решений необходимо выполнить вход.

www.contester.ru