Pagini recente » Cod sursa (job #983300) | Cod sursa (job #118137) | Cod sursa (job #1550427) | Cod sursa (job #2070761) | Cod sursa (job #500192)
Cod sursa(job #500192)
#include<stdio.h>
#include<stdlib.h>
#define NM 100001
#define eps 0.0000001
double u[NM],d[NM],w[NM];
int m;
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];}
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,n,nr=0;
int v[NM]={0};
double s=0,a,b,c,p1,p2,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);
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){
if(i<n){p1=u[i];d1=d[i];}
else d1=0;
p2=b*max();d2=max()-p2;
if(d1>0&&d1>=d2){
s-=d1;
insert(p1);
i++;
}
else{
s-=d2;
if(p2>eps){
w[1]=p2;
shift_down(1);
}
else{
clear();
}
}
nr++;
}
printf("%d",nr);
return 0;
}