Cod sursa(job #309956)

Utilizator sandyxpSanduleac Dan sandyxp Data 1 mai 2009 15:35:21
Problema Dezastru Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 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], Used[MAXN];
double P[MAXN];

int not_used() {
    for (int i = 1; i <= n; ++i)
        if (!Used[i]) {
            Used[i] = 1;
            return i;
        }
    return 0;
}

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];
        Used[i] = 1;
    }
    // def apt calc C_n_k
    i = k;
    while (1) {
        prob += pcrt;
        nr ++;

        int val_init = A[i];
        pcrt /= P[A[i]];
        while (A[i] <= n && Used[A[i]])  A[i] ++;
        Used[val_init] = 0;
        if (A[i] <= n) {
            pcrt *= P[A[i]];
            Used[A[i]] = 1;
        }
        // descending
        while (i && A[i] > n) {
            --i;
            if (i == 0) break;
            pcrt /= P[A[i]];
            val_init = A[i];
            while (A[i] <= n && Used[A[i]]) A[i] ++;
            Used[val_init] = 0;
            if (A[i] <= n) {
                pcrt *= P[A[i]];
                Used[A[i]] = 1;
            }
        }
        if (i == 0) break;
        // going up again
        for (; i < k; ++i) {
            A[i+1] = not_used();
            assert(A[i+1] != 0);
            pcrt *= P[A[i+1]];
            //if (A[i+1] == 0) break;
        }
    }
    fo << setiosflags(ios::fixed) << setprecision(6) << prob/nr << endl;
    return 0;
}