Cod sursa(job #1483660)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 9 septembrie 2015 18:33:57
Problema Dezastru Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("dezastru.in");
ofstream out("dezastru.out");
const int maxn = 30;
double alive[maxn];
int k, n;
double dp[maxn][maxn];

int fact(int n) {
    if(n == 1)
        return 1;
    return n * fact(n - 1);
}

int comb(int n, int k) {
///    comb(n, k) = n! / (n - k)! * !k
    if(k == 1)
        return n;
    if(n == k)
        return 1;
    return comb(n - 1, k) + comb(n - 1, k - 1);
}

int main()
{
    /**
        dp[i][j] = suma probabilitatilor produselor de j factori cu primele i zile

        rasp: dp[n][k];


        dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * alive[i];

    */
    in >> n >> k;
    for(int i = 1; i <= n; i++)
        in >> alive[i];
    for(int i = 0 ; i <= n ; ++ i)
        dp[i][0] = 1;
    for(int i = 1 ; i <= n ; ++ i)
        for(int j = 1 ; j <= min(i, k) ; ++ j)
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * alive[i];
    out << dp[n][k] / comb(n, k) << '\n';
    return 0;
}