Cod sursa(job #1748990)

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

using namespace std;

const int kMaxN = 30;

double p_success[kMaxN];
double p_final, p_current, fact_k, fact_n;
int n, k;

void Backtracking(int n_elem, int id_start) {
  if(n_elem == k + 1) {
    p_final += p_current * fact_k / fact_n;
    return;
  }
  for(int i = id_start; i <= n + n_elem - k; i++) {
    p_current *= p_success[i];
    Backtracking(n_elem + 1, i + 1);
    p_current /= p_success[i];
  }
}

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]);
  
  fact_k = 1; for(int i = 2; i <= k; i++) fact_k *= i;
  fact_n = 1; for(int i = 2; i <= n; i++) fact_n *= i;
  
  p_current = 1;
  Backtracking(1, 1);
  
  printf("%.6f\n", p_final);
  return 0;
}