Binary Search on the Answer

Lab C++ Advanced 30 points

n boards have lengths Lᵢ. You need k pieces of equal integer length cut from them. Print the largest possible piece length (0 if impossible), by binary searching the answer.

Input

n k, then n lengths.

Output

One integer.

Example

Input

4 11
802 743 457 539

Output

Sample input available Sample output available

Editor

C++

Hints

Longer pieces mean fewer pieces - the question is monotonic, so binary search works.

Solution explanation

"Binary search on the answer" turns an optimisation problem into a yes/no check.

Show solution

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> L(n);
    long long hi = 0;
    for (auto &x : L) {
        cin >> x;
        hi = max(hi, x);
    }
    auto pieces = [&](long long len) {
        long long total = 0;
        for (long long x : L) total += x / len;
        return total;
    };
    long long lo = 1, best = 0;
    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        if (pieces(mid) >= k) {
            best = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    cout << best << "\n";
    return 0;
}

Output

Answer