Cod sursa(job #1367748)

Utilizator muraru_georgeMuraru George Cristian 323CB muraru_george Data 2 martie 2015 03:42:44
Problema Dezastru Scor 70
Compilator c Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<stdio.h>
#include<stdbool.h>
int v[26], n, k, l = 0;
bool checked[26];
float p[26], all_prob;

void back1(int nr_curent, float probTot)
{

	
	if (k + 1 == nr_curent) {
		l++;
		all_prob += probTot;
		return;
	}


	int i;
	for (i = v[nr_curent - 1] + 1; i <= n ; i++) {
		if (!checked[i]) {
			checked[i] = true;
			v[nr_curent] = i;
			back1(nr_curent + 1, probTot/p[i]);
			checked[i] = false;
		}
	}
}
	
void back2(int nr_curent, float probTot)
{

	
	if (k + 1 == nr_curent) {
		l++;
		all_prob += probTot;
		return;
	}


	int i;
	for (i = v[nr_curent - 1] + 1; i <= n ; i++) {
		if (!checked[i]) {
			checked[i] = true;
			v[nr_curent] = i;
			back2(nr_curent + 1, probTot * p[i]);
			checked[i] = false;
		}
	}
}

int main(void)
{
	FILE *f_in = freopen("dezastru.in", "rt", stdin);
	FILE *f_out = freopen("dezastru.out", "wt", stdout);

	scanf("%d %d\n", &n, &k);
	int i;
	float totalProb = 1;
	for (i = 1; i <= n; i++) {
		scanf("%f", &p[i]);
		totalProb *= p[i];
	}
	
	if (k > n / 2) {
		k = n - k;
		back1(1, totalProb);
	} else
		back2(1, 1);
	printf("%f\n", all_prob / l);
}