Cod sursa(job #498860)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 7 noiembrie 2010 15:15:14
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<stdio.h>
#include<stdlib.h>
#define NM 100001
#define eps 0.0000001


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,m,nr=0;
int v[NM]={0};
double s=0,a,b,c,w[NM]={0},p1,p2,t,d1,d2;
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);
i=j=0;nr++;m=1;
w[++j]=v[i]*a;s-=v[i]-w[j];i++;
while(s>c+eps){
	p1=a*v[i];p2=b*w[m];
	d1=v[i]-p1;d2=w[m]-p2;
	if(d1>=d2){
		s-=v[i]-p1;
		w[++m]=p1;
		i++;
		}
	else{
		s-=w[m]-p2;
		w[m]=p2;
		}
	j=m;t=w[m];
	while(j&&w[j]<w[j-1]) w[j]=w[j-1],j--;
	w[j]=t;
	nr++;
	}
printf("%d",nr);
return 0;
}