Pagini recente » Cod sursa (job #2006942) | Cod sursa (job #1574011) | Cod sursa (job #1730926) | Cod sursa (job #705591) | Cod sursa (job #465918)
Cod sursa(job #465918)
#include<stdio.h>
#define dd double
#define eps 0.0000001
int k,n,v[100009],sol;
dd s,a,b,rec;
struct comb
{
double x,z;
int y;
};
comb heap[250006];
int cmp(double a,double b)
{
if(a+eps>b)
return 1;
return 0;
}
void perc(int nod)
{
int r1=cmp(heap[nod].z,heap[2*nod].z);
int r2=cmp(heap[nod].z,heap[2*nod+1].z);
int r3=cmp(heap[2*nod].z,heap[2*nod+1].z);
if(r1 && r2)
return ;
comb aux;
if(r3)
{
aux=heap[nod];
heap[nod]=heap[2*nod];
heap[2*nod]=aux;
perc(2*nod);
return ;
}
aux=heap[nod];
heap[nod]=heap[2*nod+1];
heap[2*nod+1]=aux;
perc(2*nod+1);
}
void sift(int nod)
{
if(nod==1)
return ;
if(cmp(heap[nod].z,heap[nod/2].z))
{
comb aux;
aux=heap[nod];
heap[nod]=heap[nod/2];
heap[nod/2]=aux;
sift(nod/2);
}
}
void add(double val)
{
heap[++k].x=val;
heap[k].z=val*(1-a);
sift(k);
}
int main ()
{
int i;
dd val;
freopen("minim2.in","r",stdin);
freopen("minim2.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&v[i]);
s+=v[i];
}
scanf("%lf%lf%lf",&a,&b,&rec);
for(i=1;i<=n;i++)
{
val=v[i];
add(val);
}
while(cmp(s,rec))
{
s-=heap[1].x;
if(!heap[1].y)
{
heap[1].x*=a;
heap[1].y=1;
}
else
heap[1].x*=b;
s+=heap[1].x;
heap[1].z=heap[1].x*(1-b);
perc(1);
sol++;
if(sol>200006)
{
printf("500000000\n");
return 0;
}
}
printf("%d\n",sol);
return 0;
}