#include #include #include #include #include #include #define rep(i, a, b) for (ll i = a; i < (b); ++i) #define all(v) (v).begin(), (v).end() using namespace std; using ll = long long; using vi = vector; /** * Author: Ulf Lundstrom * Date: 2009-04-17 * License: CC0 * Source: Numeriska algoritmer med matlab, Gerd Eriksson, NADA, KTH * Description: Finds the argument minimizing the function $f$ in the interval $[a,b]$ assuming $f$ is unimodal on the interval, i.e. has only one local minimum. The maximum error in the result is $eps$. Works equally well for maximization with a small change in the code. See TernarySearch.h in the Various chapter for a discrete version. * Usage: double func(double x) { return 4+x+.3*x*x; } double xmin = gss(-1000,1000,func); * Time: O(\log((b-a) / \epsilon)) * Status: tested */ /// It is important for r to be precise, otherwise we don't necessarily maintain the inequality a < x1 < x2 < b. double gss(double a, double b, auto &&f) { double r = (sqrt(5) - 1) / 2, eps = 1e-6; double x1 = b - r * (b - a), x2 = a + r * (b - a); double f1 = f(x1), f2 = f(x2); while (b - a > eps) if (f1 < f2) { //change to > to find maximum b = x2; x2 = x1; f2 = f1; x1 = b - r * (b - a); f1 = f(x1); } else { a = x1; x1 = x2; f1 = f2; x2 = a + r * (b - a); f2 = f(x2); } return a; } int main() { ios::sync_with_stdio(false); cin.tie(0); auto start = chrono::high_resolution_clock::now(); mt19937 rng(start.time_since_epoch().count()); auto time_left = [&]() { return 1000 - chrono::duration_cast(chrono::high_resolution_clock::now() - start).count(); }; ios::sync_with_stdio(false); cin.tie(0); ll n, f_max; cin >> n >> f_max; vi x(n); rep(i, 0, n) cin >> x[i]; auto g = [&](double f) { ll sum = 0; rep(i, 0, n) sum += ceil(x[i] * f / 1000); return sum / f; }; double best = numeric_limits::infinity(); queue> q; q.push({0, f_max}); while (time_left() > 100) { auto [l, r] = q.front(); q.pop(); auto p = gss(l, r, g); auto x = g(p); if (x < best * 1.1) { q.emplace(l, p); q.emplace(p, r); } best = min(best, x); } cout << setprecision(10) << fixed << best << '\n'; return 0; }