Cod sursa(job #465733)

Utilizator tranbachhaiTran Bach Hai tranbachhai Data 25 iunie 2010 12:40:55
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.57 kb
#include<stdio.h>
#include<math.h>
#define NMAX 400010
#define eps 0.000001
//heap
using namespace std;

double sum,a[3],rec,h[NMAX];
int n,x1,x2,op,tip[NMAX],nr;

void cob(int nod)
{
int aux1,min=nod*2;
double aux;
x2=nod;
if (tip[nod*2] && tip[nod*2+1])
	{
		if (h[nod*2+1]*a[tip[nod*2+1]]>h[nod*2]*a[tip[nod*2]])
			min=nod*2+1;
	}
else if (tip[nod*2]) 
	min=nod*2;
else if (tip[nod*2+1])
	min=nod*2+1;
else	min=-1;
	if (h[min]*a[tip[min]]>h[nod]*a[tip[nod]])
			{
				aux=h[min];
				h[min]=h[nod];
				h[nod]=aux;
				aux1=tip[min];
				tip[min]=tip[nod];
				tip[nod]=aux1;
				cob(min);
			}
}

void urc(int nod)
{
int aux1;
double aux;
x1=nod;
		if (h[nod/2]*a[tip[nod/2]]<h[nod]*a[tip[nod]] && nod>1)
			{
				aux=h[nod/2];
				h[nod/2]=h[nod];
				h[nod]=aux;
				aux1=tip[nod/2];
				tip[nod/2]=tip[nod];
				tip[nod]=aux1;
				urc(nod/2);
			}
}

int main()
{
	int i;
double temp;
	freopen("minim2.in","r",stdin);
	freopen("minim2.out","w",stdout);
	
	scanf("%d",&n);
	scanf("%lf",&temp);
	h[++nr]=temp;
	tip[nr]=1;
	sum=sum+temp;
	a[1]=1;
	for (i=2;i<=n;++i)
		{
		scanf("%lf",&temp);
		h[++nr]=temp;
		tip[nr]=1;
	    urc(nr);
		cob(x1);
		sum=sum+temp;
		}
	scanf("%lf%lf%lf",&a[1],&a[2],&rec);
	a[1]=1-a[1];
	a[2]=1-a[2];
while(!(fabs(sum-rec)<eps || sum<rec))
{
	++op;
	if (tip[1]==1)
		{
			sum=sum-a[1]*h[1];
			tip[1]=2;
			h[1]=h[1]*(1-a[1]);
			cob(1);
			urc(x2);
		}
	else 
		{
			sum=sum-a[2]*h[1];
			h[1]=h[1]*(1-a[2]);
			cob(1);
			urc(x2);
		}
}	
	printf("%d",op);	
	return 0;
}