Cod sursa(job #1666509)

Utilizator pickleVictor Andrei pickle Data 28 martie 2016 06:14:18
Problema Dezastru Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <algorithm>
#include <bitset>
#include <cmath>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <string.h>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
ifstream fin ("dezastru.in");
ofstream fout ("dezastru.out");
const int INF = 0x3f3f3f3f;
const int Nmax = 30;

double p[Nmax];
double S[Nmax][Nmax];
ll C[Nmax][Nmax];

int main() {
  int N, K;
  fin >> N >> K;
  for(int i = 1; i <= N; ++i)
    fin >> p[i];

  // initialize
  for(int n = 0; n <= N; ++n) {
    S[n][0] = 1;
    C[n][0] = 1;
  }
  for(int k = 1; k <= N; ++k) {
    S[0][k] = 0;
    C[0][k] = 0;
  }

  for(int n = 1; n <= N; ++n)
  for(int k = 1; k <= n; ++k) {
    S[n][k] = S[n-1][k] + p[n]*S[n-1][k-1];
    C[n][k] = C[n-1][k] + C[n-1][k-1];
  }

  // for(int n = 0; n <= N; ++n) {
  //   for(int k = 0; k <= n; ++k)
  //     cout << C[n][k] << ' ';
  //   cout << endl;
  // }

  // for(int n = 0; n <= N; ++n) {
  //   for(int k = 0; k <= n; ++k)
  //     cout << S[n][k] << ' ';
  //   cout << endl;
  // }
  fout << (S[N][K]/C[N][K]) << endl;

  return 0;
}