Loading...
Loading...
Loading...
A college plans a trip for n classes. Class i has a[i] students. Every bus has the same size d, and each class travels in its own buses: two classes never share a bus. So class i needs a[i] / d buses, rounded up.
The college can book at most t buses in total. Print the smallest whole number d for which all classes fit.
Example 1
Input
4 6 1 2 5 9
Output
5
With d = 5 the classes need 1 + 1 + 1 + 2 = 5 buses. With d = 4 they need 1 + 1 + 2 + 3 = 7.
Example 2
Input
3 3 40 15 60
Output
60
One bus per class, so d is the largest class, 60.
Try the problem first. Open one hint at a time.
A larger bus never needs more buses. So once some d works, every larger d works too.
The answer is the boundary between sizes that need too many buses and sizes that fit. It lies between 1 and the largest class.
Test the middle size, count the buses with rounding up, and keep the half where the boundary must be.
Read t with Long.parseLong. Add the bus counts in a long, because the total can be near 10^14.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor