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