Pagini recente » Cod sursa (job #2971216) | Cod sursa (job #1683581) | Cod sursa (job #349221) | Cod sursa (job #1739685) | Cod sursa (job #1249722)
#include <cstdio>
#include <algorithm>
#include <vector>
const int nmax = 100100;
const int inf = 1000000001;
const double eps = 1e-8;
using namespace std;
double a, b, record, pb[15], fin[nmax];
vector <double> v;
int n, x[nmax], vact, result, stnr[nmax];
inline void STEPS(double t) {
int i, j, c;
double vbp;
for (i=1;i<=n;i++) {
if ((1-a)*x[i]<t) {
stnr[i]=0;
fin[i]=x[i];
continue;
}
c = 0;
vbp = 1;
for (j=12;j>=0;j--) {
if (x[i]* a* vbp * pb[j] * (1 - b) >= t - eps) {
c += (1 << j);
vbp *= pb[j];
}
}
stnr[i] = c + 2;
fin[i] = x[i] * a * vbp * b;
double update = x[i] * a * vbp * (1 - b);
if (x[i] * a* (1 - b) < t + eps) {
stnr[i] = 1;
fin[i] = x[i] * a;
update = x[i] * (1 - a);
}
v.push_back(update);
}
}
inline bool SOL() {
double sumTimes = 0;
int sumSteps = 0;
for (int i = 1; i <= n; i++) {
sumTimes += fin[i];
sumSteps += stnr[i];
}
sort(v.begin(), v.end());
for (int i = 0; i < v.size(); i++)
if (sumTimes + v[i] < record + eps) {
sumTimes += v[i];
sumSteps--;
}
else
break;
v.clear();
vact = sumSteps;
if (sumTimes <= 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()) {
result = min(result, vact);
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);
pb[0] = b;
for(int i=1;i<15;i++)
pb[i]=pb[i-1]*pb[i - 1];
result = inf;
SEARCH(0, 1000000000);
printf("%d\n", result);
return 0;
}