Cod sursa(job #465807)

Utilizator irene_mFMI Irina Iancu irene_m Data 25 iunie 2010 13:15:56
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 2.39 kb
#include <cstdio>
#include <algorithm>
#define infile "minim2.in"
#define outfile "minim2.out"
#define tt(x)	((x)/2)
#define fs(x)	(2*(x))
#define fd(x)	(2*(x)+1)
#define MaxN 100024

double d[MaxN],R,S;
int N,L;
double A,B,t[MaxN],heap[MaxN];
long long sol;

void read()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        scanf("%Lf",&d[i]);
        S+=d[i];
    }
    scanf("%Lf%Lf",&A,&B);
    scanf("%Lf",&R);
}

int cmp(double x,double y)
{
    return x-y>0.00001;
}

void up_heap(int nod)
{
    double aux;
    while(nod>1 && heap[nod]>heap[tt(nod)]+0.00001)
    {
        aux=heap[nod]; heap[nod]=heap[tt(nod)]; heap[tt(nod)]=aux;
        aux=t[nod]; t[nod]=t[tt(nod)]; t[tt(nod)]=aux;
        nod=tt(nod);
    }
}

void down_heap(int nod)
{
    double aux;
    while((fs(nod)<=L && heap[nod]<heap[fs(nod)]+0.00001) ||
		(fd(nod)<=L && heap[nod]<heap[fd(nod)]+0.00001))
	{
		if(fd(nod)<=L)
		{
			if(heap[fs(nod)]>heap[fd(nod)]-0.00001)
			{
				aux=heap[nod]; heap[nod]=heap[fs(nod)]; heap[fs(nod)]=aux;
				aux=t[nod]; t[nod]=t[fs(nod)]; t[fs(nod)]=aux;
				nod=fs(nod);
			}
			else
			{
				aux=heap[nod]; heap[nod]=heap[fd(nod)]; heap[fd(nod)]=aux;
				aux=t[nod]; t[nod]=t[fd(nod)]; t[fd(nod)]=aux;
				nod=fd(nod);
			}
		}
		else
		{
			aux=heap[nod]; heap[nod]=heap[fs(nod)]; heap[fs(nod)]=aux;
            aux=t[nod]; t[nod]=t[fs(nod)]; t[fs(nod)]=aux;
            nod=fs(nod);
		}
	}

}

void solve()
{
    int i;
    for(i=1;i<=N;i++)
    {
        t[i]=A;
        heap[++L]=d[i], up_heap(L);
    }

    int nod;
    while(S-R>0.00001)
    {
        nod=1;
        while(S-heap[nod]+heap[nod]*t[nod]>S-heap[fs(nod)]+heap[fs(nod)]*t[fs(nod)]+0.00001 ||
              S-heap[nod]+heap[nod]*t[nod]>S-heap[fd(nod)]+heap[fd(nod)]*t[fd(nod)]+0.00001)
              if(S-heap[nod]+heap[nod]*t[nod]>S-heap[fs(nod)]+heap[fs(nod)]*t[fs(nod)]+0.00001)
                nod=fs(nod);
            else
                nod=fd(nod);

        S-=heap[nod]; S+=heap[nod]*t[nod];
        heap[nod]*=t[nod];
        if(t[nod]==A)
            t[nod]=B;

        down_heap(nod);
        sol++;
    }

}

void write()
{
    printf("%lld\n",sol);
}
int main()
{
    freopen(infile,"r",stdin);
    freopen(outfile,"w",stdout);

    read();
    solve();
    write();

    fclose(stdin);
    fclose(stdout);
    return 0;
}