Cod sursa(job #1759418)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 19 septembrie 2016 09:19:50
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <cstdio>
#include <cmath>

#define MAXN 100000
#define MAXP 20000
#define EPS 0.000001

double a, b, put[MAXP+1];
int v[MAXN+1], n;

inline void precalc(){
    put[0]=1;
    for(int i=1; i<=MAXP; i++)
        put[i]=put[i-1]*b;
}

inline double calc(double lim){
    int r;
    double x, sum=0, trans=log(b);
    for(int i=1; i<=n; i++){
        x=v[i];
        if(x*(1-a)>=lim){
            x*=a;
            if(x*(1-b)>=lim){
                r=log(lim/x/(1-b))/trans;
                x*=put[r];
                while(x*(1-b)>=lim) x*=b;
            }
        }
        sum+=x;
    }
    return sum;
}

inline int solve(double lim){
    int r, ans=0;
    double x, trans=log(b);
    for(int i=1; i<=n; i++){
        x=v[i];
        r=0;
        if(x*(1-a)>=lim){
            x*=a;
            ans++;
            if(x*(1-b)>=lim){
                r=log(lim/x/(1-b))/trans;
                x*=put[r];
                ans+=r;
                while(x*(1-b)>=lim) x*=b, ans++;
            }
        }
    }
    return ans;
}

int main(){
    int max;
    double st, dr, m, k;
    FILE *fin, *fout;
    fin=fopen("minim2.in", "r");
    fout=fopen("minim2.out", "w");
    fscanf(fin, "%d", &n);
    for(int i=1; i<=n; i++){
        fscanf(fin, "%d", &v[i]);
        if(v[i]>max) max=v[i];
    }
    fscanf(fin, "%lf%lf%lf", &a, &b, &k);
    st=0;
    dr=max;
    precalc();
    while(dr-st>EPS){
        m=(st+dr)/2;
        if(calc(m)-k<=EPS) st=m;
        else dr=m;
    }
    fprintf(fout, "%d\n", solve(st));
    fclose(fin);
    fclose(fout);
    return 0;
}