Pagini recente » Cod sursa (job #2899048) | Cod sursa (job #1758683) | Cod sursa (job #2998924) | Cod sursa (job #3039161) | Cod sursa (job #1249712)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int nmax = 100100;
const double eps = 1e-8;
int n, x[nmax], nract, rez, nrsteps[nmax];
double a, b, record, B[15], fin[nmax];
vector <double> v;
inline void STEPS(double t) {
int i, j, c;
double bp;
for (i=1;i<=n;i++) {
if ((1-a)*x[i]<t){
nrsteps[i]=0;
fin[i]=x[i];
continue;
}
c=0, bp=1;
for (j=12;j>=0;j--)
if (x[i] *a*bp*B[j]*(1-b)>=t-eps) {
c+=(1 << j);
bp*=B[j];
}
nrsteps[i] = c+2;
fin[i] = x[i]*a*bp*b;
double update=x[i]*a *bp*(1-b);
if(x[i]*a*(1-b)<t+eps){
nrsteps[i] = 1;
fin[i]=x[i]*a;
update=x[i]*(1-a);
}
v.push_back(update);
}
}
inline bool SOL() {
double stimes=0;
int ssteps=0;
for (int i=1;i<=n;i++) {
stimes+=fin[i];
ssteps+=nrsteps[i];
}
sort(v.begin(), v.end());
for (int i=0;i<(int)v.size();i++)
if (stimes+v[i]<record+eps) {
stimes+=v[i];
ssteps--;
}
else break;
v.clear();
nract=ssteps;
if (stimes<=record+eps) return true;
return false;
}
inline void SEARCH(double left, double right) {
double m;
for (int step=1;step<=48;step++) {
m=(left+right)/2.0;
STEPS(m);
if(SOL()){
rez=min(rez,nract);
left=m;
}
else right=m;
}
}
int main() {
freopen("minim2.in", "r", stdin);
freopen("minim2.out", "w", stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&x[i]);
scanf("%lf%lf%lf",&a,&b,&record);
B[0]=b;
for (int i=1;i<15;i++)
B[i]=B[i - 1]*B[i - 1];
rez=1000000001;
SEARCH(0,1000000000);
printf("%d\n", rez);
return 0;
}