01b4c419a6 2013-02-19        kinaba: #include <iostream>
01b4c419a6 2013-02-19        kinaba: #include <sstream>
01b4c419a6 2013-02-19        kinaba: #include <iomanip>
01b4c419a6 2013-02-19        kinaba: #include <vector>
01b4c419a6 2013-02-19        kinaba: #include <string>
01b4c419a6 2013-02-19        kinaba: #include <map>
01b4c419a6 2013-02-19        kinaba: #include <set>
01b4c419a6 2013-02-19        kinaba: #include <algorithm>
01b4c419a6 2013-02-19        kinaba: #include <numeric>
01b4c419a6 2013-02-19        kinaba: #include <iterator>
01b4c419a6 2013-02-19        kinaba: #include <functional>
01b4c419a6 2013-02-19        kinaba: #include <complex>
01b4c419a6 2013-02-19        kinaba: #include <queue>
01b4c419a6 2013-02-19        kinaba: #include <stack>
01b4c419a6 2013-02-19        kinaba: #include <cmath>
01b4c419a6 2013-02-19        kinaba: #include <cassert>
01b4c419a6 2013-02-19        kinaba: using namespace std;
01b4c419a6 2013-02-19        kinaba: typedef long long LL;
01b4c419a6 2013-02-19        kinaba: typedef long double LD;
01b4c419a6 2013-02-19        kinaba: typedef complex<LD> CMP;
01b4c419a6 2013-02-19        kinaba: 
01b4c419a6 2013-02-19        kinaba: class CentaurCompany { public:
01b4c419a6 2013-02-19        kinaba: 	struct State {
01b4c419a6 2013-02-19        kinaba: 		int nNode;
01b4c419a6 2013-02-19        kinaba: 		vector< vector< vector<double> > > th; // nHumanNodes -> nEq -> nEq -> prob
01b4c419a6 2013-02-19        kinaba: 		vector< vector< vector<double> > > tk; // nHumanNodes -> nEq -> nEq -> prob
01b4c419a6 2013-02-19        kinaba: 	};
01b4c419a6 2013-02-19        kinaba: 
01b4c419a6 2013-02-19        kinaba: 	double getvalue(vector <int> a, vector <int> b)
01b4c419a6 2013-02-19        kinaba: 	{
01b4c419a6 2013-02-19        kinaba: 		int N = a.size() + 1;
01b4c419a6 2013-02-19        kinaba: 		vector< vector<int> > G(N);
01b4c419a6 2013-02-19        kinaba: 		for(int i=0; i<a.size(); ++i) {
01b4c419a6 2013-02-19        kinaba: 			G[a[i]-1].push_back(b[i]-1);
01b4c419a6 2013-02-19        kinaba: 			G[b[i]-1].push_back(a[i]-1);
01b4c419a6 2013-02-19        kinaba: 		}
01b4c419a6 2013-02-19        kinaba: 
01b4c419a6 2013-02-19        kinaba: 		double e = 0.0;
01b4c419a6 2013-02-19        kinaba: 		State s = rec(-1, 0, G);
01b4c419a6 2013-02-19        kinaba: 		for(int ah=0; ah<=s.nNode; ++ah)
01b4c419a6 2013-02-19        kinaba: 		for(int ahe=0; ahe<=ah; ++ahe)
01b4c419a6 2013-02-19        kinaba: 		for(int ake=0; ake<=(s.nNode-ah); ++ake)
01b4c419a6 2013-02-19        kinaba: 		{
01b4c419a6 2013-02-19        kinaba: 			int ak = s.nNode - ah;
01b4c419a6 2013-02-19        kinaba: 			{
01b4c419a6 2013-02-19        kinaba: 				double p = s.th[ah][ahe][ake];
01b4c419a6 2013-02-19        kinaba: 				e += p * (max(2*(ahe-1)-ah,0)+max(2*(ake-1)-ak,0));
01b4c419a6 2013-02-19        kinaba: 			}
01b4c419a6 2013-02-19        kinaba: 			{
01b4c419a6 2013-02-19        kinaba: 				double p = s.tk[ah][ahe][ake];
01b4c419a6 2013-02-19        kinaba: 				e += p * (max(2*(ahe-1)-ah,0)+max(2*(ake-1)-ak,0));
01b4c419a6 2013-02-19        kinaba: 			}
01b4c419a6 2013-02-19        kinaba: 		}
01b4c419a6 2013-02-19        kinaba: 		return e;
01b4c419a6 2013-02-19        kinaba: 	}
01b4c419a6 2013-02-19        kinaba: 
01b4c419a6 2013-02-19        kinaba: 	State rec(int p, int v, const vector<vector<int> >& G)
01b4c419a6 2013-02-19        kinaba: 	{
01b4c419a6 2013-02-19        kinaba: 		State s = {1,
01b4c419a6 2013-02-19        kinaba: 			vector< vector< vector<double> > >(2, vector< vector<double> >(2, vector<double>(2))),
01b4c419a6 2013-02-19        kinaba: 			vector< vector< vector<double> > >(2, vector< vector<double> >(2, vector<double>(2)))
01b4c419a6 2013-02-19        kinaba: 		};
01b4c419a6 2013-02-19        kinaba: 		s.th[1][1][0] = 0.5;
01b4c419a6 2013-02-19        kinaba: 		s.tk[0][0][1] = 0.5;
01b4c419a6 2013-02-19        kinaba: 		for(int i=0; i<G[v].size(); ++i) if(G[v][i] != p)
01b4c419a6 2013-02-19        kinaba: 			s = combine(s, rec(v, G[v][i], G));
01b4c419a6 2013-02-19        kinaba: 		return s;
01b4c419a6 2013-02-19        kinaba: 	}
01b4c419a6 2013-02-19        kinaba: 
01b4c419a6 2013-02-19        kinaba: 	State combine(const State& a, const State& b)
01b4c419a6 2013-02-19        kinaba: 	{
01b4c419a6 2013-02-19        kinaba: 		int N = a.nNode + b.nNode;
01b4c419a6 2013-02-19        kinaba: 		State s = {N,
01b4c419a6 2013-02-19        kinaba: 			vector< vector< vector<double> > >(N+1, vector< vector<double> >(N+1, vector<double>(N+1))),
01b4c419a6 2013-02-19        kinaba: 			vector< vector< vector<double> > >(N+1, vector< vector<double> >(N+1, vector<double>(N+1)))
01b4c419a6 2013-02-19        kinaba: 		};
01b4c419a6 2013-02-19        kinaba: 		for(int ah=0; ah<=a.nNode; ++ah)
01b4c419a6 2013-02-19        kinaba: 		for(int ahe=0; ahe<=ah; ++ahe)
01b4c419a6 2013-02-19        kinaba: 		for(int ake=0; ake<=(a.nNode-ah); ++ake)
01b4c419a6 2013-02-19        kinaba: 		for(int bh=0; bh<=b.nNode; ++bh)
01b4c419a6 2013-02-19        kinaba: 		for(int bhe=0; bhe<=bh; ++bhe)
01b4c419a6 2013-02-19        kinaba: 		for(int bke=0; bke<=(b.nNode-bh); ++bke) {
01b4c419a6 2013-02-19        kinaba: 			if(ahe+bhe!=0)
01b4c419a6 2013-02-19        kinaba: 			s.th[ah+bh][ahe+bhe-1][ake+bke] += a.th[ah][ahe][ake]*b.th[bh][bhe][bke];
01b4c419a6 2013-02-19        kinaba: 			s.th[ah+bh][ahe+bhe][ake+bke] += a.th[ah][ahe][ake]*b.tk[bh][bhe][bke];
01b4c419a6 2013-02-19        kinaba: 			s.tk[ah+bh][ahe+bhe][ake+bke] += a.tk[ah][ahe][ake]*b.th[bh][bhe][bke];
01b4c419a6 2013-02-19        kinaba: 			if(ake+bke!=0)
01b4c419a6 2013-02-19        kinaba: 			s.tk[ah+bh][ahe+bhe][ake+bke-1] += a.tk[ah][ahe][ake]*b.tk[bh][bhe][bke];
01b4c419a6 2013-02-19        kinaba: 		}
01b4c419a6 2013-02-19        kinaba: 		return s;
01b4c419a6 2013-02-19        kinaba: 	}
01b4c419a6 2013-02-19        kinaba: };
01b4c419a6 2013-02-19        kinaba: 
01b4c419a6 2013-02-19        kinaba: // BEGIN CUT HERE
01b4c419a6 2013-02-19        kinaba: #include <ctime>
01b4c419a6 2013-02-19        kinaba: double start_time; string timer()
01b4c419a6 2013-02-19        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
01b4c419a6 2013-02-19        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
01b4c419a6 2013-02-19        kinaba:  { os << "{ ";
01b4c419a6 2013-02-19        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
01b4c419a6 2013-02-19        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
01b4c419a6 2013-02-19        kinaba: void verify_case(const double& Expected, const double& Received) {
01b4c419a6 2013-02-19        kinaba:  bool ok = (abs(Expected - Received) < 1e-9);
01b4c419a6 2013-02-19        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
01b4c419a6 2013-02-19        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
01b4c419a6 2013-02-19        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
01b4c419a6 2013-02-19        kinaba: #define END	 verify_case(_, CentaurCompany().getvalue(a, b));}
01b4c419a6 2013-02-19        kinaba: int main(){
01b4c419a6 2013-02-19        kinaba: 
01b4c419a6 2013-02-19        kinaba: CASE(0)
01b4c419a6 2013-02-19        kinaba: 	int a_[] = {1};
01b4c419a6 2013-02-19        kinaba: 	  vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
01b4c419a6 2013-02-19        kinaba: 	int b_[] = {2};
01b4c419a6 2013-02-19        kinaba: 	  vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
01b4c419a6 2013-02-19        kinaba: 	double _ = 0.0;
01b4c419a6 2013-02-19        kinaba: END
01b4c419a6 2013-02-19        kinaba: CASE(1)
01b4c419a6 2013-02-19        kinaba: 	int a_[] = {1,1,1};
01b4c419a6 2013-02-19        kinaba: 	  vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
01b4c419a6 2013-02-19        kinaba: 	int b_[] = {2,3,4};
01b4c419a6 2013-02-19        kinaba: 	  vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
01b4c419a6 2013-02-19        kinaba: 	double _ = 0.125;
01b4c419a6 2013-02-19        kinaba: END
01b4c419a6 2013-02-19        kinaba: CASE(2)
01b4c419a6 2013-02-19        kinaba: 	int a_[] = {1,2,3,2,2};
01b4c419a6 2013-02-19        kinaba: 	  vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
01b4c419a6 2013-02-19        kinaba: 	int b_[] = {2,3,4,5,6};
01b4c419a6 2013-02-19        kinaba: 	  vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
01b4c419a6 2013-02-19        kinaba: 	double _ = 0.375;
01b4c419a6 2013-02-19        kinaba: END
01b4c419a6 2013-02-19        kinaba: CASE(3)
01b4c419a6 2013-02-19        kinaba: 	int a_[] = {1,2,3,4,5,6,7,8,9};
01b4c419a6 2013-02-19        kinaba: 	  vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
01b4c419a6 2013-02-19        kinaba: 	int b_[] = {2,3,4,5,6,7,8,9,10};
01b4c419a6 2013-02-19        kinaba: 	  vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
01b4c419a6 2013-02-19        kinaba: 	double _ = 0.41796875;
01b4c419a6 2013-02-19        kinaba: END
01b4c419a6 2013-02-19        kinaba: CASE(4)
01b4c419a6 2013-02-19        kinaba: 	int a_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
01b4c419a6 2013-02-19        kinaba: 	  vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
01b4c419a6 2013-02-19        kinaba: 	int b_[] = {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36};
01b4c419a6 2013-02-19        kinaba: 	  vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
01b4c419a6 2013-02-19        kinaba: 	double _ = 15.500000001076842;
01b4c419a6 2013-02-19        kinaba: END
01b4c419a6 2013-02-19        kinaba: CASE(5)
01b4c419a6 2013-02-19        kinaba: 	int a_[] = {10, 7, 2, 5, 6, 2, 4, 9, 7};
01b4c419a6 2013-02-19        kinaba: 	  vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
01b4c419a6 2013-02-19        kinaba: 	int b_[] = {8, 10, 10, 4, 1, 6, 2, 2, 3};
01b4c419a6 2013-02-19        kinaba: 	  vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
01b4c419a6 2013-02-19        kinaba: 	double _ = 0.646484375;
01b4c419a6 2013-02-19        kinaba: END
01b4c419a6 2013-02-19        kinaba: CASE(6)
01b4c419a6 2013-02-19        kinaba: 	int a_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35};
01b4c419a6 2013-02-19        kinaba: 	  vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
01b4c419a6 2013-02-19        kinaba: 	int b_[] = {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36};
01b4c419a6 2013-02-19        kinaba: 	  vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
01b4c419a6 2013-02-19        kinaba: 	double _ = -1;
01b4c419a6 2013-02-19        kinaba: END
01b4c419a6 2013-02-19        kinaba: /*
01b4c419a6 2013-02-19        kinaba: CASE(7)
01b4c419a6 2013-02-19        kinaba: 	int a_[] = ;
01b4c419a6 2013-02-19        kinaba: 	  vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
01b4c419a6 2013-02-19        kinaba: 	int b_[] = ;
01b4c419a6 2013-02-19        kinaba: 	  vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
01b4c419a6 2013-02-19        kinaba: 	double _ = ;
01b4c419a6 2013-02-19        kinaba: END
01b4c419a6 2013-02-19        kinaba: */
01b4c419a6 2013-02-19        kinaba: }
01b4c419a6 2013-02-19        kinaba: // END CUT HERE