Cod sursa(job #2173804)

Utilizator 24601Dan Ban 24601 Data 16 martie 2018 02:10:26
Problema Dezastru Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <inttypes.h>
#include <stdio.h>
#include <string.h>

#define SIZE 25

static double sum, p[SIZE];
static int np, iter[SIZE], sol[SIZE+1];

static void comb(int n, int k)
{
    int lvl[SIZE], lvl_top, nivel;
    double prods[SIZE], prod;

    lvl_top = 0;
    lvl[lvl_top++] = 0;
    prod = 1.0;

    while (lvl_top > 0) {
        nivel = lvl[lvl_top - 1];

        if (nivel == k) {
            sum += prod;
            np++;
            prod = prods[nivel];
            lvl_top--;
        } else {
            if (sol[nivel] + iter[nivel + 1] + (k - nivel) <= n) {
                prods[nivel + 1] = prod;
                sol[nivel + 1] = sol[nivel] + 1 + iter[nivel + 1];
                prod *= p[sol[nivel + 1] - 1];
                iter[nivel + 1]++;
                lvl[lvl_top++] = nivel + 1;
            } else {
                iter[nivel + 1] = 0;
                prod = prods[nivel];
                lvl_top--;
            }
        }
    }
}

int main(void)
{
    int i, n, k;

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

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

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

    comb(n, k);

    printf("%lf", sum / np);

    return 0;
}