Cod sursa(job #698753)

Utilizator matei_cChristescu Matei matei_c Data 29 februarie 2012 15:49:54
Problema Dezastru Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<cstdio>

const int MAX_N = 26;

int n,k;
long long factorial=0;
double p[MAX_N],prob,sum;
int sol[MAX_N],sel[MAX_N];

void back(int level)
{
	if(k+1==level)
	{
		prob=1;
		factorial++;
		for(int i=1;i<=k;++i)
			prob*=p[sol[i]];
		sum+=prob;
		//printf("%lf\n",prob);
		return ;
	}
	for(int i=sol[level-1] + 1;i<=n;++i)
	{
		if(sel[i]==0)
		{
			sel[i]=1;
			sol[level]=i;
			back(level+1);
			sel[i]=0;
		}	
	}	
}

int main()
{
	freopen("dezastru.in","r",stdin);
	freopen("dezastru.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)
	{	
		scanf("%lf",&p[i]);
	}
	back(1);
	double sol = sum / (double)factorial;
	printf("%lf\n",sol);
	return 0;
}