Cod sursa(job #2104103)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 11 ianuarie 2018 09:44:05
Problema Minim2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<fstream>
#include<cmath>
using namespace std;
ifstream fi("minim2.in");
ofstream fo("minim2.out");
int n,i,A[100001],rez;
double lgb,x,a,b,r,P[10001];
long double sum;

bool check(double val)
{
    rez=0;
    sum=0.0;
    for(int i=1; i<=n; i++)
    {
        double nr=A[i];
        if((1-a)*nr>=val)
        {
            nr*=a;
            rez++;
        }
        if((1-b)*nr>=val)
        {
            double aux=nr*(1-b);
            int p=(int)(log(val/aux)/lgb)+1;
            nr=nr*P[p];
            if(aux*P[p+1]>=val)
            {
                p++;
                nr=nr*b;
            }
            rez+=p;
        }
        sum+=nr;
    }
    return (sum-r<1e-6);
}

double bs(double st, double dr)
{
    double mij=0;
    while(dr-st>(1e-6))
    {
        mij=(st+dr)/2;
        if(check(mij))
            st=mij;
        else
            dr=mij;
    }
    return st;
}

int main()
{
    fi>>n;
    for(i=1; i<=n; i++)
        fi>>A[i];
    fi>>a>>b>>r;
    lgb=log(b);
    P[0]=1;
    for(i=1; i<=10000; i++)
        P[i]=P[i-1]*b;
    x=bs(0,1000000000);
    check(x);
    fo<<rez-(int)((r-sum)/x)<<"\n";
    fi.close();
    fo.close();
    return 0;
}