d4ec396a23 2014-04-21 kinaba: #include <iostream> d4ec396a23 2014-04-21 kinaba: #include <sstream> d4ec396a23 2014-04-21 kinaba: #include <iomanip> d4ec396a23 2014-04-21 kinaba: #include <vector> d4ec396a23 2014-04-21 kinaba: #include <string> d4ec396a23 2014-04-21 kinaba: #include <map> d4ec396a23 2014-04-21 kinaba: #include <set> d4ec396a23 2014-04-21 kinaba: #include <algorithm> d4ec396a23 2014-04-21 kinaba: #include <numeric> d4ec396a23 2014-04-21 kinaba: #include <iterator> d4ec396a23 2014-04-21 kinaba: #include <functional> d4ec396a23 2014-04-21 kinaba: #include <complex> d4ec396a23 2014-04-21 kinaba: #include <queue> d4ec396a23 2014-04-21 kinaba: #include <stack> d4ec396a23 2014-04-21 kinaba: #include <cmath> d4ec396a23 2014-04-21 kinaba: #include <cassert> d4ec396a23 2014-04-21 kinaba: #include <tuple> d4ec396a23 2014-04-21 kinaba: using namespace std; d4ec396a23 2014-04-21 kinaba: typedef long long LL; d4ec396a23 2014-04-21 kinaba: typedef complex<double> CMP; d4ec396a23 2014-04-21 kinaba: d4ec396a23 2014-04-21 kinaba: double C(int n, int k) d4ec396a23 2014-04-21 kinaba: { d4ec396a23 2014-04-21 kinaba: k = min(n-k, k); d4ec396a23 2014-04-21 kinaba: double t = 1; d4ec396a23 2014-04-21 kinaba: for(int i=1; i<=k; ++i) d4ec396a23 2014-04-21 kinaba: t = t * (n-i+1) / i; d4ec396a23 2014-04-21 kinaba: return t; d4ec396a23 2014-04-21 kinaba: } d4ec396a23 2014-04-21 kinaba: d4ec396a23 2014-04-21 kinaba: class EagleInZoo { public: d4ec396a23 2014-04-21 kinaba: double calc(vector <int> parent, int K) d4ec396a23 2014-04-21 kinaba: { d4ec396a23 2014-04-21 kinaba: int N = parent.size() + 1; d4ec396a23 2014-04-21 kinaba: vector<vector<int>> child(N); d4ec396a23 2014-04-21 kinaba: for(int i=1; i<N; ++i) d4ec396a23 2014-04-21 kinaba: child[parent[i-1]].push_back(i); d4ec396a23 2014-04-21 kinaba: return rec(child, 0, K); d4ec396a23 2014-04-21 kinaba: } d4ec396a23 2014-04-21 kinaba: d4ec396a23 2014-04-21 kinaba: map<pair<int,int>,double> memo; d4ec396a23 2014-04-21 kinaba: double rec(const vector<vector<int>>& child, int v, int K) d4ec396a23 2014-04-21 kinaba: { d4ec396a23 2014-04-21 kinaba: if(K == 1) d4ec396a23 2014-04-21 kinaba: return 1.0; d4ec396a23 2014-04-21 kinaba: if(child[v].empty()) d4ec396a23 2014-04-21 kinaba: return 0.0; d4ec396a23 2014-04-21 kinaba: pair<int,int> key(v, K); d4ec396a23 2014-04-21 kinaba: if(memo.count(key)) return memo[key]; d4ec396a23 2014-04-21 kinaba: d4ec396a23 2014-04-21 kinaba: double ans = 0.0; d4ec396a23 2014-04-21 kinaba: for(int u: child[v]) // When K-the eagle goes to |u|. d4ec396a23 2014-04-21 kinaba: for(int uN=0; uN<=K-2; ++uN) // When uN out of K-2 previous eagles went to |u|. d4ec396a23 2014-04-21 kinaba: { d4ec396a23 2014-04-21 kinaba: ans += C(K-2, uN) d4ec396a23 2014-04-21 kinaba: * pow(1.0/child[v].size(), uN) d4ec396a23 2014-04-21 kinaba: * pow(1.0-1.0/child[v].size(), K-2-uN) d4ec396a23 2014-04-21 kinaba: * rec(child, u, uN+1); d4ec396a23 2014-04-21 kinaba: } d4ec396a23 2014-04-21 kinaba: return memo[key] = ans / child[v].size(); d4ec396a23 2014-04-21 kinaba: } d4ec396a23 2014-04-21 kinaba: }; d4ec396a23 2014-04-21 kinaba: d4ec396a23 2014-04-21 kinaba: // BEGIN CUT HERE d4ec396a23 2014-04-21 kinaba: #include <ctime> d4ec396a23 2014-04-21 kinaba: double start_time; string timer() d4ec396a23 2014-04-21 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } d4ec396a23 2014-04-21 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) d4ec396a23 2014-04-21 kinaba: { os << "{ "; d4ec396a23 2014-04-21 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) d4ec396a23 2014-04-21 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } d4ec396a23 2014-04-21 kinaba: void verify_case(const double& Expected, const double& Received) { d4ec396a23 2014-04-21 kinaba: bool ok = (abs(Expected - Received) < 1e-9); d4ec396a23 2014-04-21 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; d4ec396a23 2014-04-21 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } d4ec396a23 2014-04-21 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); d4ec396a23 2014-04-21 kinaba: #define END verify_case(_, EagleInZoo().calc(parent, K));} d4ec396a23 2014-04-21 kinaba: int main(){ d4ec396a23 2014-04-21 kinaba: d4ec396a23 2014-04-21 kinaba: CASE(0) d4ec396a23 2014-04-21 kinaba: int parent_[] = {0,0}; d4ec396a23 2014-04-21 kinaba: vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); d4ec396a23 2014-04-21 kinaba: int K = 2; d4ec396a23 2014-04-21 kinaba: double _ = 1.0; d4ec396a23 2014-04-21 kinaba: END d4ec396a23 2014-04-21 kinaba: CASE(1) d4ec396a23 2014-04-21 kinaba: int parent_[] = {0,0}; d4ec396a23 2014-04-21 kinaba: vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); d4ec396a23 2014-04-21 kinaba: int K = 3; d4ec396a23 2014-04-21 kinaba: double _ = 0.5; d4ec396a23 2014-04-21 kinaba: END d4ec396a23 2014-04-21 kinaba: CASE(2) d4ec396a23 2014-04-21 kinaba: int parent_[] = {0,1,0,3}; d4ec396a23 2014-04-21 kinaba: vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); d4ec396a23 2014-04-21 kinaba: int K = 4; d4ec396a23 2014-04-21 kinaba: double _ = 0.75; d4ec396a23 2014-04-21 kinaba: END d4ec396a23 2014-04-21 kinaba: CASE(3) d4ec396a23 2014-04-21 kinaba: int parent_[] = {0,0,1,1,2,4,4,4,5,5,6,6}; d4ec396a23 2014-04-21 kinaba: vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); d4ec396a23 2014-04-21 kinaba: int K = 20; d4ec396a23 2014-04-21 kinaba: double _ = 0.14595168754091617; d4ec396a23 2014-04-21 kinaba: END d4ec396a23 2014-04-21 kinaba: CASE(4) d4ec396a23 2014-04-21 kinaba: int parent_[] = {0,1,2,3,2,1,1,7,0,9,10,11,12,13,14,15,16,17,18,14,9}; d4ec396a23 2014-04-21 kinaba: vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); d4ec396a23 2014-04-21 kinaba: int K = 24; d4ec396a23 2014-04-21 kinaba: double _ = 0.3272154791654077; d4ec396a23 2014-04-21 kinaba: END d4ec396a23 2014-04-21 kinaba: CASE(5) d4ec396a23 2014-04-21 kinaba: int parent_[] = {0,1,2,3,4,5,6,7,8,9,10}; d4ec396a23 2014-04-21 kinaba: vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); d4ec396a23 2014-04-21 kinaba: int K = 50; d4ec396a23 2014-04-21 kinaba: double _ = 0.0; d4ec396a23 2014-04-21 kinaba: END d4ec396a23 2014-04-21 kinaba: /* d4ec396a23 2014-04-21 kinaba: CASE(6) d4ec396a23 2014-04-21 kinaba: int parent_[] = ; d4ec396a23 2014-04-21 kinaba: vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); d4ec396a23 2014-04-21 kinaba: int K = ; d4ec396a23 2014-04-21 kinaba: double _ = ; d4ec396a23 2014-04-21 kinaba: END d4ec396a23 2014-04-21 kinaba: CASE(7) d4ec396a23 2014-04-21 kinaba: int parent_[] = ; d4ec396a23 2014-04-21 kinaba: vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); d4ec396a23 2014-04-21 kinaba: int K = ; d4ec396a23 2014-04-21 kinaba: double _ = ; d4ec396a23 2014-04-21 kinaba: END d4ec396a23 2014-04-21 kinaba: */ d4ec396a23 2014-04-21 kinaba: } d4ec396a23 2014-04-21 kinaba: // END CUT HERE