Cod sursa(job #1991854)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 18 iunie 2017 15:40:31
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>

using namespace std;

ifstream fin ("minim2.in"); ofstream fout ("minim2.out");

const int nmax = 1e5;
const int pmax = 1e4;
const int logpmax = 13;
const double epsmare = 1e-6;
const double epsmic = 1e-11;

int n;
double a, b, rec;
double v[nmax + 1], pb[pmax + 1];

pair <int, bool> check (double valmax) {
    double sum = 0;
    int cate = 0;
    for (int i = 1; i <= n; ++ i) {
        if (v[ i ] * (1 - a) < valmax) {
            sum += v[ i ];
        } else if (v[ i ] * a * (1 - b) < valmax) {
            sum += v[ i ] * a;
            ++ cate;
        } else {
            double aux = v[ i ] * a * (1 - b);
            ++ cate;

            int ans = 0;
            for (int step = (1 << logpmax); step > 0; step >>= 1) {
                if (ans + step <= pmax && aux * pb[ans + step] >= valmax) {
                    ans += step;
                }
            }

            cate += ans;
            sum += v[ i ] * a * pb[ ans ];
        }
    }

    return make_pair(cate, sum - rec < epsmare);
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; ++ i) fin >> v[ i ];
    fin >> a >> b >> rec;

    pb[ 0 ] = 1;
    for (int i = 1; i <= pmax; ++ i) {
        pb[ i ] = pb[i - 1] * b;
    }

    double st = 0, dr = 1e9;
    while (dr - st > epsmic) {
        double mij = (st + dr) / 2;

        if (check( mij ).second) {
            st = mij;
        } else {
            dr = mij;
        }
    }

    fout << check( st ).first << "\n";

    fin.close();
    fout.close();
    return 0;
}