ADDED   SRM/642-U/1A.cpp
Index: SRM/642-U/1A.cpp
==================================================================
--- SRM/642-U/1A.cpp
+++ SRM/642-U/1A.cpp
@@ -0,0 +1,119 @@
+#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;
+
+class WaitingForBus { public:
+	double whenWillBusArrive(vector <int> time, vector <int> prob, int s)
+	{
+		const int WAIT_TIME_MAX = 100000;
+
+		deque<double> p(WAIT_TIME_MAX+1, 0.0);
+		p[0] = 1.0;
+		for(int t=1; t<=s; ++t) {
+			double p0 = p[0];
+			p.pop_front();
+			p.push_back(0.0);
+			for(int i=0; i<time.size(); ++i)
+				p[time[i]-1] += p0 * prob[i] / 100;
+		}
+
+		double ans = 0.0;
+		for(int t=0; t<=WAIT_TIME_MAX; ++t)
+			ans += t * p[t];
+		return ans;
+	}
+};
+
+// 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(_, WaitingForBus().whenWillBusArrive(time, prob, s));}
+int main(){
+
+CASE(0)
+	int time_[] = {5,100};
+	  vector <int> time(time_, time_+sizeof(time_)/sizeof(*time_)); 
+	int prob_[] = {90,10};
+	  vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); 
+	int s = 5; 
+	double _ = 9.5; 
+END
+CASE(1)
+	int time_[] = {5};
+	  vector <int> time(time_, time_+sizeof(time_)/sizeof(*time_)); 
+	int prob_[] = {100};
+	  vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); 
+	int s = 101; 
+	double _ = 4.0; 
+END
+CASE(2)
+	int time_[] = {5,10};
+	  vector <int> time(time_, time_+sizeof(time_)/sizeof(*time_)); 
+	int prob_[] = {50,50};
+	  vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); 
+	int s = 88888; 
+	double _ = 3.666666666666667; 
+END
+CASE(3)
+	int time_[] = {1,2,3,4};
+	  vector <int> time(time_, time_+sizeof(time_)/sizeof(*time_)); 
+	int prob_[] = {10,20,30,40};
+	  vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); 
+	int s = 1000; 
+	double _ = 1.166666666666667; 
+END
+CASE(4)
+	int time_[] = {10,100,1000,10000,100000};
+	  vector <int> time(time_, time_+sizeof(time_)/sizeof(*time_)); 
+	int prob_[] = {90,4,3,2,1};
+	  vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); 
+	int s = 100000; 
+	double _ = 21148.147303578935; 
+END
+/*
+CASE(5)
+	int time_[] = ;
+	  vector <int> time(time_, time_+sizeof(time_)/sizeof(*time_)); 
+	int prob_[] = ;
+	  vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); 
+	int s = ; 
+	double _ = ; 
+END
+CASE(6)
+	int time_[] = ;
+	  vector <int> time(time_, time_+sizeof(time_)/sizeof(*time_)); 
+	int prob_[] = ;
+	  vector <int> prob(prob_, prob_+sizeof(prob_)/sizeof(*prob_)); 
+	int s = ; 
+	double _ = ; 
+END
+*/
+}
+// END CUT HERE

ADDED   SRM/642-U/1C-U.cpp
Index: SRM/642-U/1C-U.cpp
==================================================================
--- SRM/642-U/1C-U.cpp
+++ SRM/642-U/1C-U.cpp
@@ -0,0 +1,196 @@
+#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