Pagini recente » Cod sursa (job #2986112) | Cod sursa (job #2056680) | Cod sursa (job #463974) | Cod sursa (job #2004179) | Cod sursa (job #465733)
Cod sursa(job #465733)
#include<stdio.h>
#include<math.h>
#define NMAX 400010
#define eps 0.000001
//heap
using namespace std;
double sum,a[3],rec,h[NMAX];
int n,x1,x2,op,tip[NMAX],nr;
void cob(int nod)
{
int aux1,min=nod*2;
double aux;
x2=nod;
if (tip[nod*2] && tip[nod*2+1])
{
if (h[nod*2+1]*a[tip[nod*2+1]]>h[nod*2]*a[tip[nod*2]])
min=nod*2+1;
}
else if (tip[nod*2])
min=nod*2;
else if (tip[nod*2+1])
min=nod*2+1;
else min=-1;
if (h[min]*a[tip[min]]>h[nod]*a[tip[nod]])
{
aux=h[min];
h[min]=h[nod];
h[nod]=aux;
aux1=tip[min];
tip[min]=tip[nod];
tip[nod]=aux1;
cob(min);
}
}
void urc(int nod)
{
int aux1;
double aux;
x1=nod;
if (h[nod/2]*a[tip[nod/2]]<h[nod]*a[tip[nod]] && nod>1)
{
aux=h[nod/2];
h[nod/2]=h[nod];
h[nod]=aux;
aux1=tip[nod/2];
tip[nod/2]=tip[nod];
tip[nod]=aux1;
urc(nod/2);
}
}
int main()
{
int i;
double temp;
freopen("minim2.in","r",stdin);
freopen("minim2.out","w",stdout);
scanf("%d",&n);
scanf("%lf",&temp);
h[++nr]=temp;
tip[nr]=1;
sum=sum+temp;
a[1]=1;
for (i=2;i<=n;++i)
{
scanf("%lf",&temp);
h[++nr]=temp;
tip[nr]=1;
urc(nr);
cob(x1);
sum=sum+temp;
}
scanf("%lf%lf%lf",&a[1],&a[2],&rec);
a[1]=1-a[1];
a[2]=1-a[2];
while(!(fabs(sum-rec)<eps || sum<rec))
{
++op;
if (tip[1]==1)
{
sum=sum-a[1]*h[1];
tip[1]=2;
h[1]=h[1]*(1-a[1]);
cob(1);
urc(x2);
}
else
{
sum=sum-a[2]*h[1];
h[1]=h[1]*(1-a[2]);
cob(1);
urc(x2);
}
}
printf("%d",op);
return 0;
}