Cod sursa(job #1484899)

Utilizator theprdvtheprdv theprdv Data 12 septembrie 2015 07:47:58
Problema Dezastru Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
// backtracking solution of 2 ^ N time complexity

#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <string.h>
#include <assert.h>

#define MAXN 25

int N, K, steps;

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

	double A[MAXN], sol = 0, ans;

	scanf("%d %d\n", &N, &K);
	for (int i = 0; i < N; ++i) scanf("%lf", &A[i]);

	for (int i = 1; i < 1 << N; ++i){
		int j = 0, x = i;
		ans = 1;
		for (; x; x -= x & (-x), ++j);
		if (j != K) continue;

		for (int j = 0; j < N; ++j)
			if (i & (1 << j)) ans *= A[j];
		sol += ans;
		++steps;
	}
	printf("%lf", (sol * 2) / (steps * 2));

	return 0;
}