Cod sursa(job #465393)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 24 iunie 2010 02:12:51
Problema Minim2 Scor Ascuns
Compilator cpp Status done
Runda Marime 1.5 kb
#include <cstdio>
#include <cmath>
#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;
        }

        int curSteps = 0, step = 1 << 15;
        for (; step; step >>= 1) {
            double val = v[i] * A * (1 - B) * pow(B, curSteps + step);
            if (val > limit - EPS) {
                curSteps += step;
            }
        }
        steps += curSteps + 1;
        sum += v[i] * A * pow(B, curSteps);
    }
    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;
}