Cod sursa(job #1759395)

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

#define MAXN 100000
#define MAXP 10000
#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(1-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)/trans;
                x*=put[r];
                while(x/(1-b)<lim) x/=b;
                while(x*(1-b)>=lim) x*=b;
            }
        }
        sum+=x;
    }
    return sum;
}

inline int solve(double lim){
    int r, ans=0;
    double x, trans=log(1-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)/trans;
                x*=put[r];
                ans+=r;
                while(x/(1-b)<lim) x/=b, ans--;
                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=0.5*(st+dr);
        if(calc(m)-k<EPS) st=m;
        else dr=m;
    }
    fprintf(fout, "%d\n", solve(st));
    fclose(fin);
    fclose(fout);
    return 0;
}