HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50526 - Gold Market

Section problems

• 51075 - Shortest Path for Bishop
• 50979 - Minimum access cost for BST
• 50688 - Epoka Furgon
• 50689 - The biggest building block
• 50686 - The Container
• 50524 - Elevator
• 50536 - Epoka Furgon Shpk
• 50682 - Hotel Durres
• 50526 - Gold Market
• 50930 - Tom and Jerry
• 50488 - Connecting Wires
• 50842 - Minimum Sum Triangle - DP
• 50676 - Cinema Millennium
• 50678 - The Jumping Rabbit
• 50598 - Minimum Sum
• 50683 - Parking Buses
• 50685 - Guest Room Usage

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.

Gold Market

You work in a jewelry production factory. And you buy different minerals in the form of dust. High security precautions are taken when sending the minerals to the factory. And because, the transportation is very expensive, you want to send the most valuable items the first.

Question: Write a program that is going to read information for n items (weight and price), then the program will show at most how much amount (price) can be transferred at once where the truck has can hold at most c kgs at once. Note: Because you are transferring minerals they can be taken in fractions.

Input specification
You will be given two numbers (n and c) the number of items and the capacity of the truck where n is an integer 0 ≤ n ≤ 3,000 and c is a floating point number 0 ≤ c ≤ 70,000 Then, in the following n lines you will be given two information for each item:

  • Weight: an floating point number between 1 and 1e5
  • Price: an floating point number between 0 and 1e8

Output specification
Show the total amount (price) that can be transferred with 2 digits precision. Because the number can be very big number use fixed notation.

Sample Input I
3 50
20 100
10 60
30 120
Sample Output I
240

Explanation:
The unit price of items are 5, 6 and 4 dollars per kg. Because we want to transfer the most valuable items, we start from the second item ($6 per kg), and we take all. Then, we take all of the first item. But we cannot take all of the third item because it exceeds the capacity of the truck. So, we take only 20 kg from it (Third item is $120, so we can carry 2/3 of it - $80). In total: 60 + 100 + 80 = 240.

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

www.contester.ru