Cod sursa(job #1759014)

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

using namespace std;

//ifstream cin("tema.in");
//ofstream cout("tema.out");

const int MAXN = 100000;
const int MAXP = 13;
const double EPS = 1e-6;
const int INF = 1000000000;

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

double Reduce(double x, double value) {
    if (x * (1 - a) < value)
        return x;
    if (x * a * (1 - b) < value) {
        current++;
        temp.push_back(x * (1 - a));
        return x * a;
    }
    x *= a;
    current += 2;
    for (int i = MAXP - 1; i >= 0; i--)
        if (x * power[i] * (1 - b) >= value) {
            current += (1 << i);
            x *= power[i];
        }
    temp.push_back(x * (1 - b));
    return x * b;
}

bool Check(double value) {
    temp.clear();
    double sum = 0;
    current = 0;
    for (int i = 1; i <= n; i++)
        sum += Reduce(v[i], value);
    sort(temp.begin(), temp.end());
    for (auto &it : temp)
        if (sum + it < limit + EPS) {
            current--;
            sum += it;
        }
        else
            break;
    if (sum < limit + EPS)
        return true;
    return false;
}

int BinarySearch() {
    double left = 0, right = INF;
    int answer = INF;
    for (int step = 1; step <= 48; step++) {
        double middle = (left + right) / 2;
        if (Check(middle)) {
            answer = min(answer, current);
            left = middle;
        }
        else
            right = middle;
    }
    return answer;
}

int main() {
    freopen("minim2.in", "r", stdin);
    freopen("minim2.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf", &v[i]);
    scanf("%lf%lf%lf", &a, &b, &limit);
    power[0] = b;
    for (int i = 1; i < MAXP; i++)
        power[i] = power[i - 1] * power[i - 1];
    printf("%d\n", BinarySearch());
    return 0;
}