Pagini recente » Cod sursa (job #2872714) | Cod sursa (job #750634) | Cod sursa (job #1785397) | Cod sursa (job #2422928) | Cod sursa (job #2104119)
#include<fstream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
ifstream fi("minim2.in");
ofstream fo("minim2.out");
int n,i,A[100001],rez;
double lgb,x,a,b,r,P[10001];
long double sum;
vector<double> V;
bool check(double val)
{
rez=0;
sum=0.0;
double upd=0.0;
V.clear();
for(int i=1; i<=n; i++)
{
double nr=A[i];
upd=0.0;
if((1-a)*nr>=val)
{
upd=nr*(1-a);
nr*=a;
rez++;
}
if((1-b)*nr>=val)
{
double aux=nr*(1-b);
int p=(int)(log(val/aux)/lgb)+1; //in loc de formula se poate face tinand un sir P[i]=b^(2^i)
nr=nr*P[p];
if(aux*P[p+1]>=val)
{
p++;
nr=nr*b;
}
upd=A[i]*a*(1-b)*P[p];
rez+=p;
}
sum+=nr;
if(upd!=0)
V.push_back(upd);
}
return (sum-r<1e-6);
}
double bs(double st, double dr)
{
double mij=0;
while(dr-st>(1e-6))
{
mij=(st+dr)/2;
if(check(mij))
st=mij;
else
dr=mij;
}
return st;
}
int main()
{
fi>>n;
for(i=1; i<=n; i++)
fi>>A[i];
fi>>a>>b>>r;
lgb=log(b);
P[0]=1;
for(i=1; i<=10000; i++)
P[i]=P[i-1]*b;
x=bs(0,1000000000);
check(x);
sort(V.begin(),V.end());
for(i=0; i<V.size(); i++)
{
if(sum+V[i]<r+(1e-6))
{
rez--;
sum+=V[i];
}
else
break;
}
fo<<rez<<"\n";
fi.close();
fo.close();
return 0;
}