Pagini recente » Cod sursa (job #1571448) | Cod sursa (job #1845705) | Cod sursa (job #1297421) | Cod sursa (job #2111679) | Cod sursa (job #2005805)
#include <bits/stdc++.h>
#define maxN 100002
using namespace std;
FILE *fin = freopen("minim2.in", "r", stdin);
FILE *fout = freopen("minim2.out", "w", stdout);
/* --------------------------------- */
int n, v[maxN];
double a, b, rsum;
/* --------------------------------- */
double sum, Pow[maxN];
struct Nod
{
bool ty;
double x, dif;
bool operator < (const Nod &ot) const
{
return dif < ot.dif;
}
};
priority_queue < Nod > H;
/* --------------------------------- */
int ans;
void compPow()
{
Pow[0] = 1.0;
for (int i = 1; i < maxN; ++ i)
Pow[i] = Pow[i - 1] * b;
}
/* --------------------------------- */
int bs(Nod nod, double bstDif)
{
int i = 0, p = 1 << 17;
while (p)
{
if (i + p < maxN)
{
double lastDif = (nod.x * Pow[i + p - 1] - nod.x * Pow[i + p]), sub = (1.0 - Pow[i + p - 1]) * nod.x;
if (lastDif >= bstDif && sub < (sum - rsum))
i += p;
}
p >>= 1;
}
return i;
}
void getAns()
{
while (fabs(sum / rsum) > 1.0)
{
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;
}
int nrop = bs(bst, sec.dif);
sum -= bst.x;
ans += nrop;
bst.x *= Pow[nrop];
sum += bst.x;
H.push({bst.ty, bst.x, bst.x * (1.0 - b)});
}
}
/* --------------------------------- */
void spCase()
{
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("%d", &v[i]);
sum += (double)v[i];
}
scanf("%lf%lf%lf", &a, &b, &rsum);
for (int i = 1; i <= n; ++ i)
H.push({0, (double)v[i], (1.0 - a) * v[i]});
compPow();
if (n == 1)
spCase();
else
getAns();
printf("%d\n", ans);
return 0;
}