Cod sursa(job #1006837)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 7 octombrie 2013 20:27:14
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <cstdio>
#include <algorithm>
#include <vector>

const int maxN = 100100;
const int inf = 1000000001;
const double eps = 1e-8;

using namespace std;

double A, B, record, powerB[15], finals[maxN];
vector <double> cutts;
int N;
int X[maxN], currActions, result, stepsNumber[maxN];

inline void getStepsNumber(double T) {
    int i, j, current;
    double currBPower;

    for (i = 1; i <= N; i++) {
        if ((1 - A) * X[i] < T) {
            stepsNumber[i] = 0;
            finals[i] = X[i];
            continue;
        }

        current = 0;
        currBPower = 1;

        for (j = 12; j >= 0; j--) {
            if (X[i] * A * currBPower * powerB[j] * (1 - B) >= T - eps) {
                current += (1 << j);
                currBPower *= powerB[j];
            }
        }

        stepsNumber[i] = current + 2;
        finals[i] = X[i] * A * currBPower * B;
        double update = X[i] * A * currBPower * (1 - B);

        if (X[i] * A * (1 - B) < T + eps) {
            stepsNumber[i] = 1;
            finals[i] = X[i] * A;
            update = X[i] * (1 - A);
        }

        cutts.push_back(update);

    }

}

inline bool getSolution() {
    double sumTimes = 0;
    int sumSteps = 0;

    for (int i = 1; i <= N; i++) {
        sumTimes += finals[i];
        sumSteps += stepsNumber[i];
    }

    sort(cutts.begin(), cutts.end());

    for (int i = 0; i < cutts.size(); i++)
        if (sumTimes + cutts[i] < record + eps) {
            sumTimes += cutts[i];
            sumSteps--;
        }
        else
            break;

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

inline void searchSmallestCut(double left, double right) {
    double m;

    for (int step = 1; step <= 48; step++) {
        m = (left + right) / 2.0;
        getStepsNumber(m);

        if (getSolution()) {
            result = min(result, currActions);
            left = m;
        }
        else
            right = m;
    }
}


int main() {
    int i, j;
    freopen("minim2.in", "r", stdin);
    freopen("minim2.out", "w", stdout);

    scanf("%d", &N);
    for (i = 1; i <= N; i++)
        scanf("%d", &X[i]);

    scanf("%lf%lf%lf", &A, &B, &record);

    powerB[0] = B;
    for (i = 1; i < 15; i++)
        powerB[i] = powerB[i - 1] * powerB[i - 1];

    result = inf;
    searchSmallestCut(0, 1000000000);

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

    return 0;
}