Pagini recente » Cod sursa (job #3250458) | Cod sursa (job #514997) | Cod sursa (job #2403061) | Cod sursa (job #2171155) | Cod sursa (job #465688)
Cod sursa(job #465688)
#include <fstream>
using namespace std;
const char InFile[]="minim2.in";
const char OutFile[]="minim2.out";
const int MaxN=100010;
const double EPS=1e-6;
struct s2d{double l,c;};
ifstream fin(InFile);
ofstream fout(OutFile);
double R,x,S,A,B;
s2d heap[MaxN];
int T,N;
inline double h(int nod)
{
return heap[nod].l-heap[nod].c;
}
inline double dabs(double a)
{
if(a>0)return a;
return -a;
}
inline int r(int a)
{
return a<<1;
}
inline int l(int a)
{
return (a<<1)+1;
}
inline int f(int a)
{
return a>>1;
}
void up_heap(int nod)
{
if(nod<2 || nod>N)return;
if(h(nod)>h(f(nod)))
{
double aux=heap[nod].l;
heap[nod].l=heap[f(nod)].l;
heap[f(nod)].l=aux;
aux=heap[nod].c;
heap[nod].c=heap[f(nod)].c;
heap[f(nod)].c=aux;
up_heap(f(nod));
}
}
void down_heap(int nod)
{
if(nod<1 || nod>N)return;
int i=nod;
int t=r(nod);
if(t<=N)
{
if(h(t)>h(i))
{
i=t;
}
}
t=l(nod);
if(t<=N)
{
if(h(t)>h(i))
{
i=t;
}
}
if(i!=nod)
{
s2d aux=heap[i];
heap[i]=heap[nod];
heap[nod]=aux;
down_heap(i);
}
}
void add_heap(double l,double c)
{
++heap[0].c;
heap[(int)(heap[0].c)].l=l;
heap[(int)(heap[0].c)].c=c;
}
int main()
{
heap[0].c=0;
fin>>N;
for(register int i=0;i<N;++i)
{
fin>>x;
add_heap(x,x);
S+=x;
}
fin>>A>>B>>R;
for(register int i=1;i<=N;++i)
{
heap[i].c*=A;
}
for(register int i=1;i<=N/2;++i)
{
down_heap(i);
}
fin.close();
T=0;
while(dabs(R-S)>=EPS && S>=R)
{
++T;
S-=h(1);
heap[1].l=heap[1].c;
heap[1].c*=B;
down_heap(1);
}
fout<<T;
fout.close();
return 0;
}