Pagini recente » Cod sursa (job #3289402) | Cod sursa (job #687993) | Cod sursa (job #498642) | Simulare 11 | Cod sursa (job #635176)
Cod sursa(job #635176)
#include <cstdio>
#include <cassert>
#include <queue>
#include <algorithm>
using namespace std;
#define NMAX 100001
#define LgMax 13
#define VMAX 1000000000
#define EPS (1e-6)
int N; double A, B, goal;
int v[NMAX];
double powB[LgMax];
inline pair<int, double> getCount(double limit)
{
int steps = 0;
double sum = 0.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 = LgMax - 1; step >= 0; --step) {
if (v[i] * powB[step] * (1 - B) > limit - EPS) {
curVal *= powB[step];
curSteps += (1<<step);
}
}
if (curVal * (1 - B) > limit - EPS) {
curVal *= B;
++curSteps;
}
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;
}
}
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", "r", stdin);
freopen("minim2.out", "w", stdout);
scanf("%d", &N);
for (int i = 0; i < N; ++i) {
scanf("%d", &v[i]);
}
scanf("%lf %lf %lf", &A, &B, &goal);
powB[0] = B;
for (int i = 1; i < LgMax; ++i) {
powB[i] = powB[i-1] * powB[i-1];
}
double l = 0, r = VMAX;
while (r - l > EPS) {
double m = (l + r) * 0.5;
if (!isPossible(m))
r = m;
else
l = m;
}
pair<int, double> res = getCount(l);
printf("%d\n", res.first);
return 0;
}