Cod sursa(job #1248208)

Utilizator cociorbaandreiAndrei Cociorba cociorbaandrei Data 24 octombrie 2014 19:37:47
Problema Dezastru Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>
#include <iostream>

float a[1000], sum;
int v[1000];

unsigned nChoosek(unsigned n, unsigned k)
{
	if (k > n) return 0;
	if (k * 2 > n) k = n - k;
	if (k == 0) return 1;

	int result = n;
	for (int i = 2; i <= k; ++i) {
		result *= (n - i + 1);
		result /= i;
	}
	return result;
}

float computeProduct(int p, long long n)
{
	float product = 1;
	for (int i = 0; i < p; i++){
		product *= a[v[i] - 1];
	}

	return (product) / n;
}

bool valid(int p)
{
	if (p == 0) 
		return true;
    if (!(v[p] > v[p - 1]) ) 
		return false;
	return true;
}

void combinari(int n, int k, int p)
{
	if (p == k){
		sum += computeProduct(p, nChoosek(n,k));
	}
	else {
		for (int i = 1; i <= n; i++){
			v[p] = i;
			if (valid(p)) {
				combinari(n, k, p + 1);
			}
		}
	}
}

int main()
{
	int n = 0, k = 0;
	FILE *in, *out;

	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);
	}

	combinari(n, k, 0);
	fprintf(out, "%.6f", sum);
	return 0;
}