Cod sursa(job #717477)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 19 martie 2012 22:27:14
Problema Dezastru Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
/*#include <fstream>

using namespace std;

int n, m, nrc, m1;
double a[28], sol;

inline void back(int k, int s, double sum)
{
	if (k == m1)
	{
		sol += sum;
		nrc++;
	}
	else
		for (int i=s + 1; i<=n-m+k; i++)
			back(k+1, i, sum*a[i]);
}

int main()
{
	ifstream f("dezastru.in");
	f>>n>>m;
	int i;
	for (i=1; i<=n; i++)
		f>>a[i];
	f.close();	
	
	m1 = m + 1;
	back(1, 0, 1);
	
	ofstream g("dezastru.out");
	g<<sol/nrc<<"\n";
	g.close();
	
	return 0;
}
*/
#include <fstream>
#include <cstdio>

using namespace std;

int n, m, t[30][30], nrc, c[28];
double a[28], sol, prod;

void Read()
{
	ifstream f("dezastru.in");
	f>>n>>m;
	int i;
	for (i=1; i<=n; i++)
		f>>a[i];
	f.close();	
}

void GenComb()
{
	int i, j;
	for (i=0; i<28; i++)
		t[i][i] = t[i][0] = 1;
	for(i=1; i<28; i++)
		for(j=1; j<i; j++)
			t[i][j] = t[i-1][j] + t[i-1][j-1];
}

inline void back(int k)
{
	if (k-1 == m)
	{
		sol += prod/nrc;
	}
	else
	{
		int i;
		for (i=c[k-1] + 1; i<=n-m+k; i++)
		{
			prod *= a[i];
			c[k] = i;
			back(k+1);
			prod /= a[i];
		}
	}
}

void Solve()
{
	GenComb();
	nrc = t[n][m];
	prod = 1;
	back(1);
}

void Write()
{
	freopen("dezastru.out", "w", stdout);
	printf("%.6lf\n", sol);
}

int main()
{
	Read();
	Solve();
	Write();
	return 0;
}