Cod sursa(job #465392)

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

using namespace std;

#define MAXN 100000
#define MAXV 1000000000
#define EPS 1e-6

int N; double A, B, goal;
int v[MAXN];

inline pair<int, double> getCount(double limit) {
    int steps = 0; double sum = 0;
    for (int i = 0; i < N; i++) {
        if (limit > v[i] * (1 - A) + EPS) {
            sum += v[i];
            continue;
        }

        // TODO: binary search this
        int curSteps = 1; double curVal = v[i] * A;
        for (; curVal * (1 - B) > limit - EPS; ) {
            curVal *= B;
            curSteps += 1;
        }
        steps += curSteps;
        sum += curVal;
    }
    return make_pair(steps, sum);
}

inline int isPossible(double limit) {
    pair<int, double> rez = getCount(limit);
    return rez.second <= goal;
}

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

    scanf("%d", &N);
    assert(1 <= N && N <= MAXN);
    for (int i = 0; i < N; i++) {
        scanf("%d", v + i);
        assert(1 <= v[i] && v[i] <= MAXV);
    }
    scanf("%lf %lf %lf", &A, &B, &goal);
    assert(0 <= A && A <= B && B <= 1);

    double l = 0, r = MAXV;
    for (; r - l > EPS; ) {
        double m = (l + r) * 0.5;
        if (!isPossible(m)) {
            r = m;
        } else {
            l = m;
        }
    }

    pair<int, double> rez = getCount(l);
    printf("%d\n", rez.first);

    return 0;
}