Artifact Content
Not logged in

Artifact a5d1138e452eadf3c42774fa64d479269b2ea418


#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