stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, a, b) for (int i = a; i < (int)b; i++)

#define all(v) v.begin(), v.end()

const int MOD = 1e9 + 7;

const int INF = 1e9;

//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122



int n;

vector<vector<int>> g(100010);



vector<int> calcdist(int s) {

    vector<int> dist(100010, -1);

    dist[s] = 0;

    queue<int> que;

    que.push(s);

    while (!que.empty()) {

        int now = que.front();

        que.pop();

        for (int next : g[now]) {

            if (dist[next] != -1) continue;

            dist[next] = dist[now] + 1;

            que.push(next);

        }

    }

    return dist;

}



int main() {

    int n, u, v;

    cin >> n >> u >> v;

    u--;

    v--;

    rep(i, 0, n - 1) {

        int a, b;

        cin >> a >> b;

        a--;

        b--;

        g[a].push_back(b);

        g[b].push_back(a);

    }



    vector<int> dist1 = calcdist(u);

    vector<int> dist2 = calcdist(v);



    int ans = 0;

    rep(i, 0, n) {

        if (dist1[i] < dist2[i]) ans = max(ans, dist2[i]);

    }

    cout << ans - 1 << endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.2765924010418912x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, a, b) for (int i = a; i < (int)b; i++)

#define all(v) v.begin(), v.end()

const int MOD = 1e9 + 7;

const int INF = 1e9;

//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122



vector<int> edge[100010];

int dist1[100010], dist2[100010];



void dfs1(int v, int p) {

    for (int nv : edge[v]) {

        if (nv == p) continue;

        dist1[nv] = dist1[v] + 1;

        dfs1(nv, v);

    }

}



void dfs2(int v, int p) {

    for (int nv : edge[v]) {

        if (nv == p) continue;

        dist2[nv] = dist2[v] + 1;

        dfs2(nv, v);

    }

}



int main() {

    int n, u, v;

    cin >> n >> u >> v;

    u--; v--;

    rep(i, 0, n - 1) {

        int a, b;

        cin >> a >> b;

        a--; b--;

        edge[a].push_back(b);

        edge[b].push_back(a);

    }



    dfs1(u, -1);

    dfs2(v, -1);



    int ans = 0;

    rep(i, 0, n) {

        if (dist1[i] < dist2[i]) ans = max(ans, dist2[i]);

    }

    cout << ans - 1 << endl;

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<string>

#include<vector>



using namespace std;



#define rep(i, n) for(int i = 0; i < n; i++)





int const MAX_N = 100000;

vector<int> G[MAX_N];

int taka[MAX_N];

int ao[MAX_N];



void dfs(int e, int num, int per[]){

    rep(i, G[e].size()){

        int edge = G[e][i];

        if (per[edge] != -1) continue;

        else {

            per[edge] = num;

            dfs(edge, num + 1, per);

        }

    }

}



int main(){

    int n, u , v;

    cin >> n >> u >> v;

    u--;

    v--;

    rep(i, n - 1){

        int a, b;

        cin >> a >> b;

        a--; b--;

        G[a].push_back(b);

        G[b].push_back(a);

    }

    fill(taka, taka + n, -1);

    fill(ao, ao + n, -1);



    taka[u] = 0;

    dfs(u, 1, taka);

    ao[v] = 0;

    dfs(v, 1, ao);

    // rep(i, n) cout << taka[i] << " ";

    // cout << endl;

    int ans = 0;

    int idx;

    rep(i, n){

        if (taka[i] < ao[i] && ans < ao[i]){

            ans = ao[i];

            idx = i;

        }

    }

    cout << ans - 1 << endl;

    // if ((ao[idx] - taka[idx]) % 2 == 0){

    //     cout << ans - 1 << endl;

    // }else{

    //     cout << ans << endl;

    // }

    

}

// Faster C++ solution for the same problem (measured speedup: 3.484962224305498x):
#include<iostream>

#include<algorithm>

#include<string>

#include<vector>

#include<cstdlib>

#include<queue>

#include<set>

#include<cstdio>

#include<map>



using namespace std;



#define ll long long

#define rep(i, n) for(int i = 0; i < n; i++)

#define P pair<int, int>



typedef vector<int> vec;

typedef vector<vec> mat;



const ll mod = 1000000007;



int main(){

    int n, u, v;

    cin >> n >> u >> v;

    u--; v--;

    vector<vector<int> > e(n);

    rep(i, n-1) {

        int a, b;

        cin >> a >> b;

        a--; b--;

        e[a].push_back(b);

        e[b].push_back(a);

    }

    vector<int> du(n, -1), dv(n, -1);

    du[u] = 0; dv[v] = 0;

    queue<P> que_u, que_v;

    que_u.push(P(u, 0));

    que_v.push(P(v, 0));

    while(que_u.size() > 0){

        P p = que_u.front();

        que_u.pop();

        int s = p.first;

        int d = p.second;

        rep(i, e[s].size()){

            if(du[e[s][i]] != -1) continue;

            du[e[s][i]] = d + 1;

            que_u.push(P(e[s][i], d+1));

        }

    }

    while(que_v.size() > 0){

        P p = que_v.front();

        que_v.pop();

        int s = p.first;

        int d = p.second;

        rep(i, e[s].size()){

            if(dv[e[s][i]] != -1) continue;

            dv[e[s][i]] = d + 1;

            que_v.push(P(e[s][i], d+1));

        }

    }

    int ans = 0;

    rep(i, n){

        if(du[i] < dv[i]){

            ans = max(ans, dv[i]);

        }

    }

    // rep(i, n){

    //     cout << du[i] << " " ;

    // }cout << endl;

    // rep(i, n){

    //     cout << dv[i] << " " ;

    // }cout << endl;

    cout << ans - 1 << endl;



}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <utility>

#include <set>

#include <stack>

#include <climits>

#include <cmath>



#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

#define all(x) (x).begin(),(x).end()

#define MEMSET(v, h) memset((v), h, sizeof(v))

typedef long long ll;



using namespace std;



struct node{

    vector<int> par;

    ll T, A, val;

};



static node c[100009];



void Aoki(int come, int cur, int depth){

    //cout<<cur<<" "<<depth<<endl;

    c[cur].A=depth;

    rep(i, c[cur].par.size()){

        if(c[cur].par[i]==come) continue;

        else Aoki(cur, c[cur].par[i], depth+1);

    }

}

void Taka(int come, int cur, int depth){

    c[cur].T=depth;

    if(c[cur].A<=depth) depth=100001;

    

    rep(i, c[cur].par.size()){

        if(c[cur].par[i]==come) continue;

        else{

           Taka(cur, c[cur].par[i], depth+1);

        }

    }

}





int main(void){

    int N, u, v, a, b;

    

    cin>>N>>u>>v;

    rep(i, N-1){

        cin>>a>>b;

        c[a-1].par.push_back(b-1);

        c[b-1].par.push_back(a-1);

    }

    Aoki(-1, v-1, 0);

    Taka(-1, u-1, 0);

    ll Maxim=0;

    rep(i, N){

        if(c[i].A>=c[i].T) Maxim=max(Maxim, c[i].A-1) /*cout<<i<<endl*/;

    }

    cout<<Maxim<<endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.1689202689877807x):
#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <utility>

#include <set>

#include <stack>

#include <climits>

#include <cmath>



#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)

#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)

#define all(x) (x).begin(),(x).end()

#define MEMSET(v, h) memset((v), h, sizeof(v))

typedef long long ll;

const char sp = ' ';



using namespace std;



struct Node{

    ll depthT;

    ll depthA;

    vector<ll> chi;

};

Node node[100004];



void dfsT(ll loca, ll depth, ll rem){

    node[loca].depthT=depth;

    rep(i, node[loca].chi.size()){

        if(node[loca].chi[i]==rem) continue;

        dfsT(node[loca].chi[i], depth+1, loca);

    }

}



void dfsA(ll loca, ll depth, ll rem){

    node[loca].depthA=depth;

    rep(i, node[loca].chi.size()){

        if(node[loca].chi[i]==rem) continue;

        dfsA(node[loca].chi[i], depth+1, loca);

    }

}



int main(void){

    ll N, u, v;

    cin>>N>>u>>v;

    rep(i, N-1){

        ll A, B;

        cin>>A>>B;

        node[A-1].chi.push_back(B-1);

        node[B-1].chi.push_back(A-1);

    }

    dfsT(u-1, 0, -1);

    dfsA(v-1, 0, -1);

    ll Maxim=0;

    rep(i, N){

        if(node[i].depthA-node[i].depthT>=0){

            ll ans=((node[i].depthA-node[i].depthT)%2==0 ? node[i].depthA-1 : node[i].depthA-1);

            

            Maxim=max(Maxim, ans);

        }

    }

    cout<<Maxim<<endl;

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

/* typedef */

typedef long long ll;

typedef pair<int, int> pii;

/* constant */

const int INF = 1 << 30;

const ll LINF = 1LL << 50;

const int NIL = -1;

const int MAX = 100005;

const int mod = 1000000007;

const double pi = 3.141592653589;

/* global variables */

vector<vector<int> > G(MAX, vector<int>());

/* function */

void bfs(int st, vector<int>& d) {

    queue<int> q;

    q.push(st);

    d[st] = 0;

    while (!q.empty()) {

        int from = q.front(); q.pop();

        for (int to : G[from]) {

            if (d[to] != NIL) continue;

            d[to] = d[from] + 1;

            q.push(to);

        }

    }

}

/* main */

int main(){

    int N, A, T;

    cin >> N >> T >> A;

    T--, A--;

    int u, v;

    for (int i = 0; i < N - 1; i++) {

        cin >> u >> v;

        u--, v--;

        G[v].push_back(u);

        G[u].push_back(v);

    }



    vector<int> disA(MAX, NIL), disT(MAX, NIL);

    bfs(T, disT);

    bfs(A, disA);



    int ans = 0;

    for (int i = 0; i < N; i++) {

        if (disT[i] >= disA[i]) continue;

        ans = max(ans, disT[i] + max(0, disA[i] - disT[i] - 1));

    }

    cout << ans << '\n';

}


// Faster C++ solution for the same problem (measured speedup: 1.2652205349776646x):
#include <bits/stdc++.h>

using namespace std;

/* typedef */

typedef long long ll;

typedef pair<int, int> pii;

/* constant */

const int INF = 1 << 30;

const ll LINF = 1LL << 50;

const int NIL = -1;

const int MAX = 100005;

const int mod = 1000000007;

const double pi = 3.141592653589;

/* global variables */

int N;

vector<vector<int>> G(MAX, vector<int>());

/* function */

vector<int> bfs(int st) {

    vector<int> dist(N, NIL);

    queue<int> q;

    q.push(st);

    dist[st] = 0;

    while (q.size()) {

        int from = q.front();

        q.pop();

        for (int to :G[from]) {

            if (dist[to] != NIL) continue;

            dist[to] = dist[from] + 1;

            q.push(to);

        }

    }

    return dist;

}

/* main */

int main(){

    int u, v;

    cin >> N >> u >> v;

    u--, v--;

    for (int i = 0; i < N-1; i++) {

        int s, t; cin >> s >> t;

        s--, t--;

        G[s].push_back(t);

        G[t].push_back(s);

    }

    vector<int> distTk = bfs(u);

    vector<int> distAO = bfs(v);

    int mx = 0;

    for (int i = 0; i < N; i++) {

        if (distTk[i] < distAO[i]) {

            if (mx < distAO[i]) {

                mx = distAO[i];

            }

        }

    }

    int ans = mx - 1;

    cout << ans << '\n';

}
// Slower C++ solution:
#include<iostream>

#include<vector>

#include<set>

#include<queue>

using namespace std;



vector<int> v[100000], d(100000);

vector<bool> vis(100000, 0);



void dfs(int x, int dep){

    d[x] = dep;

    vis[x] = true;

    for(int y : v[x]){

        if(!vis[y]) dfs(y, dep+1);

    }

}



int main(){

    int n, a, b;

    cin >> n >> a >> b;

    a--, b--;

    for(int i = 0; i < n-1; i++){

        int x, y;

        cin >> x >> y;

        x--, y--;

        v[x].push_back(y);

        v[y].push_back(x);

    }

    dfs(a, 0);

    set<int> dist[n+5];

    for(int i = 0; i < n; i++)  if(i != b)  dist[d[i]].insert(i);

    int ans = 0;

    vector<bool> no(n, 0);

    queue<int> aoki;

    aoki.push(b);

    no[b] = true;

    set<int> even, odd;

    even.insert(a);

    while(true){

        // cout << ans << endl;

        // cout << "even ";

        // for(int x : even)   cout << x << " ";

        // cout << endl;

        // cout << "odd ";

        // for(int x : odd)   cout << x << " ";

        // cout << endl;



        for(int x : dist[ans+1]){

            if(no[x]) continue;

            if((ans+1)%2==0)    even.insert(x);

            else                odd.insert(x);

        }



        bool judge = false;

        if((ans+1)%2 == 0)  judge = even.empty();

        else                judge = odd.empty();

        if(judge){

            cout << ans << endl;

            return 0;

        }

        ans++;

        queue<int> naoki;

        while(!aoki.empty()){

            int x = aoki.front();   aoki.pop();

            for(int next : v[x]){

                if(no[next])  continue;

                no[next] = true;

                naoki.push(next);

                if(d[next]%2 == 0)   even.erase(next);

                else                 odd.erase(next);

            }

        }

        if(ans%2 == 1)      judge = odd.empty();

        else                judge = even.empty();

        if(judge){

            cout << ans << endl;

            return 0;

        }

        aoki = naoki;

    }

}

// Faster C++ solution for the same problem (measured speedup: 3.9248000289576734x):
#include<iostream>

#include<vector>

#include<functional>

using namespace std;



int main(){

    int n, a, b;

    cin >> n >> a >> b;

    a--, b--;

    vector<int> v[n];

    for(int i = 0; i < n-1; i++){

        int x, y;

        cin >> x >> y;

        x--, y--;

        v[x].push_back(y);

        v[y].push_back(x);

    }

    function<void(vector<int>&,int,int,int)> f = [&](vector<int> &d, int x, int par, int dep){

        d[x] = dep;

        for(int y : v[x]){

            if(y != par)    f(d, y, x, dep+1);

        }

    };

    vector<int> tak(n), aoki(n);

    f(tak, a, -1, 0);

    f(aoki, b, -1, 0);

    int ret = 0;

    for(int i = 0; i < n; i++){

        if(tak[i] < aoki[i])    ret = max(ret, aoki[i]-1);

    }

    cout << ret << endl;

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



int a[100005],b[100005],c[100005];

vector<int>d[100006];

 

void dfs(int v,int s) {

	a[v]=a[s]+1;

	b[v]=1;

	c[v]=s;

	for(auto x:d[v]) {

		if(x==s) continue;

		dfs(x,v);

		b[v]=max(b[v],b[x]+1);

	}

	

}

int main(){

    int n,u,v;

    cin>>n>>u>>v;

	for(int i=1;i<n;i++) {

		int x,y;

		cin>>x>>y;

		d[x].push_back(y);

		d[y].push_back(x);

	}

	dfs(v,0);

	int ans=-1;

	int dis=a[u]-a[v];

	

	dis=(dis-1)>>1;

//	cout<<dis<<endl;

	while(dis--){ 

	    u=c[u];

	}

	if(d[u].size()==1) 

	     ans=a[u]-2;

	else 

	    ans=b[u]+a[u]-3;

	    

	cout<<ans<<endl;

	



}


// Faster C++ solution for the same problem (measured speedup: 18.36148881397788x):
#include <cstdio>

#include <cmath>

using namespace std;

const int N=1e5+5;

const int E=N<<1;

const int mod=1e9+7;

int n,u,v;

int a[N],b[N];

int d1[N],d2[N];

int h[N],nx[E],to[E];

int ec;

int ans;

void ae(int u,int v)

{

	ec++;

	nx[ec]=h[u];

	to[ec]=v;

	h[u]=ec;

}

void dfs(int u,int f,int d[])

{

	d[u]=d[f]+1;

	for (int i=h[u];i;i=nx[i])

		if (to[i]!=f)

			dfs(to[i],u,d);

}

int main()

{

	scanf("%d%d%d",&n,&u,&v);

	for (int i=1;i<n;i++)

	{

		scanf("%d%d",&a[i],&b[i]);

		ae(a[i],b[i]);

		ae(b[i],a[i]);

	}

	dfs(u,0,d1);

	dfs(v,0,d2);

	for (int i=1;i<=n;i++)

		if (d1[i]<d2[i]&&d2[i]-2>ans)

			ans=d2[i]-2;

	printf("%d\n",ans);

	return 0;

}
// Slower C++ solution:
#include "bits/stdc++.h"

using namespace std;

#define ll long long int

#define rep(i,n) for( int i = 0; i < n; i++ )

#define rrep(i,n) for( int i = n; i >= 0; i-- )

#define REP(i,s,t) for( int i = s; i <= t; i++ )

#define RREP(i,s,t) for( int i = s; i >= t; i-- )

#define dump(x)  cerr << #x << " = " << (x) << endl;

#define INF 2000000000

#define mod 1000000007

#define INF2 1000000000000000000



vector<int> G[200010];

int L[2][200010];





void dfs(int T, int V, int cost) {

    //cout << T << " " <<V << " " << cost << endl;

	L[T][V] = cost;

	for (auto to : G[V]){

		if (L[T][to] != INF) continue;

        if (T == 0)

		    dfs(T, to, cost + 1);

        else if (T == 1 && L[1][V] < L[0][V] && L[1][V] + 1 < L[0][to])

            dfs(T, to, cost + 1);

	}

}



int main(void)

{

    cin.tie(0);

    ios::sync_with_stdio(false);



	int N, u, v;

	cin >> N >> u >> v;

    u--; v--;

	rep(i, N - 1) {

		int a, b;

		cin >> a >> b;

        a--; b--;

		G[a].push_back(b);

		G[b].push_back(a);

	}

	rep(i, 2) rep(j, 200010) L[i][j] = INF;

	dfs(0, v, 0);

	dfs(1, u, 0);

    int ans = 0;

    rep(i, N) {

        //cout << L[0][i] << " " << L[1][i] << endl;

        if (L[0][i] > L[1][i])

            ans = max(ans, L[0][i] - 1);

    }

    cout << ans << endl;



    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.3310889519148876x):
#include <iostream>

#include <fstream>

#include <set>

#include <map>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <functional>

#include <algorithm>

#include <climits>

#include <cmath>

#include <iomanip>

using namespace std;

#define ll long long int

#define rep(i,n) for( int i = 0; i < n; i++ )

#define rrep(i,n) for( int i = n; i >= 0; i-- )

#define REP(i,s,t) for( int i = s; i <= t; i++ )

#define RREP(i,s,t) for( int i = s; i >= t; i-- )

#define dump(x)  cerr << #x << " = " << (x) << endl;

#define INF 2000000000

#define mod 1000000007

#define INF2 1000000000000000000

vector<int> G[100010];

int d[2][100010];

void dfs(int x, int c, int p = -1, int depth = 0) {

    d[c][x] = depth;

    for(auto to: G[x]) {

        if(to == p) continue;

        if(c == 0)

            dfs(to, c, x, depth + 1);

        else if(d[0][x] >= depth + 1) {

            dfs(to, c, x, depth + 1);

        }

    }

}



int main(void)

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    int N, u, v;

    cin >> N >> u >> v;

    u--; v--;

    rep(i, N) d[1][i] = INF;

    rep(i, N - 1) {

        int a, b;

        cin >> a >> b;

        a--; b--;

        G[a].push_back(b);

        G[b].push_back(a);

    }

   dfs(v, 0); dfs(u, 1); 

    int ans = 0;

    rep(i, N) {

        //cout << "*" << d[0][i] << " " << d[1][i] << endl;

        if(d[1][i] != INF) ans = max(ans, d[0][i] - 1);

    }

    cout << ans << endl;





    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

     

using namespace std;



map <int,double> dp[3000];



int main(void)

{

	cin.tie(0);

	ios::sync_with_stdio(false);



	int n;

	double t;

	vector <double> p;



	cin >> n;

	for(int i=0;i<n;i++)

	{

		cin >> t;

		p.push_back(t);

	}



	dp[0][0] = 1;

	for(int i=0;i<n;i++)

	{

		for(auto it : dp[i])

		{

			dp[i+1][it.first - 1] += it.second*(1 - p[i]);

			dp[i+1][it.first + 1] += it.second*(p[i]);

		}

	}



	double res = 0;



	for(auto it : dp[n])

	{

		if(it.first > 0)

		{

			res += it.second;

		}

	}



	cout << fixed;

	cout.precision(9);

	

	cout << res << '\n';



	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.1455466827780787x):
#include <bits/stdc++.h>

     

using namespace std;



double dp[3010][3010];



int main(void)

{

	cin.tie(0);

	ios::sync_with_stdio(false);



	int n;

	double t;

	vector <double> p;



	cin >> n;

	for(int i=0;i<n;i++)

	{

		cin >> t;

		p.push_back(t);

	}



	dp[0][0] = 1 - p[0];

	dp[0][1] = p[0];



	for(int i=1;i<n;i++)

	{

		for(int j=0;j<=n;j++)

		{

			dp[i][j] += (dp[i-1][j])*(1 - p[i]);

			dp[i][j+1] += (dp[i-1][j])*(p[i]);

		}

	}



	double res = 0;



	for(int i=(n/2)+1;i<=n;i++)

	{

		res += dp[n-1][i];

	}



	cout << fixed;

	cout.precision(9);



	cout << res << '\n';



	return 0;

}
// Slower C++ solution:
#include<stdio.h>

#include<string.h>

#include<time.h>

#include<math.h>

#include<stdlib.h>

#include<iostream>

#include<iomanip>

#include<utility>

#include<algorithm>

#include<stack>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define fi first

#define sec second

#define pb push_back

#define mp make_pair

#define rep(a,b,c) for(int a=1;a<=b;a+=c)

#define repp(a,b,c,d) for(int a=b;a<=c;a+=d)



const double PI=acos(-1);

const double EPS=1e-12;

const int MOD=1e9+7;

const int INF=1<<30;





using namespace std;



double dat[3005][1505][2];

double p[3005];

int in;



double prob(int pos,int cnt,int phase){

	if(2*cnt>in)return dat[pos][cnt][phase]=0.0;

	if(pos==in)return dat[pos][cnt][phase]=1.0;

	if(dat[pos][cnt][phase]>-EPS)return dat[pos][cnt][phase];

	double temp=p[pos+1]*prob(pos+1,cnt,0)+(1.0-p[pos+1])*prob(pos+1,cnt+1,1);

	return dat[pos][cnt][phase]=temp;

}



int main(){

	//ios::sync_with_stdio(false);cin.tie(NULL);	cout.tie(NULL);

	cin>>in;

	double res;

	repp(j,0,1500,1){

		repp(k,0,1,1){

			dat[0][j][k]=-1e5;

		}

	}

	rep(i,in,1){

		cin>>p[i];

		repp(j,0,1500,1){

			repp(k,0,1,1){

				dat[i][j][k]=-1e5;

			}

		}

	}

	cout<<fixed<<setprecision(10)<<prob(0,0,0)<<endl;

	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 1.1148525253146684x):
#include<bits/stdc++.h>

#define INF 1073741824

#define ll long long

#define PI (2*acos(0.0))

#define p1(n) printf("showing %d\n",n)

#define p2(m,n) printf("showing %d %d\n",m,n)

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL);

#define mp make_pair

#define pb push_back

#define pii pair<int,int>

#define pll pair<ll,ll>

#define x first

#define y second

#define on(val,pos) val|(1<<pos)

#define off(val,pos) val&(~(1<<pos))

#define check(val,pos) (val&(1<<pos))



//first four adjacent,second four corner

//int row[8]={0,-1,0,1,1,-1,-1,1};

//int col[8]={-1,0,1,0,-1,-1,1,1};

using namespace std;



int main(){

    ll i,j,k,n,m,t=0,cnt,test;

    //freopen("000input.txt","r",stdin);

    cin>>n;

    double dp[n+5],head;

    memset(dp,0,sizeof dp);

    dp[0]=1;

    for(i=0;i<n;i++){

        scanf("%lf",&head);

        for(int j=i+1;j>=0;j--){

            dp[j]=(j==0?0:dp[j-1]*head)+dp[j]*(1-head);

        }

    }

    double ans=0;

    for(i=n/2+1;i<=n;i++){

        ans+=dp[i];

    }

    printf("%.9lf",ans);

    //free();   //if pointer array

    return 0;

}
// Slower C++ solution:
#include<stdio.h>

#include<string.h>

#include<time.h>

#include<math.h>

#include<stdlib.h>

#include<iostream>

#include<iomanip>

#include<utility>

#include<algorithm>

#include<stack>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define fi first

#define sec second

#define pb push_back

#define mp make_pair

#define rep(a,b,c) for(int a=1;a<=b;a+=c)

#define repp(a,b,c,d) for(int a=b;a<=c;a+=d)



const double PI=acos(-1);

const double EPS=1e-12;

const int MOD=1e9+7;

const int INF=1<<30;





using namespace std;



double dat[3005][1505][2];

double p[3005];

int in;



double prob(int pos,int cnt,int phase){

	if(2*cnt>in)return dat[pos][cnt][phase]=0.0;

	if(pos==in)return dat[pos][cnt][phase]=1.0;

	if(dat[pos][cnt][phase]>-EPS)return dat[pos][cnt][phase];

	double temp=p[pos+1]*prob(pos+1,cnt,0)+(1.0-p[pos+1])*prob(pos+1,cnt+1,1);

	return dat[pos][cnt][phase]=temp;

}



int main(){

	//ios::sync_with_stdio(false);cin.tie(NULL);	cout.tie(NULL);

	cin>>in;

	double res;

	repp(j,0,1500,1){

		repp(k,0,1,1){

			dat[0][j][k]=-1e5;

		}

	}

	rep(i,in,1){

		cin>>p[i];

		repp(j,0,1500,1){

			repp(k,0,1,1){

				dat[i][j][k]=-1e5;

			}

		}

	}

	cout<<fixed<<setprecision(10)<<prob(0,0,0)<<endl;

	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 1.1144455575019347x):
//概率dp 

#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;



const int maxn=3050;

double p[maxn];

double dp[maxn][maxn];



int main()

{

	int n;

	cin>>n;

    for(int i = 1;i<=n;++i)

        cin>>p[i];

    

    dp[1][1]=p[1];

    dp[1][0]=1.0000000-p[1];



    for(int i = 2;i<=n;++i){

        for(int j=0;j<=i;j++){

            if(j==0){

                dp[i][j]=dp[i-1][j]*(1.00000-p[i]);

                continue;

            }

            dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1.0000-p[i]);

        }

    }

    double ans=0.0000000000000000000;

    for(int i=(n+1)/2;i<=n;i++)

    {

        ans+=dp[n][i];

    }

    printf("%.10lf\n",ans);

    return 0;

}