Cod sursa(job #500761)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 12 noiembrie 2010 23:41:29
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include<stdio.h>
#include<stdlib.h>
#define NM 100001
#define eps 0.000001

double u[NM],d[NM],w[NM];
int m;
char sir[10*NM+1],*ps=sir;
inline int tata(int k){return k/2;}
inline int fiu_st(int k){return 2*k;}
inline int fiu_dr(int k){return 2*k+1;}
inline double max(){return w[1];}
inline double cmm(double X,double Y){
if(X>Y) return X;
return Y;
}

void shift_down(int k){
int fiu;
double aux;
do{
	fiu=0;
	if(fiu_st(k)<=m) fiu=fiu_st(k);
	if(fiu_dr(k)<=m&&w[fiu_dr(k)]>w[fiu])
		fiu=fiu_dr(k);
	if(w[fiu]<=w[k]) fiu=0;
	if(fiu){aux=w[fiu];w[fiu]=w[k];w[k]=aux;k=fiu;}
}while(fiu);
}

void shift_up(int k){
double x=w[k];
while(k>1&&w[tata(k)]<x){
	w[k]=w[tata(k)];
	k=tata(k);
	}
w[k]=x;
}

void insert(double x){
m++;w[m]=x;
shift_up(m);
}

void clear(){
w[1]=w[m--];
shift_down(1);
}

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,n,v[NM]={0},nr=0;
double s=0,a,b,c,p1,p2,d1,d2,
	pb[20]={1},dpb[20]={1},dif;
scanf("%d\n",&n);
fgets(sir,10*NM,stdin);
for(i=0;i<n;++i){
	v[i]=atoi(ps);
	s+=v[i];
	while(*ps!=32) ps++;
	ps++;
	}
scanf("%lf%lf%lf",&a,&b,&c);
pb[0]=b;dpb[0]=1-b;
for(i=1;i<=13;i++){
	pb[i]=pb[i-1]*pb[i-1];
	dpb[i]=dpb[i-1]*dpb[i-1];
	}
c+=eps;
qsort(v,n,sizeof(v[0]),fcmp);
for(i=0;i<n;++i){
	d[i]=(1-a)*v[i];
	u[i]=a*v[i];
	}
i=0;nr++;insert(u[i]);
s-=d[i];i++;
while(s>c){
	p2=b*max();d2=max()-p2;
	if(i<n){p1=u[i];d1=d[i];}
	else d1=0;
	if(d1>=d2){
		s-=d1;
		insert(p1);;
		i++;
		nr++;
		}
	else{
		if(d1) dif=d1;
		else dif=(1-b)*cmm(w[2],w[3]);
		j=0;
		if(dif>d2){
			while(j<13&&w[1]*dpb[j+1]<dif) j++;
			p2=pb[j]*w[1];
			d2=w[1]-p2;
			}
		s-=d2;
		w[1]=p2;
		shift_down(1);
		nr+=1<<j;
		}
	}
printf("%d",nr);
return 0;
}