Pagini recente » Cod sursa (job #2901603) | Cod sursa (job #254707) | Cod sursa (job #2931978) | Cod sursa (job #2346205) | Cod sursa (job #465686)
Cod sursa(job #465686)
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define FIN "minim2.in"
#define FOUT "minim2.out"
#define MAXN 100002
#define DIF 0.000001
int N, Nr, X;
double R, A, B, D[MAXN];
priority_queue < pair <double, char> > H;
void solve()
{
int i;
pair <double, char> p;
X = N;
R = -R;
for (i = 1; i <= N; ++ i)
R += D[i];
for (i = 1; i <= N; ++ i)
H.push(make_pair(D[i] * (1 - A), 1));
while (X)
{
++ Nr;
R -= H.top().first;
p = H.top();
if (p.second == 1)
{
-- X;
p.first = p.first / (1 - A) * A;
}
else
p.first = p.first / (1 - B) * B;
H.pop();
H.push(make_pair(p.first * (1 - B), 0));
if (R < DIF) return;
}
for (i = N, D[0] = 1; i; -- i)
D[i] = H.top().first / (1 - B), H.pop(), D[N + 1] += D[i];
while (1)
{
if (R >= D[N + 1] * B + DIF)
{
Nr += N;
R -= D[N + 1];
D[N + 1] *= B;
D[0] *= B;
}
else
for (i = N, D[0] *= B; i && R >= DIF; -- i)
{
R -= D[i] * (double)(1 - D[0]);
++ Nr;
}
if (R < DIF) return;
}
}
int main()
{
int i;
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; ++ i)
scanf("%lf", &D[i]);
scanf("%lf %lf %lf", &A, &B, &R);
solve();
printf("%d\n", Nr);
}