Cod sursa(job #819508)

Utilizator googolplexeGoogol googolplexe Data 19 noiembrie 2012 10:34:31
Problema Dezastru Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <iomanip>

using namespace std;

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

int attacks = 0, assaults = 0;
float chances[25] = {0.0f}, chanceToSurvive = 0.0f;
int permutation[25] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
float factorial = 0.0f;

int inPermutation(int value)
{
	for(int i=0 ; i < attacks; i++)
		if(permutation[i]==value)
			return 1;
	return 0;
}

void bt(int position)
{
	if(position == assaults)
	{
		float partialChance = 1.0f;
		for(int i = 0; i < assaults; i++)
			partialChance *= chances[permutation[i]];
		chanceToSurvive += partialChance;
		factorial+=1;
	}
	else
	{
		for(int attack = 0; attack < attacks; attack++)
		{
			if(!inPermutation(attack))
			{
				permutation[position] = attack;
				bt( position+1 );
				permutation[position] = -1;
			}
		}
	}
}

int main()
{
	in >> attacks >> assaults;
	for(int i = 0; i < attacks; i++)
		in >> chances[i];
	in.close();
	bt(0);
	out << setprecision(6)<< chanceToSurvive/factorial;
	out.close();
	return 0;
}