Pagini recente » Cod sursa (job #2268256) | Cod sursa (job #2314598) | Cod sursa (job #892067) | Cod sursa (job #2658370) | Cod sursa (job #479303)
Cod sursa(job #479303)
#include <cstdio>
#include <algorithm>
#include <vector>
const int maxN = 100100;
const int inf = 1000000001;
const double eps = 1e-8;
using namespace std;
double A, B, record, powerB[15], finals[maxN];
vector <double> cutts;
int N;
int X[maxN], currActions, result, stepsNumber[maxN];
inline void getStepsNumber(double T) {
int i, j, current;
double currBPower;
for (i = 1; i <= N; i++) {
if ((1 - A) * X[i] < T) {
stepsNumber[i] = 0;
finals[i] = X[i];
continue;
}
current = 0;
currBPower = 1;
for (j = 13; j >= 0; j--) {
if (X[i] * A * currBPower * powerB[j] * (1 - B) >= T - eps) {
current += (1 << j);
currBPower *= powerB[j];
}
}
stepsNumber[i] = current + 2;
finals[i] = X[i] * A * currBPower * B;
double update = X[i] * A * currBPower * (1 - B);
if (X[i] * A * (1 - B) < T + eps) {
stepsNumber[i] = 1;
finals[i] = X[i] * A;
update = X[i] * (1 - A);
}
cutts.push_back(update);
}
}
inline bool getSolution() {
double sumTimes = 0;
int sumSteps = 0;
for (int i = 1; i <= N; i++) {
sumTimes += finals[i];
sumSteps += stepsNumber[i];
}
sort(cutts.begin(), cutts.end());
for (int i = 0; i < cutts.size(); i++)
if (sumTimes + cutts[i] < record + eps) {
sumTimes += cutts[i];
sumSteps--;
}
else break;
cutts.clear();
currActions = sumSteps;
if (sumTimes <= record + eps)
return true;
return false;
}
inline void searchSmallestCut(double left, double right) {
double m;
for (int step = 1; step <= 48; step++) {
m = (left + right) / 2.0;
getStepsNumber(m);
if (getSolution()) {
result = min(result, currActions);
left = m;
}
else
right = m;
}
}
int main() {
int i, j;
freopen("minim2.in", "r", stdin);
freopen("minim2.out", "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; i++)
scanf("%d", &X[i]);
scanf("%lf%lf%lf", &A, &B, &record);
powerB[0] = B;
for (i = 1; i < 15; i++)
powerB[i] = powerB[i - 1] * powerB[i - 1];
result = inf;
searchSmallestCut(0, 1000000000);
printf("%d\n", result);
return 0;
}