Cod sursa(job #536654)

Utilizator mariusandreiMarius Lucian Andrei mariusandrei Data 18 februarie 2011 22:00:43
Problema Dezastru Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<cstdio>
using namespace std;
int n,k,m,nr;
int sol[26];
float v[26],st[1000001];

void init()
{
	sol[m]=0;
}

int valid()
{
	for(int i=1;i<m;i++)
		if(sol[i]>=sol[m])
			return 0;
		return 1;
}
int solutie()
{
	return (m==k);
}
int succesor()
{
	if(sol[m]<n)
	{
		sol[m]++;
		return 1;
	}
	return 0;
}
void afisare()
{
	nr++;
	st[nr]=1;
	for(int i=1;i<=k;i++)
		st[nr]*=v[sol[i]];
}
void back()
{	
	m=1;
	init();
	int as, ev;
	while(m>0)
	{		
		do
		{
			as=succesor();
			if(as)
				ev=valid();
		}while(as&&!ev);
		if(as)
			if(solutie())
				afisare();
			else
			{
				m++;
				init();
			}
			else
				m--;
	}
}
void functie()
{
	float solutie=0;
	for(int i=1;i<=nr;i++)
		solutie+=st[i]/(float)nr;
	printf("%f",solutie);
		
}
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("%f",&v[i]);
	back();
	functie();
	return 0;	
}