Pagini recente » Cod sursa (job #1968710) | Cod sursa (job #820358) | Cod sursa (job #2385978) | Cod sursa (job #33756) | Cod sursa (job #465807)
Cod sursa(job #465807)
#include <cstdio>
#include <algorithm>
#define infile "minim2.in"
#define outfile "minim2.out"
#define tt(x) ((x)/2)
#define fs(x) (2*(x))
#define fd(x) (2*(x)+1)
#define MaxN 100024
double d[MaxN],R,S;
int N,L;
double A,B,t[MaxN],heap[MaxN];
long long sol;
void read()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
scanf("%Lf",&d[i]);
S+=d[i];
}
scanf("%Lf%Lf",&A,&B);
scanf("%Lf",&R);
}
int cmp(double x,double y)
{
return x-y>0.00001;
}
void up_heap(int nod)
{
double aux;
while(nod>1 && heap[nod]>heap[tt(nod)]+0.00001)
{
aux=heap[nod]; heap[nod]=heap[tt(nod)]; heap[tt(nod)]=aux;
aux=t[nod]; t[nod]=t[tt(nod)]; t[tt(nod)]=aux;
nod=tt(nod);
}
}
void down_heap(int nod)
{
double aux;
while((fs(nod)<=L && heap[nod]<heap[fs(nod)]+0.00001) ||
(fd(nod)<=L && heap[nod]<heap[fd(nod)]+0.00001))
{
if(fd(nod)<=L)
{
if(heap[fs(nod)]>heap[fd(nod)]-0.00001)
{
aux=heap[nod]; heap[nod]=heap[fs(nod)]; heap[fs(nod)]=aux;
aux=t[nod]; t[nod]=t[fs(nod)]; t[fs(nod)]=aux;
nod=fs(nod);
}
else
{
aux=heap[nod]; heap[nod]=heap[fd(nod)]; heap[fd(nod)]=aux;
aux=t[nod]; t[nod]=t[fd(nod)]; t[fd(nod)]=aux;
nod=fd(nod);
}
}
else
{
aux=heap[nod]; heap[nod]=heap[fs(nod)]; heap[fs(nod)]=aux;
aux=t[nod]; t[nod]=t[fs(nod)]; t[fs(nod)]=aux;
nod=fs(nod);
}
}
}
void solve()
{
int i;
for(i=1;i<=N;i++)
{
t[i]=A;
heap[++L]=d[i], up_heap(L);
}
int nod;
while(S-R>0.00001)
{
nod=1;
while(S-heap[nod]+heap[nod]*t[nod]>S-heap[fs(nod)]+heap[fs(nod)]*t[fs(nod)]+0.00001 ||
S-heap[nod]+heap[nod]*t[nod]>S-heap[fd(nod)]+heap[fd(nod)]*t[fd(nod)]+0.00001)
if(S-heap[nod]+heap[nod]*t[nod]>S-heap[fs(nod)]+heap[fs(nod)]*t[fs(nod)]+0.00001)
nod=fs(nod);
else
nod=fd(nod);
S-=heap[nod]; S+=heap[nod]*t[nod];
heap[nod]*=t[nod];
if(t[nod]==A)
t[nod]=B;
down_heap(nod);
sol++;
}
}
void write()
{
printf("%lld\n",sol);
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
read();
solve();
write();
fclose(stdin);
fclose(stdout);
return 0;
}