Cod sursa(job #728584)

Utilizator harababurelPuscas Sergiu harababurel Data 28 martie 2012 20:05:29
Problema Dezastru Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dezastru.in");
ofstream g("dezastru.out");
short n, k, st[30];
bool vizitat[30];
long long perm=0;
double p[30], prob, probfinal=0;

void citire() {
	int i;
	f>>n>>k;
	for(i=1; i<=n; i++) f>>p[i];
}
void tipar() {
	int i; prob=1;
	for(i=1; i<=k; i++) {
//		g<<st[i]<<" ";
		prob*=p[st[i]];
	}
	
	probfinal+=prob;
//	g<<"\n";
	perm++;
}

int valid(int q) {
//	int i; 
//	for(i=1; i<q; i++) {
//		if(st[q]<=st[i]) return 0;
//	}
	
	
	return 1;
}

void back(int q) {
	int i;
	for(i=1; i<=n; i++) {
		while(vizitat[i] && i<n) i++;
		if(!vizitat[i] || i!=n) {
		st[q]=i;
			vizitat[st[q]]=1;
			if(q==k) tipar();
			else back(q+1);
		vizitat[st[q]]=0;
		}
	}
	
}

int main() {
	citire();
	back(1);
	g<<probfinal/perm;
	f.close();
	g.close();
	return 0;
}