Cod sursa(job #1759433)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 19 septembrie 2016 09:56:02
Problema Minim2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

#define MAXN 100000
#define MAXP 20000
#define EPS 1e-6

double a, b, k, put[MAXP+1], last[MAXN+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-2;
                if(r<0) r=0;
                x*=put[r];
                while(x*(1-b)>=lim) x*=b;
            }
        }
        sum+=x;
    }
    return sum;
}

inline int solve(double lim){
    int r, ans=0, u=0;
    double x, sum=0, 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-2;
                if(r<0) r=0;
                x*=put[r];
                while(x*(1-b)>=lim) x*=b, r++;
                if(r>0) last[u++]=(1-b)*(x/b), ans+=r;
            }else last[u++]=(1-a)*(x/a);
        }
        sum+=x;
    }
    std::sort(last, last+u);
    for(int i=0; i<u; i++){
        if(sum+last[i]<=k){
            sum+=last[i];
            ans--;
        }
    }
    return ans;
}

int main(){
    int max;
    double st, dr, m;
    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;
}