Pagini recente » Cod sursa (job #2265370) | Cod sursa (job #271670) | Cod sursa (job #843031) | Cod sursa (job #3168490) | Cod sursa (job #2504834)
#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;
}