Cod sursa(job #501021)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 14 noiembrie 2010 08:22:11
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<stdio.h>
#include<stdlib.h>
#define NM 100001
#define eps 0.000001


int fcmp(const void*x, const void *y){
return *((int*)y)-*((int*)x);
}

int main(){
freopen("minim2.in","r",stdin);
freopen("minim2.out","w",stdout);
int i,j,k,n,nr=0;
int v[NM]={0};
double s=0,ss=0,a,b,c,w[NM]={0},d[NM]={0},t,td;
scanf("%d",&n);
for(i=0;i<n;++i) scanf("%d",&v[i]),s+=v[i];
scanf("%lf%lf%lf",&a,&b,&c);
qsort(v,n,sizeof(v[0]),fcmp);
for(i=0;i<n;++i){
	w[i+1]=v[i]*a;
	d[i+1]=v[i]-w[i+1];
	}
s-=c-eps;
i=1;
while(ss<s&&i<=n){
	if(d[i]>=d[1]){
		ss+=d[i];
		nr++;
		d[i]=w[i]*(1-b);
		w[i]*=b;
		i++;
		}
	else{
		ss+=d[1];
		nr++;
		d[1]=(1-b)*w[1];
		w[1]*=b;
		j=2;
		t=w[1],td=d[1];
		if(j<i){
			while(td<d[j]&&j<i-1){
				w[j-1]=w[j];
				d[j-1]=d[j];
				j++;
				}
			w[j]=t;
			d[j]=td;
			}
		}
	}
printf("%d",nr);
return 0;
}