Cod sursa(job #465833)

Utilizator ursu-valiJerdea Florin ursu-vali Data 25 iunie 2010 13:29:40
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.31 kb
#include<stdio.h>
#define infile "minim2.in"
#define outfile "minim2.out"
#define nmax 100010

long v[nmax];
long s[nmax],n;
float a,b,min;
float z[nmax];
long i,sum=0,nr=1,ok=1;
float q,w;

void read()
{
	long i;
	scanf("%ld",&n);
	for(i=1;i<=n;i++)
		scanf("%ld",&v[i]);
	scanf("%f%f%f",&a,&b,&min);
}
long divide(long p,long q) 
{
	long st=p,dr=q,x=v[p];
	while(st<dr)
	{
		while(st<dr && v[dr]>=x)
			dr--;
		v[st]=v[dr];
		while(st<dr && v[st]<=x)
			st++;
		v[dr]=v[st];
	}
	v[st]=x;
	return st;
}
void qs(long p,long q) 
{
	long m;
	m=divide(p,q);
	if(m-1 > p)
		qs(p,m-1);
	if(m+1 < q)
		qs(m+1,q);
}
void alpha(long i)
{
	long j;
	while(((float)v[i]-z[i]-z[i]*b>z[i-1])&&(ok==1))
		{
			sum+=(float)z[i]*b-z[i];
			nr++;
			z[i]*=b;
			if(sum<min)
			{
				printf("%ld\n",nr);
				ok=0;
			}
			for(j=i+1;j<=n;j++)
				if(z[i]<z[j])
					alpha(j);
		}
}
void solve()
{

	for(i=1;i<=n;i++)
	{
		sum+=v[i];
		z[i]=(float)v[i]*a;
	}
	for(i=n;i>=1 && ok==1;i--)
	{
		sum+=z[i]-v[i];
		if(sum<min)
		{
			printf("%ld\n",nr);
			ok=0;
		}
		alpha(i);
	}
	/*for(i=1;i<=n;i++)
		printf("%ld ",v[i]);*/
}
int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	read();
	qs(1,n);
	solve();
	fclose(stdin);
	fclose(stdout);
	return 0;
}