219b0aef.cpp

#include <bits/stdc++.h>
#define alive std::cout << "$LINE @" << __LINE__ << " ALIVE" << std::endl
#define watch(var) std::cout << "$ LINE @" << __LINE__ << " FUN @" << __FUNCTION__ \
                             << " VAR @" << (#var) << ": " << (var) << std::endl

using namespace std;

typedef int i32;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
typedef double f64;
typedef long double f128;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    x = 0;
    bool neg = false;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

const int N = 20 + 5;
const int M = 4;

int n;

f64 p[M], pw[M][N];
u64 fac[N];

inline void prepare()
{
    fac[0] = 1ULL;
    for (int i = 1; i <= n; ++i)
    {
        fac[i] = fac[i - 1] * (u64)i;
    }
    for (int k = 0; k < M; ++k)
    {
        f64 *pw = ::pw[k], &p = ::p[k];
        pw[0] = 1.0;
        for (int i = 1; i <= n; ++i)
        {
            pw[i] = pw[i - 1] * p;
        }
    }
}

int main()
{
    read(n);
    for (int i = 0; i < M; ++i)
    {
        scanf("%lf", &p[i]);
    }

    prepare();

    typedef pair<f64, u64> pfu;

    priority_queue<pfu, vector<pfu>, greater<pfu>> q;

    for (int a = 0; a <= n; ++a)
    {
        for (int b = 0, max = n - a; b <= max; ++b)
        {
            for (int c = 0, max = n - a - b; c <= max; ++c)
            {
                int d = n - a - b - c;
                q.emplace(pw[0][a] * pw[1][b] * pw[2][c] * pw[3][d],
                          fac[n] / fac[a] / fac[b] / fac[c] / fac[d]);
            }
        }
    }

    f64 ans = 0.0;

    while (q.size() > 1UL)
    {
        pfu u = q.top();
        q.pop();
        if (u.second > 1ULL)
        {
            ans += u.first * (u.second & (~1ULL));
            q.emplace(u.first * 2.0, u.second >> 1);
            u.second &= 1ULL;
        }
        if (u.second == 1ULL)
        {
            pfu v = q.top();
            q.pop();
            ans += u.first + v.first;
            q.emplace(u.first + v.first, 1ULL);
            if (v.second > 1ULL)
            {
                q.emplace(v.first, v.second - 1ULL);
            }
        }
    }

    printf("%.8f\n", ans);
    return 0;
}