Pagini recente » Cod sursa (job #2772464) | Cod sursa (job #922152) | Cod sursa (job #994483) | Cod sursa (job #3031320) | Cod sursa (job #500761)
Cod sursa(job #500761)
#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;
}