Pagini recente » Cod sursa (job #965780) | Cod sursa (job #553417) | Cod sursa (job #707036) | Cod sursa (job #1140994) | Cod sursa (job #2005820)
#include <bits/stdc++.h>
#define maxN 100002
#define maxM 10002
using namespace std;
FILE *fin = freopen("minim2.in", "r", stdin);
FILE *fout = freopen("minim2.out", "w", stdout);
/* --------------------------------- */
int n;
double v[maxN], a, b, rsum;
/* --------------------------------- */
double sum;
struct Nod
{
bool ty;
double x, dif;
inline bool operator < (const Nod &ot) const
{
if (dif == ot.dif)
return x < ot.x;
return dif < ot.dif;
}
};
priority_queue < Nod > H;
/* --------------------------------- */
int ans;
double Pow(int x)
{
if (x == 0)
return 1;
if (x == 1)
return b;
if (x & 1)
return b * Pow(x / 2);
return Pow(x / 2) * Pow(x / 2);
}
/* --------------------------------- */
int bs(Nod nod, double bstDif)
{
int i = 0, p = 1 << 13;
while (p)
{
if (i + p < maxM)
{
double P = Pow(i + p - 1);
double lastDif = (nod.x * P - nod.x * P * b), sub = (1.0 - P) * nod.x;
if (lastDif >= bstDif && sub < (sum - rsum))
i += p;
}
p >>= 1;
}
return i;
}
void getAns()
{
while (sum > rsum && ans < 200)
{
Nod bst = H.top(), sec;
H.pop();
sec = H.top();
if (bst.ty == 0)
{
sum -= bst.dif;
++ ans;
bst.ty = 1;
bst.x *= a;
bst.dif = (1.0 - b) * bst.x;
}
sum -= bst.x;
int nrop = bs(bst, sec.dif);
ans += nrop;
bst.x *= Pow(nrop);
sum += bst.x;
H.push({bst.ty, bst.x, bst.x * (1.0 - b)});
}
}
/* --------------------------------- */
void spCase()
{
return;
if (sum <= rsum)
return ;
ans = 1;
sum *= a;
while (sum > rsum)
{
sum *= b;
++ ans;
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
{
scanf("%lf", &v[i]);
sum += v[i];
}
scanf("%lf%lf%lf", &a, &b, &rsum);
for (int i = 1; i <= n; ++ i)
H.push({0, v[i], (1.0 - a) * v[i]});
//compPow();
if (n == 1)
spCase();
else
getAns();
printf("%d\n", ans);
return 0;
}