Cod sursa(job #2349558)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 20 februarie 2019 16:13:58
Problema Minim2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include<bits/stdc++.h>
#define Nmax 100010
using namespace std;
ifstream f("minim2.in");
ofstream g("minim2.out");
int n;
int z[Nmax];
double dist[Nmax], p[20010], a, b, r;
double eps = 1e-6;
int itt;
int mx;
double timp;
bool check(double c)
{
    timp = 0.00000000;
    for(int i = n; i >= 1; --i)
    {
        int st = 0;
        int dr = mx - 1;
        int ans = 0;
        double aa = dist[i];
        if(aa * (1 - a) >= c)
            aa *= a, ++itt;
        while(st <= dr)
        {
            int mid = (st + dr) / 2;
            double diff = aa * (p[mid] * p[mid + 1]);
            if(c >= diff)
                ans = mid, dr = mid - 1;
            else
                st = mid + 1;
        }
        timp = timp + aa * p[ans];
        itt += ans;
    }
    return (timp - r < eps);
}
int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i)
        f >> z[i];
    sort(z + 1, z + n + 1);
    for(int i = 1; i <= n; ++i)
        dist[i] = z[i];
    f >> a >> b >> r;
    p[0] = 1.0000000;
    for(int i = 1; i <= 20001; ++i)
    {
        p[i] = p[i-1] * b;
        if(p[i] > eps)
            ++mx;
        else
            break;
    }
    double st = 0.0000000;
    double dr = 1000000000.0000000;
    long long ans = 0;
    while(dr - st > eps)
    {
        itt = 0;
        double mid = (st + dr) * 0.500000000;
        if(check(mid))
            st = mid, ans = itt;
        else
            dr = mid;
    }
    g << ans - (int)((r - timp) / st);
    return 0;
}