Cod sursa(job #961366)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 22:28:13
Problema Minim2 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
#define maxn 100010
#define maxp 13
#define eps 0.000001
 
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()
{
    freopen("minim2.in", "r", stdin);
    freopen("minim2.out", "w", stdout);
 
    scanf("%d", &n);
    for(int i=1; i<=n; ++i)
        scanf("%lf", &v[i]);
 
    scanf("%lf%lf%lf", &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<=48; ++i)
    {
        med=(left+right)/2;
        if(check(med))
        {
            sol=min(csol, sol);
            left=med;
        }
        else
            right=med;
    }
 
    printf("%d\n", sol);
    return 0;
}