Cod sursa(job #1838838)

Utilizator antanaAntonia Boca antana Data 1 ianuarie 2017 21:34:59
Problema Dezastru Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <cstdio>

#define MAXN 26

using namespace std;

unsigned long long kfact, nkfact, nfact;
double p[MAXN], ans;
int st[MAXN], n, k;

void bkt(int level, double prob)
{
    if(level == k+1)
    {
        ans += prob;
        return;
    }

    int upper, lower, i;

    lower = st[level-1] + 1;
    upper = n-k+level;

    for(i=lower; i<=upper; ++i)
    {
        st[level] = i;
        bkt(level+1, prob*p[i]);
    }
}

int main()
{
    freopen("dezastru.in", "r", stdin);
    freopen("dezastru.out", "w", stdout);

    int i;

    scanf("%d%d", &n, &k);

    for(i=1; i<=n; ++i)
        scanf("%lf", &p[i]);

    kfact = nkfact = nfact = 1;

    for(i=1; i<=n-k; ++i) nkfact *= i;
    for(i=k+1; i<=n; ++i) nfact *= i;

    bkt(1, 1);

    printf("%lf", ans*nkfact/nfact);

    return 0;
}