Cod sursa(job #309968)

Utilizator sandyxpSanduleac Dan sandyxp Data 1 mai 2009 15:49:35
Problema Dezastru Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <cassert>
#include <iomanip>
using namespace std;

#define NUME "dezastru"
ifstream fi(NUME".in");
ofstream fo(NUME".out");
#define MAXN 30

int n, k, A[MAXN];
double P[MAXN];

int main()
{
    int i, nr = 0;
    double prob = 0, pcrt = 1;
    fi >> n >> k;
    for (i = 1; i <= n; ++i)
        fi >> P[i];

    for (i = 1; i <= k; ++i) {
        A[i] = i;
        pcrt *= P[i];
    }
    // def apt calc C_n_k
    // si pt fiecare din aceste probabilitati, inmultesc cu k!(n-k)!
    //
    // totul div n!
    i = k;
    while (1) {
        prob += pcrt; // * k!(n-k)!, dar div n! - adica div nr, facem la sf
        nr ++;
        pcrt /= P[A[i]];
        A[i] ++;
        // descending
        while (i && A[i] > n+i-k) {
            --i;
            if (i == 0) break;
            pcrt /= P[A[i]];
            A[i] ++;
        }
        if (i == 0) break;
        pcrt *= P[A[i]];
        // going up again
        for (; i < k; ++i) {
            A[i+1] = A[i] + 1;
            pcrt *= P[A[i+1]];
        }
    }
    // nr = Cnk
    fo << setiosflags(ios::fixed) << setprecision(6) << prob/nr << endl;
    return 0;
}