Cod sursa(job #467987)

Utilizator vladiiIonescu Vlad vladii Data 1 iulie 2010 19:54:23
Problema Minim2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <iostream>
using namespace std;
#define maxn 100010
#define maxact 10010

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

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

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