Cod sursa(job #2381518)

Utilizator Juve45UAIC Alexandru Ionita Juve45 Data 16 martie 2019 22:08:09
Problema Dezastru Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.8 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;
int curr, msk;

void bkt(int lvl) {

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

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);
	cout << ans / nr << '\n';
}