Cod sursa(job #468034)

Utilizator vladiiIonescu Vlad vladii Data 1 iulie 2010 23:04:09
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <iostream>
#include <math.h>
using namespace std;
#define maxn 100010
#define maxact 10010
#define e 1E-6

long long N, S, nract, sol, D[maxn];
long double A, B, Record, sum;
long double Bpow[maxact];

long long afla(long double ramas, long double val) {
    int ls = 0, ld = 10000;
    long long rasp = 0;
    while(ls <= ld) {
         int mij = (ls + ld) >> 1;
         if(ramas * Bpow[mij] < val) {
              rasp = mij;
              ld = mij - 1;
         }
         else {
              ls = mij + 1;
         }
    }
    return rasp;
}

int main() {
    FILE *f1=fopen("minim2.in", "r"), *f2=fopen("minim2.out", "w");
    int i, j, p, q;
    fscanf(f1, "%lld\n", &N);
    for(i=1; i<=N; i++) {
         fscanf(f1, "%lld", &D[i]);
         S += D[i];
    }
    fscanf(f1, "%llf %llf %llf", &A, &B, &Record);
    
    Bpow[0] = 1;
    for(i=1; i<maxact; i++) {
         Bpow[i] = Bpow[i-1] * B;
    }    
    
    int ls=0, ld = 1000000000;
    while(ls <= ld) {
         nract = 0; sum = 0;
         long double mij = (ls + ld) >> 1;
         long double val = mij;
         for(i=1; i<=N; i++) {
              long double aux = D[i];
              if(aux * (1 - A) >= val) {
                   aux = aux * A;
                   nract++;
                   if(aux * (1 - B) >= val) {
                        //long long decite = afla(aux * (1 - B), val);
                        int decite = (int)(log(val / aux / (1 - B))) / log(B);
                        nract += decite;
                        aux *= Bpow[decite];
                        while(aux * (1 - B) >= val) {
                             aux *= B;
                             nract++;
                        }
                   }
              }
              sum += aux;
         }
         if(fabs(sum - Record) <= e || sum < Record) {
              sol = nract;
              ls = (long long)mij + 1;
         }
         else {
              ld = (long long)mij - 1;
         }
    }
    
    fprintf(f2, "%lld\n", sol);
    fclose(f1); fclose(f2);
    return 0;
}