Cod sursa(job #490333)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 6 octombrie 2010 00:56:13
Problema Dezastru Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include<fstream>
#include<iostream>
#include<iomanip>
using namespace std;

#define MAXN 26
typedef unsigned long long uint64;
int n,k;

double probs[MAXN];

double total;

inline int maximum(const int a, const int b)
{
	return a>b?a:b;
}

inline int minimum(const int a, const int b)
{
	return a<b?a:b;
}


void comb(const int cur, const int l, const double prod)
{
	if(l==k)
	{
		/*double prod=1;
		for(int i=1; i<=k; ++i)
		{
			cout<<v[i]<<" ";
			prod*=probs[v[i]];
		}
		cout<<"\n";*/
		//cout<<"-- "<<l<<" --\n";
		//cout<<cur<<endl;
		//cout<<"Done\n";
		total+=prod;
	}
	else
	{
		//cout<<"-- "<<l<<" --\n";
		for(int i=cur; i<=n; ++i)
		{
			//v[cur+1]=i+1;
			//cout<<i<<" * ";
			comb(i+1,l+1,prod*probs[i]);
		}
	}
}

int main()
{
	//int v[MAXN];
	fstream fin("dezastru.in", fstream::in);
	fstream fout("dezastru.out", fstream::out);
	
	fin>>n>>k;
	uint64 Cnk=1,prod=1;
	for(int i=maximum(n-k,k)+1; i<=n; ++i)
		Cnk*=i;
	for(int i=1; i<=minimum(n-k,k); ++i)
		prod*=i;
	Cnk/=prod;
	//cout<<Cnk<<endl;
	
	for(int i=1; i<=n; ++i)
	{
		fin>>probs[i];
		//cout<<probs[i]<<" ";
	}
	//cout<<endl;
	
	/*for(int i=1;i<=25; ++i)
		fact*=i;
	cout<<fact<<endl;*/
	
	for(int i=1; i<=n-k+1; ++i)
	{
		comb(i+1,1,probs[i]);
	}

	fout<<setiosflags(fstream::fixed)<<setprecision(6)<<total/((double)Cnk)<<" \n";
	fin.close();
	fout.close();
	return 0;
}