Cod sursa(job #2104119)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 11 ianuarie 2018 10:22:55
Problema Minim2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include<fstream>
#include<vector>
#include<algorithm>
#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;
vector<double> V;

bool check(double val)
{
    rez=0;
    sum=0.0;
    double upd=0.0;
    V.clear();
    for(int i=1; i<=n; i++)
    {
        double nr=A[i];
        upd=0.0;
        if((1-a)*nr>=val)
        {
            upd=nr*(1-a);
            nr*=a;
            rez++;
        }
        if((1-b)*nr>=val)
        {
            double aux=nr*(1-b);
            int p=(int)(log(val/aux)/lgb)+1; //in loc de formula se poate face tinand un sir P[i]=b^(2^i)
            nr=nr*P[p];
            if(aux*P[p+1]>=val)
            {
                p++;
                nr=nr*b;
            }
            upd=A[i]*a*(1-b)*P[p];
            rez+=p;
        }
        sum+=nr;
        if(upd!=0)
            V.push_back(upd);
    }
    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);
    sort(V.begin(),V.end());
    for(i=0; i<V.size(); i++)
    {
        if(sum+V[i]<r+(1e-6))
        {
            rez--;
            sum+=V[i];
        }
        else
            break;
    }
    fo<<rez<<"\n";
    fi.close();
    fo.close();
    return 0;
}