Problem Description

A programming competition is being organized where all participant computers must be connected to a central server using equal-length cables arranged in a star topology. Given a colleciton of network cables of various lengths, the objective is to determine the maximum possible length such that exactly K segments of equal length can be obtained by cutting the available cables.

Input Format

The first line contains two integers N and K representing the number of cables and required segments respectively. This is followed by N lines each containing a decimal number indicating the length of a cable in meters, accurate to two decimal places.

Output Format

Output a single line with the maximum segment length in meters, formatted to two decimal places. If it's impossible to obtain even 1 cm length segments for all K pieces, output "0.00".

Sample Input

4 11
8.02
7.43
4.57
5.39

Sample Output

2.00

Solution Approach

This problem can be solved efficiently using binary search on the possible segment lengths. Since we want to maximize the length, we perform a search over the range from 1 centimeter up to the longest cable length. For each candidate length, we calculate how many total segments can be produced. If the count meets or exceeds the requirement, we attempt a larger length; otherwise, we reduce our search space.

To avoid floating point inaccuracies, all measurements are converted to centimeters during computation and converted back for output.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

class CableCutter {
private:
    vector<int> stock_lengths;  // Lengths in centimeters
    int required_count;
    
public:
    CableCutter(int n, int k) : required_count(k) {
        stock_lengths.reserve(n);
    }
    
    void add_cable(double length_meters) {
        stock_lengths.push_back(static_cast<int>(length_meters * 100));
    }
    
    int compute_max_segments() {
        if (stock_lengths.empty()) return 0;
        
        int left_bound = 1;
        int right_bound = *max_element(stock_lengths.begin(), stock_lengths.end());
        int optimal_length = 0;
        
        while (left_bound <= right_bound) {
            int test_length = left_bound + (right_bound - left_bound) / 2;
            long long total_pieces = 0;
            
            for (int cable : stock_lengths) {
                total_pieces += cable / test_length;
            }
            
            if (total_pieces >= required_count) {
                optimal_length = test_length;
                left_bound = test_length + 1;
            } else {
                right_bound = test_length - 1;
            }
        }
        
        return optimal_length;
    }
};

int main() {
    int n, k;
    cin >> n >> k;
    
    CableCutter cutter(n, k);
    
    for (int i = 0; i < n; ++i) {
        double length;
        cin >> length;
        cutter.add_cable(length);
    }
    
    int result_cm = cutter.compute_max_segments();
    cout << fixed << setprecision(2) << result_cm / 100.0 << endl;
    
    return 0;
}