Cod sursa(job #1991900)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 18 iunie 2017 16:57:36
Problema Minim2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <cmath>

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, double> 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 = (int)(log(valmax / aux) / log( b ));
            if (aux * pb[ans + 1] >= valmax) ++ ans;

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

    return make_pair(cate, sum);
}

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 > epsmare) {
        double mij = (st + dr) / 2;

        if (check( mij ).second - rec < epsmare) {
            st = mij;
        } else {
            dr = mij;
        }
    }

    pair<int, double> sol = check( st );
    fout << sol.first - (int)((rec - sol.second) / st) << "\n";

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