Cod sursa(job #465777)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 25 iunie 2010 13:07:17
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 1 Marime 1.65 kb
#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 = 1, D[0] = 1; i <= N; ++ 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 = 1, D[0] *= B; i <= N && 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);
}