Cod sursa(job #2504834)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 5 decembrie 2019 17:27:04
Problema Dezastru Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <iostream>
#include <fstream>

using namespace std;

const int MAXN = 27;

int N, K;
double arr[MAXN];
bool used[MAXN];
double dp[MAXN][MAXN];
double calculated[MAXN][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;
int cnt = 0;

double backtrack(int step, int nr, double prod) {
	if (step > N) {
		if (nr == K) {
			cnt ++;
			return prod;
		}

		return 0;
	}

	
	double first = backtrack(step + 1, nr + 1, prod * arr[step]);
	double second = backtrack(step + 1, nr, prod);


	return first + second;
}


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);

	//dp[i][j] = suma toate produsele de j elemente pana la i
	for (int i = 0; i <= N + 1; i++) {
		
		// for (int j = 1; j <= K; j++) dp[i][1] += arr[j];
		dp[i][0] = 1.0;
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			// if (i - j < 1) continue;
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] * arr[i];

			
		}
	}

	fout << dp[N][K] / coeficient;

	return 0;
}