Cod sursa(job #1739061)

Utilizator GoogalAbabei Daniel Googal Data 8 august 2016 15:40:52
Problema Minim2 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <fstream>
#include <vector>
#include <algorithm>

#define maxn 100010
#define maxp 14
#define eps 0.000001

using namespace std;

ifstream fin("minim2.in");
ofstream fout("minim2.out");

int n, i, j, k, sol, csol;
double v[maxn], bpt[maxp];
double a, b, r, sum;

vector<double> t;

double reduce(double x, double value)
{
    if(x*(1-a)<value)
        return x;

    if(x*a*(1-b)<value)
    {
        ++csol;
        t.push_back(x*(1-a));
        return x*a;
    }

    x=x*a;
    csol+=2;
    for(int i=maxp-1; i>=0; --i)
        if(x*bpt[i]*(1-b)>=value)
        {
            csol+=(1<<i);
            x*=bpt[i];
        }

    t.push_back(x*(1-b));
    return x*b;
}

int check(double value)
{
    double csum=0;

    t.clear();
    csol=0;
    for(int i=1; i<=n; ++i)
        csum+=reduce(v[i], value);

    sort(t.begin(), t.end());
    for(int i=0; i<t.size(); ++i)
        if(csum+t[i]<r+eps)
        {
            --csol;
            csum+=t[i];
        }
        else
            break;

    if(csum<r+eps)
        return 1;
    return 0;
}

int main()
{


    fin>>n;
    for(int i=1; i<=n; ++i)
        fin>>v[i];

   fin>>a>>b>>r;

    bpt[0]=b;
    for(int i=1; i<maxp; ++i)
        bpt[i]=bpt[i-1]*bpt[i-1];

    double left=0, med, right=1000000000;

    sol=1000000000;
    for(int i=1; i<=50; ++i)
    {
        med=(left+right)/2;
        if(check(med))
        {
            sol=min(csol, sol);
            left=med;
        }
        else
            right=med;
    }

  fout<<sol;
    return 0;
}