Cod sursa(job #36568)

Utilizator grecoTiberiu-Lucian Florea greco Data 23 martie 2007 18:39:41
Problema Dezastru Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
/*
 * Dezastru - A(N, K) - ??p
 *
 */

using namespace std;

#include <cstdio>
#include <cstring>

int N, K, start, nxt[64], prv[64], cnt;
double v[64], sum, tmp[64];

void back(int lev)
{
	int i;
	if (lev == K+1)
		sum += tmp[K], ++cnt;
	else
		for (i = nxt[start]; i != -1; i = nxt[i]) {
			tmp[lev] = tmp[lev-1]*v[i];
			nxt[prv[i]] = nxt[i];
			prv[nxt[i]] = prv[i];

			back(lev+1);

			nxt[prv[i]] = i;
			prv[nxt[i]] = i;
		}
}

int main()
{
	int i;
	freopen("dezastru.in", "r", stdin);
	freopen("dezastru.out", "w", stdout);
	
	scanf("%d %d", &N, &K);
	for (i = 1; i <= N; ++i)
		scanf("%lf", v+i);

	memset(nxt, -1, sizeof(nxt));
	memset(prv, -1, sizeof(prv));
	start = 0, nxt[start] = prv[start] = -1;

	for (i = N; i > 0; --i) {
		nxt[i] = nxt[start];
		prv[nxt[i]] = i;
		prv[i] = start;
		nxt[start] = i;
	}
	sum = 0., tmp[0] = 1.;
	back(1);

	printf("%lf\n", sum/(double)cnt);
	return 0;
}