Pagini recente » Borderou de evaluare (job #1567424) | Cod sursa (job #1619306) | Cod sursa (job #1457288) | Cod sursa (job #1783327) | Cod sursa (job #1991854)
#include <fstream>
using namespace std;
ifstream fin ("minim2.in"); ofstream fout ("minim2.out");
const int nmax = 1e5;
const int pmax = 1e4;
const int logpmax = 13;
const double epsmare = 1e-6;
const double epsmic = 1e-11;
int n;
double a, b, rec;
double v[nmax + 1], pb[pmax + 1];
pair <int, bool> check (double valmax) {
double sum = 0;
int cate = 0;
for (int i = 1; i <= n; ++ i) {
if (v[ i ] * (1 - a) < valmax) {
sum += v[ i ];
} else if (v[ i ] * a * (1 - b) < valmax) {
sum += v[ i ] * a;
++ cate;
} else {
double aux = v[ i ] * a * (1 - b);
++ cate;
int ans = 0;
for (int step = (1 << logpmax); step > 0; step >>= 1) {
if (ans + step <= pmax && aux * pb[ans + step] >= valmax) {
ans += step;
}
}
cate += ans;
sum += v[ i ] * a * pb[ ans ];
}
}
return make_pair(cate, sum - rec < epsmare);
}
int main() {
fin >> n;
for (int i = 1; i <= n; ++ i) fin >> v[ i ];
fin >> a >> b >> rec;
pb[ 0 ] = 1;
for (int i = 1; i <= pmax; ++ i) {
pb[ i ] = pb[i - 1] * b;
}
double st = 0, dr = 1e9;
while (dr - st > epsmic) {
double mij = (st + dr) / 2;
if (check( mij ).second) {
st = mij;
} else {
dr = mij;
}
}
fout << check( st ).first << "\n";
fin.close();
fout.close();
return 0;
}