Cod sursa(job #796515)

Utilizator googolplexeGoogol googolplexe Data 11 octombrie 2012 17:58:51
Problema Dezastru Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>

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 == attacks)
	{
		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 << chanceToSurvive/factorial;
	out.close();
	return 0;
}