HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50682 - Hotel Durres

Guest
• Review clarifications (5)

Section problems

• 51072 - Castle on chessboard
• 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

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.

Hotel Durres

Durres is a famous city with its historic and touristic places. Hotel Durres is located in a high mountain and far from the city. It's one of the biggest touristic hotels in the region which accepts many tourists every year.

Because the hotel is far from the city, it uses a gas tank for its heating system. Filling the gas tank costs a lot and the operation is very noisy and disturbing the clients. It's so noisy that it can be handled just once a day (on a certain time of the day). The director of operations, wants to reduce the costs in such a way that the tank will be filled when the amount in the tank cannot support the activities for that day.

Question: Assuming that the tank is full in the beginning, write a program that is going to find out the minimum cost of filling and the amount of gas used for the given period and for the given number of clients. Note: Assume that the amount in the tank supports the max number of people in one day.

Input specification: There are 4 numbers in the first line:

  • number of days: an integer where 0 < (number of days) < 30000
  • Tank capacity: a floating point number between 100 and 5000
  • c: the cost of filling, an integer
  • Gas used per person: a floating point number 0 < (Gas used per person) ≤ 10.
The following n lines list the number of clients for the following n days and each of the number is between 0 and 500.

Output specification
Show two integers: the amount of money spent for filling the tank. The amount of gas bought (with respect to the number of people, like gas for 10 people).

Sample Input I
6 50.0 50 1.0
23 24 15 14 14 47
Sample Output I
100 90

Explanation: In the beginning, the tank is full. Because for every person 1 liter gas is needed, the full tank supports 50 people. So, the current tank supports for the first two days, but it has to be filled before the third day (47 liters bought). Then, the second tank supports the third (15), the fourth (14) and the fifth (14) days (43 liters bought). The current amount suffices for the last day. So, the tank has been filled twice (2x50) $100, and gas for 90 people (90x 1 liters) of gas has been bought.


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

www.contester.ru