Skip to content

Candy sticks

Image

Description

There are \(M\) kids and \(N\) candy sticks.
Kids will be happy only if every kid receives candy stick of the same length.
Candy sticks can be split, but it's not possible to stick them together.

The task is to find the maximum length of the candy stick and make kids happy.

Input data

The first line contains \(N\) - number of candy sticks, \(M\) - number of kids.
Second line contains \(N\) integers - \(a_{i}\) length of the \(i_{th}\) candy stick.

Output data

Maximum length of the candy stick with error that doesn't exceed \(10^{-4}\).

Constraints

1 \(\leqslant\) N, M \(\leqslant\) \(1000\),
0 \(\leqslant\) \(a_{i}\) \(\leqslant\) \(10^9\)

Example test cases

Input:
3 4
1 10 5
Output:
3.333333

Input:
3 5
1 1 1
Output:
0.500000

Solution

Solution is to run the binary search for the length of the candy stick.
At first, find the boundaries for the binary search lines [6-19].
If the number of sticks is more than number of kids then the shortest stick length is the left boundary else 0.

Search invariant: for each length \(m\) check the amount sticks that is possible to obtain by splits [25-28].
If the amount of sticks is more or equal to kids number, then update the left boundary, right otherwise.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int main()
{
    int N, M;
    cin >> N >> M;

    vector<double> v(N, 0);
    double l = INT_MAX;
    double r = INT_MIN;
    for(int i = 0; i < N; ++i)
    {
        cin >> v[i];
        l = std::min(l, v[i]);
        r = std::max(r, v[i]);
    }

    if(M > N)
    {
        l = 0;
    }

    while(r - l > 0.0000001)
    {
        double m = l + (r - l)/2;
        int count = 0;
        for(const auto a : v)
        {
            count += a / m;
        }
        if(count >= M)
        {
            l = m;
        }
        else
        {
            r = m;
        }
    }

    printf("%.7lf", l);

    return 0;
}
Solution time complexity: \(O(N*log(max(a_{i})))\)
Solution memory complexity: \(O(N)\)

References