4fd800b3a8 2011-02-23 kinaba: #include <iostream> 4fd800b3a8 2011-02-23 kinaba: #include <sstream> 4fd800b3a8 2011-02-23 kinaba: #include <iomanip> 4fd800b3a8 2011-02-23 kinaba: #include <vector> 4fd800b3a8 2011-02-23 kinaba: #include <string> 4fd800b3a8 2011-02-23 kinaba: #include <map> 4fd800b3a8 2011-02-23 kinaba: #include <set> 4fd800b3a8 2011-02-23 kinaba: #include <algorithm> 4fd800b3a8 2011-02-23 kinaba: #include <numeric> 4fd800b3a8 2011-02-23 kinaba: #include <iterator> 4fd800b3a8 2011-02-23 kinaba: #include <functional> 4fd800b3a8 2011-02-23 kinaba: #include <complex> 4fd800b3a8 2011-02-23 kinaba: #include <queue> 4fd800b3a8 2011-02-23 kinaba: #include <stack> 4fd800b3a8 2011-02-23 kinaba: #include <cmath> 4fd800b3a8 2011-02-23 kinaba: #include <cassert> 4fd800b3a8 2011-02-23 kinaba: #include <cstring> 4fd800b3a8 2011-02-23 kinaba: using namespace std; 4fd800b3a8 2011-02-23 kinaba: typedef long long LL; 4fd800b3a8 2011-02-23 kinaba: typedef complex<double> CMP; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: class RoadsOfKingdom { public: 4fd800b3a8 2011-02-23 kinaba: vector< vector<double> > P; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: double getProbability(vector <string> roads) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: P = read_input(roads); 4fd800b3a8 2011-02-23 kinaba: memo = vector<double>(1<<P.size(), -1); 4fd800b3a8 2011-02-23 kinaba: memo0 = vector<double>(P.size()<<P.size(), -1); 4fd800b3a8 2011-02-23 kinaba: memo1 = vector<double>(P.size()<<P.size(), -1); 4fd800b3a8 2011-02-23 kinaba: return prob_tree( (1<<P.size())-1 ); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector< vector<double> > read_input(const vector<string>& R) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int N = R.size(); 4fd800b3a8 2011-02-23 kinaba: vector< vector<double> > P(N, vector<double>(N)); 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<N; ++i) 4fd800b3a8 2011-02-23 kinaba: for(int j=0; j<N; ++j) 4fd800b3a8 2011-02-23 kinaba: P[i][j] = (R[i][j] - '0') / 8.0; 4fd800b3a8 2011-02-23 kinaba: return P; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector<double> memo; 4fd800b3a8 2011-02-23 kinaba: double prob_tree(int S) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: if( memo[S] >= 0 ) 4fd800b3a8 2011-02-23 kinaba: return memo[S]; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // the first and the second smallest IDs in S 4fd800b3a8 2011-02-23 kinaba: int v, w; 4fd800b3a8 2011-02-23 kinaba: for(v=0; (1<<v)<=S; ++v) if( S & 1<<v ) break; 4fd800b3a8 2011-02-23 kinaba: for(w=v+1; (1<<w)<=S; ++w) if( S & 1<<w ) break; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // if |S| < 2 then it always forms a tree 4fd800b3a8 2011-02-23 kinaba: if( (1<<w) > S ) 4fd800b3a8 2011-02-23 kinaba: return memo[S] = 1.0; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // Let's consider v as the "root node" of S, and try all possible "subtrees" T containing w. 4fd800b3a8 2011-02-23 kinaba: // The situation is (other nodes)=v-(T where w in T) 4fd800b3a8 2011-02-23 kinaba: double p = 0.0; 4fd800b3a8 2011-02-23 kinaba: for(int T=S; T; T=(T-1)&S) 4fd800b3a8 2011-02-23 kinaba: if( (T & 1<<w) && !(T & 1<<v) ) 4fd800b3a8 2011-02-23 kinaba: p += prob_tree(T) * prob_tree(S&~T) * prob_separated(T, S&~T&~(1<<v)) * prob_one(v, T); 4fd800b3a8 2011-02-23 kinaba: return memo[S] = p; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: double prob_separated(int S1, int S2) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: double p = 1.0; 4fd800b3a8 2011-02-23 kinaba: for(int v=0; (1<<v)<=S1; ++v) if( S1 & 1<<v ) 4fd800b3a8 2011-02-23 kinaba: p *= prob_zero(v, S2); 4fd800b3a8 2011-02-23 kinaba: return p; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector<double> memo0; 4fd800b3a8 2011-02-23 kinaba: double prob_zero(int v, int S) // 0 connection between v and S 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: const int key = v<<P.size() | S; 4fd800b3a8 2011-02-23 kinaba: if( memo0[key] >= 0 ) return memo0[key]; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: double p = 1.0; 4fd800b3a8 2011-02-23 kinaba: for(int u=0; (1<<u)<=S; ++u) if( S & 1<<u ) 4fd800b3a8 2011-02-23 kinaba: p *= 1.0 - P[v][u]; 4fd800b3a8 2011-02-23 kinaba: return memo0[key] = p; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector<double> memo1; 4fd800b3a8 2011-02-23 kinaba: double prob_one(int v, int S) // exactly 1 connection between v and S 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: const int key = v<<P.size() | S; 4fd800b3a8 2011-02-23 kinaba: if( memo1[key] >= 0 ) return memo1[key]; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: double p = 0.0; 4fd800b3a8 2011-02-23 kinaba: for(int c=0; (1<<c)<=S; ++c) if( S & 1<<c ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: double q = 1.0; 4fd800b3a8 2011-02-23 kinaba: for(int u=0; (1<<u)<=S; ++u) if( S & 1<<u ) 4fd800b3a8 2011-02-23 kinaba: q *= u==c ? P[v][u] : 1-P[v][u]; 4fd800b3a8 2011-02-23 kinaba: p += q; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return memo1[key] = p; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: #include <ctime> 4fd800b3a8 2011-02-23 kinaba: double start_time; string timer() 4fd800b3a8 2011-02-23 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 4fd800b3a8 2011-02-23 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 4fd800b3a8 2011-02-23 kinaba: { os << "{ "; 4fd800b3a8 2011-02-23 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 4fd800b3a8 2011-02-23 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 4fd800b3a8 2011-02-23 kinaba: void verify_case(const double& Expected, const double& Received) { 4fd800b3a8 2011-02-23 kinaba: bool ok = (abs(Expected - Received) < 1e-9); 4fd800b3a8 2011-02-23 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 4fd800b3a8 2011-02-23 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 4fd800b3a8 2011-02-23 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 4fd800b3a8 2011-02-23 kinaba: #define END verify_case(_, RoadsOfKingdom().getProbability(roads));} 4fd800b3a8 2011-02-23 kinaba: int main(){ 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: CASE(0) 4fd800b3a8 2011-02-23 kinaba: string roads_[] = {"04", 4fd800b3a8 2011-02-23 kinaba: "40"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 0.5; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(1) 4fd800b3a8 2011-02-23 kinaba: string roads_[] = {"08", 4fd800b3a8 2011-02-23 kinaba: "80"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 1.0; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(2) 4fd800b3a8 2011-02-23 kinaba: string roads_[] = {"00", 4fd800b3a8 2011-02-23 kinaba: "00"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 0.0; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(3) 4fd800b3a8 2011-02-23 kinaba: string roads_[] = {"088", 4fd800b3a8 2011-02-23 kinaba: "808", 4fd800b3a8 2011-02-23 kinaba: "880"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 0.0; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(4) 4fd800b3a8 2011-02-23 kinaba: string roads_[] = {"044", 4fd800b3a8 2011-02-23 kinaba: "404", 4fd800b3a8 2011-02-23 kinaba: "440"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 0.375; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(5) 4fd800b3a8 2011-02-23 kinaba: string roads_[] = {"0701", 4fd800b3a8 2011-02-23 kinaba: "7071", 4fd800b3a8 2011-02-23 kinaba: "0708", 4fd800b3a8 2011-02-23 kinaba: "1180"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 0.622314453125; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(6) 4fd800b3a8 2011-02-23 kinaba: string roads_[] = {"0622100102300020", "6070000107208008", "2700207010110410", "2000188001010820", "1021032008000021", "0008300013001000", "0078200200000201", "1100002007000011", "0010010000600000", "2701830700518172", "3210000065000200", "0011000001002081", "0800010008020100", "0048002001201000", "2012200107080000", "0800101102010000"}; 4fd800b3a8 2011-02-23 kinaba: vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 5.519032471358341E-5; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: /* 4fd800b3a8 2011-02-23 kinaba: CASE(7) 4fd800b3a8 2011-02-23 kinaba: string roads_[] = ; 4fd800b3a8 2011-02-23 kinaba: vector <string> roads(roads_, roads_+sizeof(roads_)/sizeof(*roads_)); 4fd800b3a8 2011-02-23 kinaba: double _ = ; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: */ 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE