Pagini recente » Cod sursa (job #2841229) | Cod sursa (job #2002765) | Cod sursa (job #854750) | Cod sursa (job #158170) | Cod sursa (job #552605)
Cod sursa(job #552605)
#include <cstdio>
#include <cassert>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 100000
#define MAXV 1000000000
#define MAXlogRez 13
#define EPS 1e-6
int N; double A, B, goal;
double Bpower[MAXlogRez];
int v[MAXN];
inline pair<int, double> getCount(double limit) {
int steps = 0; double sum = 0;
vector<double> lastChange;
for (int i = 0; i < N; i++) {
if (limit > v[i] * (1 - A) + EPS) {
sum += v[i];
continue;
}
int curSteps = 1; double curVal = v[i] * A;
for (int step = MAXlogRez - 1; step >= 0; step -= 1) {
if (curVal * Bpower[step] * (1 - B) > limit - EPS) {
curVal *= Bpower[step];
curSteps += (1 << step);
}
}
if (curVal * (1 - B) > limit - EPS) {
curVal *= B;
curSteps += 1;
}
steps += curSteps;
sum += curVal;
if (curSteps == 1) {
lastChange.push_back(v[i] * (1 - A));
} else {
lastChange.push_back(curVal / B * (1 - B));
}
}
sort(lastChange.begin(), lastChange.end());
for (size_t k = 0; k < lastChange.size(); k++) {
if (sum + lastChange[k] < goal + EPS) {
sum += lastChange[k];
steps -= 1;
}
}
return make_pair(steps, sum);
}
inline int isPossible(double limit) {
pair<int, double> rez = getCount(limit);
return rez.second < goal + EPS;
}
int main() {
freopen("minim2.in", "rt", stdin);
#ifndef DEBUG
freopen("minim2.out", "wt", stdout);
#endif
scanf("%d", &N);
assert(1 <= N && N <= MAXN);
for (int i = 0; i < N; i++) {
scanf("%d", v + i);
assert(1 <= v[i] && v[i] <= MAXV);
}
scanf("%lf %lf %lf", &A, &B, &goal);
assert(0 <= A && A <= B && B <= 1);
Bpower[0] = B;
for (int i = 1; i < MAXlogRez; i++) {
Bpower[i] = Bpower[i - 1] * Bpower[i - 1];
}
double l = 0, r = MAXV;
for (; r - l > EPS; ) {
double m = (l + r) * 0.5;
if (!isPossible(m)) {
r = m;
} else {
l = m;
}
}
pair<int, double> rez = getCount(l);
printf("%d\n", rez.first);
return 0;
}