Cod sursa(job #2349591)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 20 februarie 2019 16:28:54
Problema Minim2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 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 pz;
int mx;
double timp;
double lgb;
bool check(double c)
{
    ++pz;
    timp = 0.00000000;
    for(int i = n; i >= 1; --i)
    {
        double nr = dist[i];
        if((1 - a) * nr >= c)
        {
            nr *= a;
            itt++;
        }
        if((1 - b) * nr >= c)
        {
            double aux = nr * (1 - b);
            int q = (int)(log(c / aux) / lgb) + 1;
            nr = nr * p[q];
            if(aux * p[q + 1] >= c)
            {
                q++;
                nr = nr * b;
            }
            itt += q;
        }
        timp += nr;
    }
    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 <= 10000; ++i)
        p[i] = p[i-1] * b;
    lgb = log(b);
    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;
    }
    check(st);
    g << ans - (int)((r - timp) / st);
    return 0;
}