Cod sursa(job #1991800)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 18 iunie 2017 13:57:22
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Simulare 15a Marime 1.09 kb
#include <fstream>
#include <queue>

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

struct str {
    double x, mod;

    inline bool operator < (const str &k) const {
        if (mod != k.mod) {
            return (mod < k.mod);
        }
        return (x < k.x);
    }
};
priority_queue< str > s;

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

    for (int i = 1; i <= n; ++ i) {
        str x;
        x.x = v[ i ];
        x.mod = v[ i ] * (1 - a);
        s.push( x );
    }

    int cnt = 0;
    while (sum - rec >= epsmare) {
        str x = s.top();
        s.pop();

        sum -= x.mod;
        ++ cnt;
        str y;
        y.x = x.x - x.mod;
        y.mod = y.x * (1 - b);
        s.push( y );
    }

    fout << cnt << "\n";

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