SRM456-D2-1000

#define ll long long
#include <bits/stdc++.h>
using namespace std;

const int OO = 1e9;
const double EPS = 1e-12;

class CutSticks {
public:
    int bs(double s, double thold) {
        ll l = 1;
        ll h = 1e9 + 50;
        ll ans = 1;
        while(l <= h) {
            double mid = (l+h)/2;
            double curr = s/mid;
            if(curr+EPS < thold) {
                h = mid-1;
            }
            else {
                ans = mid;
                l = mid+1;
            }
        }
        return ans;
    }

    double maxKth(vector<int> sticks, int C, int K) {
        ll n =  sticks.size();
        double ansl = 0;
        double ansh = 1e9;
        double ans = 0;
        for(int btimes = 0; btimes < 128; btimes++) {
            double mid = (ansl+ansh)/2.0;
            bool possible = false;
            for(int i = 0; i < n; i++) {
                if(mid-EPS > sticks[i]) {
                    continue;
                }
                ll cuts = 1;
                ll mx_pos = 1;
                ll extra_cuts = 0;
                for(int k = 0; k < n; k++) {
                    if(k == i || mid-EPS > sticks[k]) {
                        continue;
                    }
                    ll pos_add = bs(sticks[k],mid);
                    mx_pos += pos_add;
                    extra_cuts += pos_add-1;
                }
                if(sticks[i]-mid > mid) {
                    ll pos_add = bs(sticks[i]-mid,mid);
                    mx_pos += pos_add;
                    extra_cuts += pos_add-1;
                }
                if(cuts+extra_cuts > C) {
                    mx_pos -= (cuts+extra_cuts-C);
                }
                //cout << "curr_v is " << curr_v << "\n";
                if(mx_pos >= K) {
                    //cout << "mx_pos is " << mx_pos << " at i = " << i << " j = " << j << "\n";
                    possible = true;
                    break;
                }
            }
            if(possible) {
                ans = mid;
                ansl = mid;
            }
            else {
                ansh = mid;
            }
        }
        return ans;
    }

};


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    CutSticks cs;
    cout << cs.maxKth({8},50,3) << "\n";
    //cout << cs.bs(8,1) << "\n";
    /*vector<int> v = {76, 594, 17, 6984, 26, 57, 9, 876, 5816, 73, 969, 527, 49};
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << "\n";
    }*/
    return 0;
}