Pagini recente » Cod sursa (job #2339660) | Cod sursa (job #63853) | Cod sursa (job #2071033) | Cod sursa (job #1539054) | Cod sursa (job #846538)
Cod sursa(job #846538)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 100010
#define maxp 13
#define eps 0.000001
int n, i, j, k, sol, csol;
double v[maxn], bpt[maxp];
double a, b, r, sum;
vector<double> t;
double reduce(double x, double value)
{
if(x*(1-a)<value)
return x;
if(x*a*(1-b)<value)
{
++csol;
t.push_back(x*(1-a));
return x*a;
}
x=x*a;
csol+=2;
for(int i=maxp-1; i>=0; --i)
if(x*bpt[i]*(1-b)>=value)
{
csol+=(1<<i);
x*=bpt[i];
}
t.push_back(x*(1-b));
return x*b;
}
int check(double value)
{
double csum=0;
t.clear();
csol=0;
for(int i=1; i<=n; ++i)
csum+=reduce(v[i], value);
sort(t.begin(), t.end());
for(int i=0; i<t.size(); ++i)
if(csum+t[i]<r+eps)
{
--csol;
csum+=t[i];
}
else
break;
if(csum<r+eps)
return 1;
return 0;
}
int main()
{
freopen("minim2.in", "r", stdin);
freopen("minim2.out", "w", stdout);
scanf("%d", &n);
for(int i=1; i<=n; ++i)
scanf("%lf", &v[i]);
scanf("%lf%lf%lf", &a, &b, &r);
bpt[0]=b;
for(int i=1; i<maxp; ++i)
bpt[i]=bpt[i-1]*bpt[i-1];
double left=0, med, right=1000000000;
sol=1000000000;
for(int i=1; i<=48; ++i)
{
med=(left+right)/2;
if(check(med))
{
sol=min(csol, sol);
left=med;
}
else
right=med;
}
printf("%d\n", sol);
return 0;
}