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: vector< vector<double> > mMul( const vector< vector<double> >& A, const vector< vector<double> >& B ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: const int n = A.size(); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector< vector<double> > C(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: double Cij = 0; 4fd800b3a8 2011-02-23 kinaba: for(int k=0; k<n; ++k) 4fd800b3a8 2011-02-23 kinaba: Cij += A[i][k] * B[k][j]; 4fd800b3a8 2011-02-23 kinaba: C[i][j] = Cij; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return C; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector< vector<double> > mPow( vector< vector<double> > M, LL t ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: vector< vector<double> > R; 4fd800b3a8 2011-02-23 kinaba: if( t == 0 ) { 4fd800b3a8 2011-02-23 kinaba: const int n = M.size(); 4fd800b3a8 2011-02-23 kinaba: R = M; 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: R[i][j] = (i==j); 4fd800b3a8 2011-02-23 kinaba: return R; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: for(; t; t>>=1, M=mMul(M,M)) 4fd800b3a8 2011-02-23 kinaba: if( t&1 ) 4fd800b3a8 2011-02-23 kinaba: R = (R.empty() ? M : mMul(R,M)); 4fd800b3a8 2011-02-23 kinaba: return R; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: class CandyBox { public: 4fd800b3a8 2011-02-23 kinaba: vector <double> expectedScore(int C, vector <int> score, int S) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int N = score.size(); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector< vector<double> > m(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: double pOut = 2.0/(N*(N*C-1)); 4fd800b3a8 2011-02-23 kinaba: m[i][j] = (i==j ? 1-pOut*(N-1) : pOut); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: m = mPow(m, S); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: double as = accumulate(score.begin(), score.end(), 0.0); 4fd800b3a8 2011-02-23 kinaba: double stay = m[0][0]; 4fd800b3a8 2011-02-23 kinaba: double out = (N==1 ? 0 : m[1][0]); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector<double> result(N); 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<N; ++i) 4fd800b3a8 2011-02-23 kinaba: result[i] = (as-score[i])*out + score[i]*stay; 4fd800b3a8 2011-02-23 kinaba: return result; 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 vector <double>& Expected, const vector <double>& Received) { 4fd800b3a8 2011-02-23 kinaba: bool ok = true; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<Expected.size(); ++i) 4fd800b3a8 2011-02-23 kinaba: if( abs(Expected[i]-Received[i])>1e-9 ) 4fd800b3a8 2011-02-23 kinaba: ok = false; 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(_, CandyBox().expectedScore(C, score, S));} 4fd800b3a8 2011-02-23 kinaba: int main(){ 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: CASE(0) 4fd800b3a8 2011-02-23 kinaba: int C = 10; 4fd800b3a8 2011-02-23 kinaba: int score_[] = {1, 10}; 4fd800b3a8 2011-02-23 kinaba: vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); 4fd800b3a8 2011-02-23 kinaba: int S = 0; 4fd800b3a8 2011-02-23 kinaba: double __[] = {1.0, 10.0 }; 4fd800b3a8 2011-02-23 kinaba: vector <double> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(1) 4fd800b3a8 2011-02-23 kinaba: int C = 2; 4fd800b3a8 2011-02-23 kinaba: int score_[] = {1, 10}; 4fd800b3a8 2011-02-23 kinaba: vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); 4fd800b3a8 2011-02-23 kinaba: int S = 1; 4fd800b3a8 2011-02-23 kinaba: double __[] = {4.0, 7.000000000000001 }; 4fd800b3a8 2011-02-23 kinaba: vector <double> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(2) 4fd800b3a8 2011-02-23 kinaba: int C = 1; 4fd800b3a8 2011-02-23 kinaba: int score_[] = {1, 4, 10}; 4fd800b3a8 2011-02-23 kinaba: vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); 4fd800b3a8 2011-02-23 kinaba: int S = 1; 4fd800b3a8 2011-02-23 kinaba: double __[] = {5.0, 5.0, 5.0 }; 4fd800b3a8 2011-02-23 kinaba: vector <double> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(3) 4fd800b3a8 2011-02-23 kinaba: int C = 98; 4fd800b3a8 2011-02-23 kinaba: int score_[] = {13, 82, 74, 78, 12, 71, 81, 80, 30}; 4fd800b3a8 2011-02-23 kinaba: vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); 4fd800b3a8 2011-02-23 kinaba: int S = 154; 4fd800b3a8 2011-02-23 kinaba: double __[] = {26.25622829378155, 74.87969915903301, 69.24219529059805, 72.06094722481552, 25.551540310227182, 67.12813133993495, 74.17501117547864, 73.47032319192427, 38.23592401420582 }; 4fd800b3a8 2011-02-23 kinaba: vector <double> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(4) 4fd800b3a8 2011-02-23 kinaba: int C = 1; 4fd800b3a8 2011-02-23 kinaba: int score_[] = {1,1}; 4fd800b3a8 2011-02-23 kinaba: vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); 4fd800b3a8 2011-02-23 kinaba: int S = 1; 4fd800b3a8 2011-02-23 kinaba: double __[] = {1,1}; 4fd800b3a8 2011-02-23 kinaba: vector <double> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(5) 4fd800b3a8 2011-02-23 kinaba: int C = 2; 4fd800b3a8 2011-02-23 kinaba: int score_[] = {1}; 4fd800b3a8 2011-02-23 kinaba: vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); 4fd800b3a8 2011-02-23 kinaba: int S = 10000; 4fd800b3a8 2011-02-23 kinaba: double __[] = {1}; 4fd800b3a8 2011-02-23 kinaba: vector <double> _(__, __+sizeof(__)/sizeof(*__)); 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE