Cod sursa(job #465391)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 24 iunie 2010 01:34:39
Problema Minim2 Scor Ascuns
Compilator cpp Status done
Runda Marime 1.02 kb
#include <cstdio>
#include <cassert>
#include <queue>

using namespace std;

#define MAXN 100005

int N; double A, B, goal, sum;
int v[MAXN];
priority_queue<pair<double, int> > H;

int main() {
    freopen("minim2.in", "rt", stdin);
#ifndef DEBUG
    freopen("minim2.out", "wt", stdout);
#endif

    scanf("%d", &N);
    assert(1 <= N && N <= 100000);
    for (int i = 0; i < N; i++) {
        scanf("%d", v + i);
    }
    scanf("%lf %lf %lf", &A, &B, &goal);
    sum = 0;
    for (int i = 0; i < N; i++) {
        H.push(make_pair(v[i] * (1 - A), 0));
        sum += v[i];
    }

    int steps = 0;
    for (; sum > goal; ) {
        double val = H.top().first; int type = H.top().second;
        H.pop();
        if (type == 0) {
            val /= (1 - A);
            sum -= val;
            val *= A;
        } else {
            val /= (1 - B);
            sum -= val;
            val *= B;
        }
        sum += val;
        H.push(make_pair(val * (1 - B), 1));
        steps += 1;
    }

    printf("%d\n", steps);

    return 0;
}