Loading...
Loading...
Loading...
Ravi's grandmother made n boxes of laddoos, and box i holds p[i] laddoos. Ravi has h hours before the guests arrive.
Ravi picks a speed s. Each hour he chooses one box and eats up to s laddoos from it. If that box has fewer than s left, he finishes it and waits for the rest of the hour. He never eats from two boxes in the same hour.
Print the smallest whole number s that lets him empty every box within h hours.
Example 1
Input
4 8 3 6 7 11
Output
4
At s = 4 he needs 1 + 2 + 2 + 3 = 8 hours. At s = 3 he needs 10 hours.
Example 2
Input
5 5 30 11 23 4 20
Output
30
One hour per box, so s must be the largest box, 30.
Try the problem first. Open one hint at a time.
If a speed s works, every faster speed also works. If s fails, every slower speed fails.
So the answer is the boundary between "too slow" and "fast enough", somewhere from 1 to the largest box.
Search that range by halving it: test the middle speed, then keep the half where the boundary must be.
For a speed s, box p takes (p + s - 1) / s hours. Add the hours in a long, because the total can pass 2 × 10^9.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor