Pagini recente » Cod sursa (job #2670017) | Cod sursa (job #259487) | Cod sursa (job #2448593) | Cod sursa (job #2592931) | Cod sursa (job #757850)
Cod sursa(job #757850)
#include <cmath>
#include <fstream>
#include <algorithm>
using namespace std;
const double eps = 0.000001;
int N;
double V[100002], powB[10002], S;
double A, B, R;
vector<double> rem;
int done(double x)
{
double sum = S;
int resnow = 0;
rem.clear();
for (int i = 1; i <= N; ++i)
{
double U = V[i];
if (U * (1 - A) >= x)
{
sum -= U * (1 - A);
U *= A;
++resnow;
int step = 1 << 13, times = -1;
for (; step; step >>= 1)
if (times + step <= 10000 && U * powB[times + step] * (1 - B) >= x)
times += step;
++times;
if (times != 0)
rem.push_back(U * powB[times - 1] * (1 - B)); // cat se sterge ultima data
sum -= U - U * powB[times];
U *= powB[times];
resnow += times;
}
}
for (size_t i = 0; i < rem.size(); ++i)
if (sum + rem[i] - R <= eps)
{
sum += rem[i];
--resnow;
}
if (sum - R <= eps) return resnow;
return 0;
}
int main()
{
ifstream fin("minim2.in");
ofstream fout("minim2.out");
fin >> N;
for (int i = 1; i <= N; ++i)
{
fin >> V[i];
S += V[i];
}
fin >> A >> B >> R;
powB[0] = 1;
for (int i = 1; i <= 10001; ++i)
powB[i] = powB[i - 1] * B;
if (S - R <= eps)
{
fout << 0 << '\n';
fin.close();
fout.close();
return 0;
}
double l1 = 0, l2 = 1000000000;
while (l2 - l1 > eps)
{
double mid = (l1 + l2) / 2;
if (done(mid)) l1 = mid;
else l2 = mid;
}
fout << done(l1) << '\n';
fin.close();
fout.close();
}