Cod sursa(job #1141816)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 13 martie 2014 10:33:56
Problema Dezastru Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
/// Craciun Catalin
///  Dezastru
///   www.infoarena.ro/problema/dezastru
#include <fstream>
#include <iostream>
#include <iomanip>
#include <algorithm>

#define NMax 30

using namespace std;

ifstream f("dezastru.in");
ofstream g("dezastru.out");

short n,k;
double A[NMax];
bool uz[NMax];
int C[NMax];
long long numitor;
double rez=0;

long long fact(long long x)
{
	long long p=1;
	
	for (int i=2;i<=x;i++)
		p*=i;
	
	return p;
}

void foundPermutation()
{
	float temp=1;
	for (int i=1;i<=k;i++)
		temp*=A[C[i]];
	
	temp/=numitor;
	
	rez+=temp;
}

void found()
{
	double temp=A[C[1]];
	for (int i=2;i<=k;i++)
		temp*=A[C[i]];

	temp=temp*fact(k);
	temp=temp/numitor;
	
	rez+=temp;
}

void perm()
{ 
	for (int i=1;i<=n;i++)
		C[i]=i;
		
	for (int i=1;i<=numitor;i++)
	{
		foundPermutation();
		next_permutation(C+1, C+n+1);
	}
}

void comb(int p)
{
	if (p==k+1)
		found();
	else
		for (int i=C[p-1]+1;i<=n;i++)
		{
			C[p]=i;
			comb(p+1);
		}
}

int main()
{	
	f>>n>>k;
	numitor=fact(n); 
	for (short i=1;i<=n;i++)
		f>>A[i];
	f.close();
	
	comb(1);
	
	g<<fixed<<setprecision(6)<<rez<<'\n';
	g.close();
	
	return 0;
}