Cod sursa(job #1244139)

Utilizator cociorbaandreiAndrei Cociorba cociorbaandrei Data 16 octombrie 2014 20:32:26
Problema Dezastru Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <iostream>
#include <vector>

float a[25];
float sum;

// Precomputed factorial
const long long fact[] =
{
	1,
	1,
	2,
	6,
	24,
	120,
	720,
	5040,
	40320,
	362880,
	3628800,
	39916800,
	479001600,
	6227020800,
	87178291200,
	1307674368000,
	20922789888000,
	355687428096000,
	6402373705728000,
	121645100408832000,
	2432902008176640000,
	5109094217170944, // + 0000
	112400072777760768, // + 0000
	2585201673888497664, // + 0000
	3102242008666197, // + 0000 times 2 + 0000
	15511210043330985984, // + 000000
};
long long getFactorial(int n)
{
	if (n <= 20)
		return fact[n];
	//Else we have to work on large numbers and rewrite the whole program from scratch
}

void printVector(std::vector<int> vector)
{
	for (std::vector<int>::const_iterator itr = vector.begin(); itr != vector.end(); itr++)
		std::cout << *itr << " ";
	std::cout << std::endl;
}

bool isValidArrangement(std::vector<int> vector, int key)
{
	for (std::vector<int>::const_iterator itr = vector.begin(); itr != vector.end(); itr++)
		if (*itr == key) return false;
	return true;
}

float computeProduct(std::vector<int> &tempStack, long long numberOfPermutation)
{
	float product = 1;
	for (std::vector<int>::const_iterator itr = tempStack.begin(); itr != tempStack.end(); itr++){
		product *= a[*itr - 1];
	}

	return product / numberOfPermutation;
}

void permute(int n, int k, std::vector<int> &tempStack)
{
	if (k == 0){
		sum += computeProduct(tempStack, getFactorial(n));
	}
	else{
		for (int itr = 1; itr <= n; itr++){
			if (isValidArrangement(tempStack, itr)){
				tempStack.push_back(itr);
				permute(n, k - 1, tempStack);
				tempStack.pop_back();
			}
		}
	}
}

int main()
{	
	int n = 0, k = 0;
	FILE *in, *out;
	std::vector<int> stack;

	in = fopen("dezastru.in", "r");
	out = fopen("dezastru.out", "w");
	
	fscanf(in, "%d %d", &n, &k);

	for (int i = 0; i < n; i++){
		fscanf(in, "%f", a + i);
	}
	
	permute(n, k, stack);
	fprintf(out, "%.6f", sum);

	return 0;
}