Cod sursa(job #517993)

Utilizator ioanabIoana Bica ioanab Data 30 decembrie 2010 12:53:15
Problema Dezastru Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
using namespace std;



int st[30],viz[30],n,k,x;
int num; 
float a[30],sum;
void init()
{
	st[k]=0;
}

int succesor()
{
	if(st[k]<n)
	{
		st[k]++;
		return 1;
	}
	return 0;
}
int valid()
{
	if(viz[st[k]]==0)
	{
		viz[st[k]]=1;
		return 1;
	}
	return 0;
}
int solutie()
{
	return k==n;
}

void tipar()
{
	int i;
	float p;
	p=1;
	for(i=1;i<=x;i++)
	{
		p=(float)p*a[st[i]];
	}
	sum=sum+p;
	num++;
}

void backt()
{
	int as,ev;
	k=1;
	init();
	while(k>0)
	{
		do
		{
			as=succesor();
			if(as)
				ev=valid();
		}while(as && !ev);
		if(as)
		{
			if(solutie())
			{
				tipar();
				viz[st[k]]=0;
			}
			else
			{
				k++;
				init();
			}
		}
		else
		{
			k--;
			viz[st[k]]=0;
		}
	}
}

int main()
{
	freopen("dezastru.in","r",stdin);
	freopen("dezastru.out","w",stdout);
	int i;
	scanf("%d%d",&n,&x);
	for(i=1;i<=n;i++)
		scanf("%f",&a[i]);
	backt();
	sum=sum/num;
	printf("%.6f",sum);
	return 0;
}