HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC-2014-15 Questions > problem:


Ind_01-50. 50718 - Elevator

IMPC-2014-15 Questions

Start: Nov.22.2014 at 03:00:00 PM
Finish: Nov.22.2014 at 08:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 3rd-6. 50695 - Longest link between...
• 4th-1. 50491 - Brokers
• 4th-2. 50524 - Elevator
• 4th-3. 50535 - Image Compression
• 4th-6. 50536 - Epoka Furgon Shpk
• Ind_01-10. 50752 - Student Groups
• Ind_01-20. 50416 - Placing Domino...
• Ind_01-30. 50764 - Fast Typing Co...
• Ind_01-50. 50718 - Elevator
• Ind_02-10. 50497 - Falling Bricks - ...
• Ind_02-20. 50745 - Bitonic Sequence
• Ind_02-30. 50657 - Permutations an...
• Ind_03-10. 50743 - Total Scholarshi...
• Ind_03-20. 50515 - Lines - Revisited
• Ind_03-40. 50777 - Dwarfs Maze
• Ind_03-50. 50679 - Jetpack Hurdle J...
• Ind_04-10. 50787 - Expected Value

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 Ilshat Safiullin.

Elevator

Making an elevator control algorithm is a very complicated task. The main purpose of the elevator control systems is to minimize the total waiting time of the people at the corridor. People don't care about the time passed in the elevator, but they don't have any patience to wait for an elevator.

Question: You should make a program for an N-floor building to let people go to work as quickly as possible. There is only one elevator with the capacity for M people. The elevator travels between two consecutive floors in 1 second and people enter or leave the elevator in 1 second. The elevator is resting on the ground floor (floor 1) at the beginning.

Input specification
There are two integers N (2 ≤ N ≤ 11) and M (M ≤ 30) on the first line of the input. The second line of the input, has N-1 integers pi (pi ≤ M) that represent the number of people in each floor starting from the second floor.

Output specification
The output has a single integer that is the minimum total waiting time.

Sample Input I
4 4
2 0 3
Sample Input II
4 5
2 0 3
Sample Output I
23
Sample Output II
14

Explanation: Elevator goes to the second floor in one second. 2 people there have totally waited 2 seconds. And in one second, they get on to the elevator. Then, elevator goes down to the first floor in one second and people get off from the elevator in one second. Total time passed is 4 seconds.

Then, elevator climbs to the fourth floor in 3 seconds. The people on the fourth floor have waited 7 seconds and it makes 21 seconds totally for all 3 people. This makes totally 23 (21+2) seconds for all the people.



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

www.contester.ru