Cod sursa(job #1759028)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 18 septembrie 2016 13:50:35
Problema Minim2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100000;
const int MAXP = 20000;
const double EPS = 1e-6;

int n;
double v[1 + MAXN];
double power[1 + MAXP];
double a, b, limit;
vector<double> temp;

bool Check(double value) {
    double sum = 0, logb = log(b);
    for (int i = 1; i <= n; i++) {
        double x = v[i];
        if (x * (1 - a) >= value) {
            x *= a;
            if (x * (1 - b) >= value) {
                int which = (log(value / x / (1.0 - b))) / logb;
                x *= power[which];
                while (x * (1 - b) >= value)
                    x *= b;
            }
        }
        sum += x;
    }
    if (fabs(sum - limit) <= EPS || sum < limit)
        return true;
    return false;
}

int Count(double value) {
    int answer = 0;
    double sum = 0, logb = log(b);
    for (int i = 1; i <= n; i++) {
        double x = v[i];
        if (x * (1 - a) >= value) {
            x *= a;
            answer++;
            if (x * (1 - b) >= value) {
                int which = (log(value / x / (1.0 - b))) / logb;
                x *= power[which];
                answer += which;
                while (x * (1 - b) >= value) {
                    temp.push_back(x * (1 - b));
                    x *= b;
                    answer++;
                }
            }
        }
        sum += x;
    }
    sort(temp.begin(), temp.end());
    for (int i = 0; i < temp.size(); i++)
        if (sum + temp[i] <= limit) {
            answer--;
            sum += temp[i];;
        }
    return answer;
}

int main() {
    freopen("minim2.in", "r", stdin);
    freopen("minim2.out", "w", stdout);
    double left = 0, right = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lf", &v[i]);
        right = max(right, v[i]);
    }
    scanf("%lf%lf%lf", &a, &b, &limit);
    power[0] = 1;
    for (int i = 1; i <= MAXP; i++)
        power[i] = power[i - 1] * b;
    while (fabs(left - right) >= EPS) {
        double middle = (left + right) / 2;
        if (Check(middle))
            left = middle;
        else
            right = middle;
    }
    printf("%d\n", Count(left));
    return 0;
}