Cod sursa(job #743363)

Utilizator Victor10Oltean Victor Victor10 Data 3 mai 2012 23:38:10
Problema Dezastru Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <cstdio>

int n, k, totalposib;
int pos [20];
double chance [30];
double S, totalchance = 1;

void back1 (int i, double curchance) {
	int j;
	for (j = pos [i - 1] + 1; j <= n; ++ j) {
		//printf ("j = %d chance [j] = %lf curchance = %lf\n", j, chance [j], curchance);
		pos [i] = j;
		curchance *= chance [pos [i]];
		if (i == k) {
			//printf ("curchance = %lf\n", curchance);
			S += curchance;
			curchance /= chance [pos [i]];
			++ totalposib;
		}
		else {
			back1 (i + 1, curchance);
			curchance /= chance [pos [i]];
		}
	}
}

void back2 (int i, double curchance) {
	int j;
	for (j = pos [i - 1] + 1; j <= n; ++ j) {
		pos [i] = j;
		curchance *= chance [pos [i]];
		if (i == k) {
			++totalposib;
			//printf ("curchance = %lf, S += %lf\n", curchance, totalchance / curchance);
			S += totalchance / curchance;
			curchance /= chance [pos [i]];
			//printf ("S = %lf\n", S);
		}
		else {
			back2 (i + 1, curchance);
			curchance /= chance [pos [i]];
		}
	}
}

int main () {
	
	freopen ("dezastru.in", "r", stdin);
	freopen ("dezastru.out", "w", stdout);
	
	int i;
	
	scanf ("%d%d", &n, &k);
	
	for (i = 1; i <= n; ++ i) {
		scanf ("%lf", &chance [i]);
		totalchance *= chance [i];
	}
	
//	printf ("totalchance = %lf\n", totalchance);
	
	if (n == k) {
		printf ("%lf\n", totalchance);
		return 0;
	}
	if (k < n - k) { // cazul in care facem totul cu back1
		back1 (1, 1);
	//	printf ("totalposib = %d\n", totalposib);
		printf ("%.6lf\n", S / (double)(totalposib));
	}
	else {
		k = n - k;
		back2 (1, 1);
		printf ("%.6lf\n", (S / (double)(totalposib)));
	}
}