Cod sursa(job #2097111)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 30 decembrie 2017 15:35:35
Problema Minim2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
FILE *f = fopen("minim2.in","r");
FILE *g = fopen("minim2.out","w");
int N;
int D[100005];
double A,B,R;
int nr = 0;
double S = 0;
double pw[100005];
double lgminusB;
double lgB;
bool ok(double val){
    nr = 0;
    S = 0;
    double lgval = log(val);
    for(int i = 1;i <= N;i++){
        double VAL = D[i];
        int x = 0;
        if((1 - A) * VAL >= val){
            VAL *= A;
            nr++;
        }
        if((1 - B) * VAL >= val){
            x = int(1 + (lgval - lgminusB - log(VAL)) / lgB);
            nr += x;
        }
        S += pw[x] * VAL;
    }
    return (S <= R);
}
int main()
{
    fscanf(f,"%d",&N);
    for(int i = 1;i <= N;i++){
        fscanf(f,"%d",&D[i]);
    }
    fscanf(f,"%lf %lf %lf",&A,&B,&R);
    lgB = log(B);
    lgminusB = log(1 - B);
    pw[0] = 1;
    for(int i = 1;i <= 100000;i++){
        pw[i] = B * pw[i - 1];
    }
    double st = 0,dr = 1e9;
    while(dr - st > 1e-6){
        double mid = (st + dr) / 2;
        if(ok(mid)){
            st = mid;
        }
        else{
            dr = mid;
        }
    }
    ok(st);
    for(int i = 1;i <= N;i++){
        if(S + st <= R){
            S += st;
            nr--;
        }
    }
    fprintf(g,"%d",nr);
    fclose(f);
    fclose(g);
    return 0;
}