Cod sursa(job #2504793)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 5 decembrie 2019 16:31:45
Problema Dezastru Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include <fstream>

using namespace std;

const int MAXN = 27;

int N, K;
double arr[MAXN];
bool used[MAXN];

int64_t fact(int n) {
	int64_t ans = 1;
	for (int i = 1; i <= n; i++) ans *= i;
	return ans;
}

int64_t comb(int64_t n, int64_t k) {
	return (fact(n)) / (fact(k) * fact(n - k));
}



double ans = 0;

double coeficient = 0;

void backtrack(int step, int nr) {
	if (step > N) {
		if (nr == K) {
			double prod = 1;
			for (int i = 1; i <= N; i++) if (used[i]) prod *= arr[i];
			ans += prod / coeficient;

		}

		return ;
	}

	used[step] = true;
	backtrack(step + 1, nr + 1);
	used[step] = false;
	backtrack(step + 1, nr);
}


int main() {
	ifstream fin("dezastru.in");
	ofstream fout("dezastru.out");
	fin >> N >> K;

	for (int i = 1; i <= N; i++) fin >> arr[i];
	coeficient = comb(N, K);
	backtrack(1, 0);

	fout << ans;
	return 0;
}