Pagini recente » Cod sursa (job #2845928) | Cod sursa (job #373373) | Cod sursa (job #1517332) | Cod sursa (job #513399) | Cod sursa (job #465819)
Cod sursa(job #465819)
#include <fstream>
using namespace std;
int v[1<<17],n;
double val[1<<17],use[1<<17],a,b;
const double dif=0.000001;
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)
{
return val[q]*(1-use[q])<val[w]*(1-use[w]);
}
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;
in>>n;
for (i=1;i<=n;i++)
{
in>>val[i];
s+=val[i];
v[i]=i;
rec_up(i);
}
in>>a>>b>>record;
for (i=1;i<=n;i++)
use[i]=a;
s-=record;
if (s<=dif)
{
out<<"0\n";
return 0;
}
for (nr=0;s>dif;nr++)
{
while(!cmp(v[1],v[2]) && s>dif)
{
s-=val[v[1]]*(1-use[v[1]]);
val[v[1]]*=use[v[1]];
use[v[1]]=b;
++nr;
}
--nr;
rec_down(1);
}
out<<nr<<"\n";
return 0;
}