#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
template<typename T>
struct DP2
{
const int N1, N2;
vector<T> data;
DP2(int N1, int N2, const T& t = T())
: N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<28)); }
T& operator()(int i1, int i2)
{ return data[ (i1*N2)+i2 ]; }
void swap(DP2& rhs)
{ data.swap(rhs.data); }
};
template<typename T>
struct DP3
{
int N1, N2, N3;
vector<T> data;
DP3(int N1, int N2, int N3, const T& t = T())
: N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<28)); }
T& operator()(int i1, int i2, int i3)
{ return data[ ((i1*N2)+i2)*N3+i3 ]; }
void swap(DP3& rhs)
{ data.swap(rhs.data); }
};
class WheelofFortune { public:
double maxExpectedValue(int N, vector <int> s)
{
const int SCORE_MAX = s.size();
// wlog Alice always declares "0".
// ps(i+1, a) := probability that "0" is covered |a| times after i-th try.
// es(i+1, a) := expected score distrobution
DP2<double> ps(s.size()+1, SCORE_MAX+1, 0.0);
DP3<double> es(s.size()+1, SCORE_MAX+1, N, 0.0);
ps(0, 0) = 1.0;
vector<vector<double>> memo1(N+1, vector<double>(N, -1));
vector<vector<double>> memo2(N+1, vector<double>(N, -1));
for(int i=0; i<s.size(); ++i)
for(int a=0; a<=SCORE_MAX; ++a) {
const double q = double(s[i])/N;
ps(i+1, a) = (1-q) * ps(i, a) + q * (a?ps(i, a-1):0.0);
for(int cell=0; cell<N; ++cell) {
double zero_t = zero_cover_times(N, s[i], cell, memo1);
double non_zero_t = non_zero_cover_times(N, s[i], cell, memo2);
es(i+1, a, cell) =
(a?ps(i, a-1):0.0) * q * (es(i, a-1, cell) + double(zero_t))
+ ps(i, a) * (1-q) * (es(i, a, cell) + double(non_zero_t));
}
}
double ans = 0.0;
for(int a=0; a<=SCORE_MAX; ++a) if(ps(s.size(), a)) {
// Under the condition that "0" is covered exactly |a| times,
// what is the optimal choice for Bob?
// Bob takes the max expected score cell (but 0).
double bob_best = 0.0;
for(int cell=1; cell<N; ++cell)
bob_best = max(bob_best, es(s.size(), a, cell));
// accumulate
ans += ps(s.size(), a) * (a+bob_best);
}
return ans;
}
double zero_cover_times(int N, int s, int cell, vector<vector<double>>& memo)
{
if(memo[s][cell] >= 0)
return memo[s][cell];
int cnt = 0, tot = 0;
for(int b=0; b<N; ++b) {
if(covers(N, b, s, 0))
++tot;
if(covers(N, b, s, 0) && covers(N, b, s, cell))
++cnt;
}
return memo[s][cell] = double(cnt)/tot;
}
double non_zero_cover_times(int N, int s, int cell, vector<vector<double>>& memo)
{
if(memo[s][cell] >= 0)
return memo[s][cell];
int cnt = 0, tot=0;
for(int b=0; b<N; ++b) {
if(!covers(N, b, s, 0))
++tot;
if(!covers(N, b, s, 0) && covers(N, b, s, cell))
++cnt;
}
return memo[s][cell] = double(cnt)/tot;
}
bool covers(int N, int b, int s, int c)
{
if(b<=c && c<=b+s-1)
return true;
if(0<=c && c<=b+s-1-N)
return true;
return false;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const double& Expected, const double& Received) {
bool ok = (abs(Expected - Received) < 1e-9);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, WheelofFortune().maxExpectedValue(N, s));}
int main(){
CASE(0)
int N = 4;
int s_[] = {2};
vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_));
double _ = 1.25;
END
CASE(1)
int N = 6;
int s_[] = {1,1,1,1,1,1};
vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_));
double _ = 2.0000000000000004;
END
CASE(2)
int N = 20;
int s_[] = {1,20,1,20,1};
vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_));
double _ = 4.299999999999999;
END
CASE(3)
int N = 10;
int s_[] = {3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7,9,5};
vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_));
double _ = 31.973469385798197;
END
CASE(4)
int N = 15;
int s_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_));
double _ = 16.691531334568044;
END
/*
CASE(5)
int N = ;
int s_[] = ;
vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_));
double _ = ;
END
CASE(6)
int N = ;
int s_[] = ;
vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_));
double _ = ;
END
*/
}
// END CUT HERE