Cod sursa(job #2097121)

Utilizator giotoPopescu Ioan gioto Data 30 decembrie 2017 16:03:44
Problema Minim2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <bits/stdc++.h>
using namespace std;

int n, NR;
double l[100005];
double pb[10005];
double a, b, r;
const double eps = 1e-6;
double Sum;
inline bool check(double Max){
    Sum = 0;
    NR = 0;
    for(int i = 1; i <= n ; ++i){
        if(l[i] * (1 - a) < Max) Sum += l[i];
        else if(l[i] * a * (1 - b) < Max){
            Sum = Sum + l[i] * a;
            ++NR;
        }
        else{
            ++NR;
            double aux = l[i] * a * (1 - b);
            int p = (int)(log(Max / aux) / log(b));
            if(aux * pb[p + 1] >= Max) ++p;
            NR += p + 1;
            Sum = Sum + l[i] * a * pb[p + 1];
        }
    }
    if(abs(Sum - r) <= eps || Sum <= r) return 1;
    return 0;
}
int main()
{
    freopen("minim2.in", "r", stdin);
    freopen("minim2.out", "w", stdout);
    scanf("%d", &n);
    int x;
    for(int i = 1; i <= n ; ++i){
        scanf("%d", &x);
        l[i] = x;
    }
    scanf("%lf%lf%lf", &a, &b, &r);
    pb[0] = 1;
    for(int i = 1; i <= 1e4 ; ++i)
        pb[i] = pb[i - 1] * b;
    double st = 0, dr = 1e9;
    while(dr - st > eps){
        double mij = (st + dr) / 2;
        if(check(mij)) st = mij;
        else dr = mij;
    }
    check(st);
    for(int i = 1; i <= n ; ++i){
        if(Sum + st <= r){
            Sum += st;
            --NR;
        }
    }
    printf("%d", NR);
    return 0;
}