Elevator
InterviewTime limit1sMemory limit1024 MB
Four children with known weights share an elevator with a passenger limit and a weight limit; find the minimum number of trips.
- Level
Easy3 of 10
- Topics
- Brute force, Implementation, Greedy, Bit manipulation
- Solved
- No attempts yet
Problem
Every elevator has a sign showing its capacity: the maximum number of passengers that can ride it at one time, and the maximum weight in kilograms it can carry.
Petar, Ivan, Dani, and Mira called the elevator of Hotel Shumen to reach their floor. After reading the capacity sign, they asked themselves this question.
Given how many kilograms each of them weighs and the capacity of the elevator, how should they group themselves so that they reach their floor with the fewest elevator calls?
Help them by writing a program lift that, given t1, t2, t3, t4, the weights of four children, the maximum number of passengers that can ride the elevator at one time M, and the maximum allowed weight N, solves this problem.
Input
The first line of the standard input contains two integers M and N. The second line contains four integers t1, t2, t3, t4. The numbers are separated by a single space.
Output
On the single line of the standard output, print one integer: the minimum number of elevator calls.
Constraints
- 2 ≤ M ≤ 100
- 0 < N ≤ 1000
- 0 < t1, t2, t3, t4 ≤ N
Hint
If the children weigh 25, 28, 33, and 18 kilograms respectively, the elevator can carry at most 4 people with a maximum weight of 100 kilograms, and they must call the elevator 2 times. The children weigh 25+28+33+18=104>100 in total, and despite the elevator being able to carry 4 people, they must split into two elevator trips.