Pagini recente » Cod sursa (job #1079386) | Cod sursa (job #3190254) | Cod sursa (job #725375) | Cod sursa (job #1192004) | Cod sursa (job #465977)
Cod sursa(job #465977)
#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]>h[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 (min!=-1 && h[min]>h[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]<h[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];
for (i=1;i<=n;++i)
h[i]=h[i]*a[1];
while(!(fabs(sum-rec)<eps || sum<rec))
{
++op;
if (tip[1]==1)
{
sum=sum-h[1];
tip[1]=2;
h[1]=h[1]/a[1]*a[2]*(1-a[1]);
cob(1);
urc(x2);
}
else
{
sum=sum-h[1];
h[1]=h[1]*(1-a[2]);
cob(1);
urc(x2);
}
}
printf("%d",op);
return 0;
}