Cod sursa(job #2097107)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 30 decembrie 2017 15:31:40
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 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];
bool ok(double val){
    nr = 0;
    S = 0;
    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 + (log(val) - log(1 - B) - log(VAL)) / log(B));
            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);
    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;
}