Pagini recente » Cod sursa (job #2720198) | Cod sursa (job #1977562) | Cod sursa (job #3040910) | Profil Fan_Club | Cod sursa (job #1484899)
// 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;
}