Cod sursa(job #698777)

Utilizator matei_cChristescu Matei matei_c Data 29 februarie 2012 15:58:01
Problema Dezastru Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<cstdio>

const int MAX_N = 26;

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

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