Cod sursa(job #1986650)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 28 mai 2017 19:38:54
Problema Dezastru Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>

using namespace std;

int const nmax = 25;

FILE *in, *out;

int n, k;

int c[1 + nmax][1 + nmax];
double p[1 + nmax];
double dp[1 + nmax][1 + nmax];
bool memodp[1 + nmax][1 + nmax];
bool memoc[1 + nmax][1 + nmax];

int computec(int n, int k) {
  //c[n][k] = c[n-1][k-1] + c[n-1][k]
  if(k == 0 || k == n)
    return 1;
  else {
    if(memoc[n][k] == 0) { //if not computed, compute
      c[n][k] = computec(n-1, k-1) + computec(n-1, k);
      memoc[n][k] = 1;
    }
    return c[n][k];
  }
}

double computedp(int n, int k) {
  if(k == 0)
    return 1;
  else {
    if(memodp[n][k] == 0){
      dp[n][k] = computedp(n-1, k-1) * p[n] + computedp(n-1, k);
      memodp[n][k] = 1;
    }
    return dp[n][k];
  }
}

int main() {
  in = fopen("dezastru.in","r");
  out = fopen("dezastru.out","w");
  fscanf(in, "%d %d", &n, &k);
  for(int i = 1;i <= n;i ++)
    fscanf(in,"%lf", &p[i]);

  dp[1][1] = p[1];
  memodp[1][1] = 1;
  for(int i = 2; i<=n; i++) {
    dp[i][i] = dp[i-1][i-1] * p[i];
    memodp[i][i] = 1;
  }

  double sol = computedp(n, k) / computec(n, k);
  fprintf(out,"%.6lf",sol);
  return 0;
}