Cod sursa(job #1006833)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 7 octombrie 2013 20:25:08
Problema Minim2 Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <cstdio>
#include <cassert>
#include <queue>
#include <algorithm>

using namespace std;

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

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

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

        int curSteps = 1; double curVal = v[i] * A;
        for (int step = MAXlogRez - 1; step >= 0; step -= 1) {
            if (curVal * Bpower[step] * (1 - B) > limit - EPS) {
                curVal *= Bpower[step];
                curSteps += (1 << step);
            }
        }
        if (curVal * (1 - B) > limit - EPS) {
            curVal *= B;
            curSteps += 1;
        }
        steps += curSteps;
        sum += curVal;

        if (curSteps == 1) {
            lastChange.push_back(v[i] * (1 - A));
        } else {
            lastChange.push_back(curVal / B * (1 - B));
        }
    }
    sort(lastChange.begin(), lastChange.end());
    for (size_t k = 0; k < lastChange.size(); k++) {
        if (sum + lastChange[k] < goal + EPS) {
            sum += lastChange[k];
            steps -= 1;
        }
    }
    return make_pair(steps, sum);
}

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

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);

    Bpower[0] = B;
    for (int i = 1; i < MAXlogRez; i++) {
        Bpower[i] = Bpower[i - 1] * Bpower[i - 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;
}