Cod sursa(job #2504798)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 5 decembrie 2019 16:35:25
Problema Dezastru Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 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));
}

int64_t fastcomb(int64_t n, int64_t k) {
	int64_t mn = min(k, n - k);
	int64_t mx = max(k, n - k);

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

	for (int i = 1; i <= mn; i++) {
		ans /= i;
	}

	return ans;
}



double ans = 0;

double coeficient = 0;

void backtrack(int step, int nr, double prod) {
	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, prod * arr[step]);
	used[step] = false;
	backtrack(step + 1, nr, prod);
}


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

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

	fout << ans;
	return 0;
}