Cod sursa(job #515540)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 21 decembrie 2010 17:58:39
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include<cstdio>
#define modul(x) x<0?(-x):x
const double e=0.000001;
int n;
double s,A,B,record,v[1<<17],pb[1<<14];
void read()
{
    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,&record);
}
void init()
{
    pb[0]=1.0;
    for(int i=1;i<=10000;i++)
        pb[i]=(double)pb[i-1]*B;
}
int cb(double x)
{
    int i=0,pas=1<<13;
    for(i=0;pas;pas>>=1)
        if(i+pas<=10000 && pb[i+pas]-x>e && !(modul(pb[i+pas]-x)>e))
            i+=pas;
    return i;
}
bool check(double x)
{
    double auxs=s;
    for(int i=1;i<=n;i++)
    {
        if(x-(v[i]-A*v[i])>e && !(modul(x-(v[i]-A*v[i]))>e))
        {
            int j=cb((double)x/(v[i]-B*v[i]));
            if(j)
            {
                double dc=(double)(v[i]-B*v[i])*(1-pb[j+1])/(1-B);
                auxs-=dc;
            }
        }
        else
        {
            int j=cb((double)x/(v[i]*A-B*A*v[i]));
            if(j)
            {
                double dc=(double)(A*v[i]-A*B*v[i])*(1-pb[j+1])/(1-B)+(v[i]-A*v[i]);
                auxs-=dc;
            }
            else
            {
                double dc=v[i]-A*v[i];
                auxs-=dc;
            }
        }
    }
    if(modul(auxs-record)<=e)
        return true;
    return false;
}
void solve(double x)
{
    int rez=0;
    for(int i=1;i<=n;i++)
    {
        if(x-(v[i]-A*v[i])>e && !(modul(x-(v[i]-A*v[i]))>e))
        {
            int j=cb((double)x/(v[i]-B*v[i]));
            rez+=j;
        }
        else
        {
            int j=cb((double)x/(v[i]*A-A*B*v[i]));
            rez+=j+1;
        }
    }
    printf("%d",rez);
}
void cautb()
{
    double st=0,dr=0;
    for(int i=1;i<=n;i++)
        if(dr<v[i]-A*v[i])
            dr=(double)v[i]-A*v[i];
    while(modul(dr-st)>=e)
    {
        double mid=(double)(st+dr)*0.5;
        if(check(mid))
            st=mid;
        else
            dr=mid;
    }
    solve(st);
}
void makes()
{
    for(int i=1;i<=n;i++)
        s=v[i]+s;
}
int main()
{
    read();
    init();
    makes();
    cautb();
    return 0;
}