Pagini recente » Cod sursa (job #1011360) | Cod sursa (job #647904) | Cod sursa (job #2855023) | Cod sursa (job #2157887) | Cod sursa (job #465685)
Cod sursa(job #465685)
#include <fstream>
using namespace std;
int v[1<<17],n;
double val[1<<17],a,b;
const double dif=0.000001;
bool use[1<<17];
ifstream in("minim2.in");
ofstream out("minim2.out");
inline void sch(int &a,int &b)
{
int aux;
aux=a;
a=b;
b=aux;
}
inline bool cmp(int q,int w)
{
double x=a,y=a;
if (use[q])
x=b;
if (use[w])
y=b;
return val[q]*(1-x)<val[w]*(1-y);
}
void rec_up(int x)
{
if (x>1 && val[v[x>>1]]<val[v[x]])
{
sch(v[x>>1],v[x]);
rec_up(x>>1);
}
}
void rec_down(int x)
{
int m=x;
if (cmp(v[m],v[x<<1]) && (x<<1)<=n)
m<<=1;
if (cmp(v[m],v[(x<<1)+1]) && (x<<1)<n)
m=(x<<1)+1;
if (m!=x)
{
sch(v[m],v[x]);
rec_down(x);
}
}
int main()
{
int i,nr;
double record,s=0,t;
in>>n;
for (i=1;i<=n;i++)
{
in>>val[i];
s+=val[i];
v[i]=i;
rec_up(i);
}
in>>a>>b>>record;
s-=record;
if (s<=dif)
{
out<<"0\n";
return 0;
}
for (nr=0;s>dif;nr++)
{
t=a;
if (use[v[1]])
t=b;
s-=val[v[1]]*(1-t);
val[v[1]]*=t;
use[v[1]]=true;
rec_down(1);
}
out<<nr<<"\n";
return 0;
}