Cod sursa(job #1749005)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 27 august 2016 17:40:37
Problema Dezastru Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <cstdio>

using namespace std;

const int kMaxN = 30;
const int kMaxK = 30;

int n, k;
int n_choose_k[kMaxN][kMaxK];
double p_success[kMaxN];
double dyn_prog[kMaxN][kMaxK];

int main() {
  freopen("dezastru.in", "r", stdin);
  freopen("dezastru.out", "w", stdout);
  
  scanf("%d %d", &n, &k);
  for(int i = 1; i <= n; i++) scanf("%lf", &p_success[i]);
  
  n_choose_k[0][0] = 1;
  for(int i = 1; i <= n; i++) {
    n_choose_k[i][0] = 1;
    for(int j = 1; j <= i; j++) {
      n_choose_k[i][j] = n_choose_k[i - 1][j] + n_choose_k[i - 1][j - 1];
    }
  }

  for(int i = 0; i <= n; i++) dyn_prog[i][0] = 1;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
      dyn_prog[i][j] = dyn_prog[i - 1][j] + p_success[i] * dyn_prog[i - 1][j - 1];
    }
  }
  
  printf("%.6f\n", dyn_prog[n][k] / n_choose_k[n][k]);
  return 0;
}