Pagini recente » Cod sursa (job #364727) | Cod sursa (job #486326) | Cod sursa (job #964163) | Cod sursa (job #2942601) | Cod sursa (job #465392)
Cod sursa(job #465392)
#include <cstdio>
#include <cassert>
#include <queue>
using namespace std;
#define MAXN 100000
#define MAXV 1000000000
#define EPS 1e-6
int N; double A, B, goal;
int v[MAXN];
inline pair<int, double> getCount(double limit) {
int steps = 0; double sum = 0;
for (int i = 0; i < N; i++) {
if (limit > v[i] * (1 - A) + EPS) {
sum += v[i];
continue;
}
// TODO: binary search this
int curSteps = 1; double curVal = v[i] * A;
for (; curVal * (1 - B) > limit - EPS; ) {
curVal *= B;
curSteps += 1;
}
steps += curSteps;
sum += curVal;
}
return make_pair(steps, sum);
}
inline int isPossible(double limit) {
pair<int, double> rez = getCount(limit);
return rez.second <= goal;
}
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);
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;
}