Cod sursa(job #831730)

Utilizator sebii_cSebastian Claici sebii_c Data 9 decembrie 2012 01:19:13
Problema Dezastru Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>

int n, k;
double res = 0.0;
double sol[25];
double v[25];
bool viz[25];

void generate(int len, int last)
{
    if (len == k) {
        double perm = 1.0;
        for (int i = 0; i < k; ++i)
            perm *= sol[i];
        res += perm;
    } else {
        for (int i = last; i < n; ++i) {
            if (viz[i])
                continue;
            viz[i] = true;
            sol[len] = v[i];
            generate(len + 1, i);
            viz[i] = false;
        }
    }
}

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

    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; ++i)
        scanf("%lf", &v[i]);
    generate(0, 0);
    int comb[26][26];
    comb[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        comb[i][0] = 1;
        for (int j = 1; j <= k; ++j)
            comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
    }
    printf("%lf\n", res / comb[n][k]);
    
    return 0;
}