Cod sursa(job #2381515)

Utilizator Juve45UAIC Alexandru Ionita Juve45 Data 16 martie 2019 21:59:58
Problema Dezastru Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> //required
// #include <ext/pb_ds/tree_policy.hpp> //required

#define dbg(x) cerr<<#x": "<<x<<"\n"
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

#define st first
#define nd second

// using namespace __gnu_pbds; 
using namespace std;

// template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // ordered_set <int> s;
template<class T> ostream& prnt(ostream& out, T v) { out << v.size() << '\n'; for(auto e : v) out << e << ' '; return out;}
template<class T> ostream& operator<<(ostream& out, vector <T> v) { return prnt(out, v); }
template<class T> ostream& operator<<(ostream& out, set <T> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, map <T1, T2> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, pair<T1, T2> p) { return out << '(' << p.st << ' ' << p.nd << ')'; }

const int N = 50;
long long n, k, m;
double p[N];

double get_p(int msk) {
	// dbg(msk);
	double ans = 1;
	int ind = 1;
	while(msk) {
		if(msk % 2 == 1)
			ans *= p[ind];
		msk /= 2;
		ind++;
	}
	// dbg(ans);
	return ans;
}

double ans, nr;


void bkt(int msk, int lvl) {

	int curr = __builtin_popcount(msk);
	if(curr > k || curr + n - lvl < k)
		return;
	if(lvl == n) {
		// dbg(msk);
		if(curr == k) {
			ans += get_p(msk);
			nr += 1;
		}
		return;
	} 

	bkt(msk * 2, lvl + 1);
	bkt(msk * 2 + 1, lvl + 1);
}

int main() {

	// ios_base::sync_with_stdio(false);
	freopen("dezastru.in", "r", stdin);
	freopen("dezastru.out", "w", stdout);

	cin >> n >> k;
	for(int i = 1; i <= n; i++) cin >> p[i];

	cout << fixed << setprecision(8);

	bkt(0, 0);
	cout << ans / nr << '\n';
}