Cod sursa(job #465953)

Utilizator chiar_nimeninimeni chiar_nimeni Data 25 iunie 2010 15:47:15
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
# include <stdio.h>
float d[100001],pr[100001],x,y,p,s,max,sum,suma;
long n,i,nr,poz,mvs;

void inter(long st,long m,long dr){
float a[100002];
for(i=st;i<=dr;i++) a[i]=d[i];
long i1=st;
long i2=m+1;
long k=st-1;
while(i1<=m&&i2<=dr)
if(a[i1]<a[i2]) d[++k]=a[i1++];
else d[++k]=a[i2++];
for(i=i1;i<=m;i++) d[++k]=a[i];
for(i=i2;i<=dr;i++) d[++k]=a[i];
}
void sort(long st,long dr){
if(st!=dr){
long m=(st+dr)/2;
sort(st,m);
sort(m+1,dr);
inter(st,m,dr);
}
}

int main ()
{
freopen ("minim2.in","r",stdin);
freopen ("minim2.out","w",stdout);
scanf ("%ld",&n);
for (i=1; i<=n; i++)
{
	scanf ("%f",&d[i]);
	p+=d[i];
}
scanf ("\n");
scanf ("%f %f %f",&x,&y,&s);
nr=0;
sort (1,n);
for (i=1; i<=n; i++) pr[i]=x;
while (p>s)
{
	mvs=0;
	max=0;
	for (i=n; i>=1; i--)
	{
		sum=d[i]*(1-pr[i]);
		if (sum>max) 
		{
			poz=i;
			max=sum;
		}
		if (sum>suma) mvs++;
		else mvs=0;
		suma=sum;
		if (mvs>10) break;
	}
	if (pr[poz]==x) pr[poz]=y;
	d[poz]-=max;
	p-=max;
	nr++;
}
printf ("%ld\n",nr);
return 0;
}