The smallest ship that still finishes in time

Medium

2000 ms limit256 MB memoryBinary search Arrays

Stuck?

Show a hint

Do not search the list, search the answer. A capacity can be checked in one pass, and if one works then every larger one does, which is exactly the run binary search needs.

The idea behind this problem

Binary search on the answer, when nothing is sorted

Next in this lesson

Sharing the books so nobody reads too much

Packages must be shipped within days days. They are loaded in the order given and never reordered, and a day's load cannot exceed the ship's capacity. Report the smallest capacity that gets everything shipped in time.

Worked example#

Weights [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5.

A capacity of 15 works:

day 1: 1 2 3 4 5   (15)
day 2: 6 7         (13)
day 3: 8           (8)
day 4: 9           (9)
day 5: 10          (10)

Fourteen does not: it needs six days. So the answer is 15.

The idea, and it is not about sorting#

Nothing here is sorted, so this looks like the wrong place for binary search. It is not, because you are not searching the list. You are searching the answer.

Two things make that work.

You can check an answer quickly. Given a capacity, walk the packages once, starting a new day whenever the next one will not fit, and count the days. That is one pass.

The answers are monotone. If a capacity of 15 works, 16 works too: more room cannot need more days. And if 14 fails, 13 fails. So the range of possible capacities looks like:

no no no no YES YES YES YES
              ^
        the answer

A sorted run of no-then-yes is exactly what binary search is for. Halve the range, test the middle, keep the half that still contains the boundary.

Picking the ends#

The smallest capacity worth considering is the heaviest single package: below that, one package never fits and no number of days helps. The largest worth considering is the sum of everything: that ships in one day and nothing bigger helps.

Getting those wrong is the usual bug. Starting the low end at 1 makes the check say "impossible" for small capacities, which is fine if your check handles it and a division by zero or an infinite loop if it does not.

The shape#

low, high = max(weights), sum(weights)
while low < high:
    mid = (low + high) / 2
    if days_needed(mid) <= days: high = mid      # mid works, and might be the smallest
    else:                        low = mid + 1   # mid is too small
return low

Note high = mid and not mid - 1: mid worked, so it is still a candidate for the smallest. That asymmetry is what makes this find the boundary rather than step past it.

Where else this appears#

Allocating pages to students, painter partition, aggressive cows, the smallest divisor under a threshold, Koko and her bananas. All of them are: guess an answer, check it in one pass, and use monotonicity to halve the guesses. Once you recognise the shape, they stop being separate problems.

Constraints#

1 <= n <= 50000
1 <= days <= n
1 <= weights[i] <= 500

Input

weights is a count then that many integers. days is a single integer on the next line.

Output

Print the smallest capacity that ships everything in time.

Examples

Input

10
1 2 3 4 5 6 7 8 9 10
5

Output

Fifteen fits in five days and fourteen does not.

Input

5
3 2 2 4 1
3

Output

Five is enough: 3 2 then 2 4 then 1. Four is not.

Input

3
1 2 3
3

Output

One package a day, so the heaviest decides it.

Something wrong with this problem? Report an issue

Ready to try it

Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.

Create a free account Sign in

Free, and it stays free. No card.