Cod sursa(job #2211758)

Utilizator _Victor_Victor Ciobanu _Victor_ Data 11 iunie 2018 19:05:26
Problema Dezastru Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <bits/stdc++.h>

using namespace std;

#define NMAX 26

ifstream fin("dezastru.in");

long long np=0;
int n,km,S[NMAX];
double P[NMAX],V[NMAX],PD[NMAX][NMAX];

void dp(){
	for(int i=0;i<=n;i++) PD[i][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=km;j++){
			PD[i][j]=PD[i-1][j]+PD[i-1][j-1]*P[i];
		}
	}
}

void bk(int k){
	if(k<=km){
		for(int i=S[k-1]+1;i<=n;i++){
			S[k]=i;
			bk(k+1);
			S[k]=0;
		}
	}else{
		np++;
	}
}

int main(){
	freopen ("dezastru.out","w",stdout);
	V[0]=1;
	fin>>n>>km;
	for(int i=1;i<=n;i++)fin>>P[i];
	bk(1);
	dp();
	printf("%.6f",PD[n][km]/np);
	//cerr<<clock()*1000.0/CLOCKS_PER_SEC<<'\n';
	return 0;
}