Cod sursa(job #465902)

Utilizator indestructiblecont de teste indestructible Data 25 iunie 2010 13:55:13
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.35 kb
#include <stdio.h>
#define NMAX 200005
#define prec 0.000001
int n,op,r;
double A[NMAX],a,b,rez,fin;
struct heap
{
	double a;
	int b;
};
heap B[NMAX];
char marc[NMAX];
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
	{
		scanf("%lf",&A[i]);
		rez+=A[i];
	}
	scanf("%lf%lf%lf",&a,&b,&fin);
}
void interschimba(int x,int y)
{
	double t;
	int p;
	t=B[x].a; B[x].a=B[y].a; B[y].a=t;
	p=B[x].b; B[x].b=B[y].b; B[y].b=p;
}
void urca(int nod)
{
	if (nod>1)
		if (B[nod/2].a<B[nod].a)
		{
			interschimba(nod/2,nod);
			urca(nod/2);
		}
}
void coboara(int nod)
{
	if (B[nod*2].a>B[nod].a || B[nod*2+1].a>B[nod].a)
	{
		int best=nod*2;
		if (nod*2+1<=r && B[nod*2+1].a>B[2*nod].a)
			best=nod*2+1;
		interschimba(best,nod);
		coboara(best);
	}
}
inline double modul(double x)
{
	return x<0 ? -x : x;
}
void solve()
{
	int i;
	for (i=1; i<=n; i++)
	{
		B[++r].a=A[i]; B[r].b=i;
		urca(r);
	}
	while (rez>fin)
	{
		if (!marc[B[1].b])
		{
			marc[B[1].b]=1;
			rez-=(1-a)*B[1].a;
			B[1].a=B[1].a*a;
			coboara(1);
			op++;
		}
		else
		{
			rez-=(1-b)*B[1].a;
			B[1].a=B[1].a*b;
			coboara(1);
			op++;
		}
		if (modul(rez-fin)<prec)
			break ;
	}
}
int main()
{
	freopen("minim2.in","r",stdin);
	freopen("minim2.out","w",stdout);
	read();
	solve();
	printf("%d\n",op);
	return 0;
}