Cod sursa(job #536653)

Utilizator mariusandreiMarius Lucian Andrei mariusandrei Data 18 februarie 2011 21:59:31
Problema Dezastru Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<cstdio>
using namespace std;
int n,k,m,nr,nrr;
int sol[26];
float v[26];
float solut=0;

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++;
	float xxx=1;
	for(int i=1;i<=k;i++)
		xxx*=v[sol[i]];
	solut+=xxx/(float)nrr;
}
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--;
	}
}
long fact(int n)
{
	if(n==1) return 1;
	return n*fact(n-1);
}
int functie(int a, int b)
{
	return (fact(n)/(fact(k)*fact(n-k)));
}
int main()
{
	freopen("dezastru.in","r",stdin);
	freopen("dezastru.out","w",stdout);
	scanf("%d%d",&n,&k);
	nrr=functie(n,k);
	for(int i=1;i<=n;i++)
		scanf("%f",&v[i]);
	back();
	printf("%f", solut);
	return 0;	
}