Cod sursa(job #1249722)

Utilizator tudormaximTudor Maxim tudormaxim Data 27 octombrie 2014 13:08:30
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <cstdio>
#include <algorithm>
#include <vector>
const int nmax = 100100;
const int inf = 1000000001;
const double eps = 1e-8;
using namespace std;
double a, b, record, pb[15], fin[nmax];
vector <double> v;
int n, x[nmax], vact, result, stnr[nmax];
inline void STEPS(double t) {
    int i, j, c;
    double vbp;
    for (i=1;i<=n;i++) {
        if ((1-a)*x[i]<t) {
            stnr[i]=0;
            fin[i]=x[i];
            continue;
        }
        c = 0;
        vbp = 1;
        for (j=12;j>=0;j--) {
            if (x[i]* a* vbp * pb[j] * (1 - b) >= t - eps) {
                c += (1 << j);
                vbp *= pb[j];
            }
        }
        stnr[i] = c + 2;
        fin[i] = x[i] * a * vbp * b;
        double update = x[i] * a * vbp * (1 - b);

        if (x[i] * a* (1 - b) < t + eps) {
            stnr[i] = 1;
            fin[i] = x[i] * a;
            update = x[i] * (1 - a);
        }
        v.push_back(update);
    }
}
inline bool SOL() {
    double sumTimes = 0;
    int sumSteps = 0;

    for (int i = 1; i <= n; i++) {
        sumTimes += fin[i];
        sumSteps += stnr[i];
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++)
        if (sumTimes + v[i] < record + eps) {
            sumTimes += v[i];
            sumSteps--;
        }
        else
            break;

    v.clear();
    vact = sumSteps;
    if (sumTimes <= record + eps)
        return true;
    return false;
}

inline void SEARCH(double left, double right) {
    double m;
    for (int step = 1; step <= 48; step++) {
        m = (left + right) / 2.0;
        STEPS(m);
        if (SOL()) {
            result = min(result, vact);
            left = m;
        }
        else right = m;
    }
}

int main() {
    freopen("minim2.in", "r", stdin);
    freopen("minim2.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
        scanf("%d",&x[i]);
    scanf("%lf%lf%lf", &a, &b, &record);
    pb[0] = b;
    for(int i=1;i<15;i++)
        pb[i]=pb[i-1]*pb[i - 1];
    result = inf;
    SEARCH(0, 1000000000);
    printf("%d\n", result);
    return 0;
}