Cod sursa(job #465918)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 25 iunie 2010 13:58:56
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.69 kb
#include<stdio.h>
#define dd double
#define eps 0.0000001

int k,n,v[100009],sol;
dd s,a,b,rec;

struct comb
{
    double x,z;
    int y;
};

comb heap[250006];


int cmp(double a,double b)
{
    if(a+eps>b)
        return 1;
    return 0;
}

void perc(int nod)
{
    int r1=cmp(heap[nod].z,heap[2*nod].z);
    int r2=cmp(heap[nod].z,heap[2*nod+1].z);
    int r3=cmp(heap[2*nod].z,heap[2*nod+1].z);
    if(r1 && r2)
        return ;
    comb aux;
    if(r3)
    {
        aux=heap[nod];
        heap[nod]=heap[2*nod];
        heap[2*nod]=aux;
        perc(2*nod);
        return ;
    }
    aux=heap[nod];
    heap[nod]=heap[2*nod+1];
    heap[2*nod+1]=aux;
    perc(2*nod+1);
}

void sift(int nod)
{
    if(nod==1)
        return ;
    if(cmp(heap[nod].z,heap[nod/2].z))
    {
        comb aux;
        aux=heap[nod];
        heap[nod]=heap[nod/2];
        heap[nod/2]=aux;
        sift(nod/2);
    }
}

void add(double val)
{
    heap[++k].x=val;
    heap[k].z=val*(1-a);
    sift(k);
}

int main ()
{
    int i;
    dd val;
    freopen("minim2.in","r",stdin);
    freopen("minim2.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        s+=v[i];
    }
    scanf("%lf%lf%lf",&a,&b,&rec);
    for(i=1;i<=n;i++)
    {
        val=v[i];
        add(val);
    }
    while(cmp(s,rec))
    {
        s-=heap[1].x;
        if(!heap[1].y)
        {
            heap[1].x*=a;
            heap[1].y=1;
        }
        else
            heap[1].x*=b;
        s+=heap[1].x;
        heap[1].z=heap[1].x*(1-b);
        perc(1);
        sol++;
        if(sol>200006)
        {
            printf("500000000\n");
            return 0;
        }
    }
    printf("%d\n",sol);
    return 0;
}