Pagini recente » Cod sursa (job #1311559) | Cod sursa (job #2271212) | Cod sursa (job #182370) | Cod sursa (job #1170245) | Cod sursa (job #1759014)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
//ifstream cin("tema.in");
//ofstream cout("tema.out");
const int MAXN = 100000;
const int MAXP = 13;
const double EPS = 1e-6;
const int INF = 1000000000;
double v[1 + MAXN];
double power[MAXP];
int n, current;
double a, b, limit;
vector<double> temp;
double Reduce(double x, double value) {
if (x * (1 - a) < value)
return x;
if (x * a * (1 - b) < value) {
current++;
temp.push_back(x * (1 - a));
return x * a;
}
x *= a;
current += 2;
for (int i = MAXP - 1; i >= 0; i--)
if (x * power[i] * (1 - b) >= value) {
current += (1 << i);
x *= power[i];
}
temp.push_back(x * (1 - b));
return x * b;
}
bool Check(double value) {
temp.clear();
double sum = 0;
current = 0;
for (int i = 1; i <= n; i++)
sum += Reduce(v[i], value);
sort(temp.begin(), temp.end());
for (auto &it : temp)
if (sum + it < limit + EPS) {
current--;
sum += it;
}
else
break;
if (sum < limit + EPS)
return true;
return false;
}
int BinarySearch() {
double left = 0, right = INF;
int answer = INF;
for (int step = 1; step <= 48; step++) {
double middle = (left + right) / 2;
if (Check(middle)) {
answer = min(answer, current);
left = middle;
}
else
right = middle;
}
return answer;
}
int main() {
freopen("minim2.in", "r", stdin);
freopen("minim2.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lf", &v[i]);
scanf("%lf%lf%lf", &a, &b, &limit);
power[0] = b;
for (int i = 1; i < MAXP; i++)
power[i] = power[i - 1] * power[i - 1];
printf("%d\n", BinarySearch());
return 0;
}