HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50524 - Elevator

Guest
• Review clarifications (1)

Section problems

• 50997 - Dynamic Knights
• 50936 - Saving the Soldiers
• 50979 - Minimum access cost for BST
• 51062 - Fish Pond II
• 51010 - Max Sequential Sum
• 51072 - Castle on chessboard
• 51075 - Shortest Path for Bishop
• 50688 - Epoka Furgon
• 50524 - Elevator
• 50536 - Epoka Furgon Shpk
• 50687 - Pascal Triangle - 2
• 50689 - The biggest building block
• 50686 - The Container
• 50682 - Hotel Durres
• 50930 - Tom and Jerry
• 50526 - Gold Market
• 50488 - Connecting Wires

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.

Elevator

The university has a new building. For the economic difficulties, the elevator just carries people from ground floor to the upper floors. Thus people walk down when returning. The people are grouped according to the floor numbers they want to go. Then, until the elevator is full. The elevator climbs up till the last person's destination floor. Then, it returns back to the ground floor. To give a fast service, the elevator starts lifting people who wants to go to the lowest floors.

Question: Write a program that is going to read the people and elevator information, then your program will calculate the total number of floors that the elevator has traveled.

Input specification
You will be given two integers in the first line: the number of floors (n) and the capacity of the elevator (cap: the number of people it can carry at once). Then in the following n lines you will be given integers which are between 0 and 1000. n is an integer between 1 and 30000 and cap is between 1 and 1000.

Output specification
Show one integer: the total number of floors that the elevator has climbed.

Sample Input I
5 6
4
3
8
2
0
Sample Output I
9

Explanation:
There five floors and elevator can carry at most 6 people. And, there are 4 people waiting for the first floor, 3 people waiting for the second floor, etc.

  • On the first run, the elevator takes 4 people for the first floor and 2 people for the second floor. And it leaves them to their floors: climbed up to the second floor.
  • On the second run, it takes 1 person for the second floor and 5 people for the third floor: climbed up to the third floor; and the total number of floors climbed is 5.
  • On the last run, it takes 3 people for the third floor and 2 people for the fourth floor: climbed up to the 4th floor; and the total is 9.


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

www.contester.ru