Artifact Content
Not logged in

Artifact da8cd7890ede0b8d096b15af763c15cec84dae7d


#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 <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

vector< vector<double> > mMul( const vector< vector<double> >& A, const vector< vector<double> >& B )
{
	const int n = A.size();

	vector< vector<double> > C(n, vector<double>(n));
	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j) {
			double Cij = 0;
			for(int k=0; k<n; ++k)
				Cij += A[i][k] * B[k][j];
			C[i][j] = Cij;
		}
	return C;
}

vector< vector<double> > mPow( vector< vector<double> > M, LL t )
{
	vector< vector<double> > R;
	if( t == 0 ) {
		const int n = M.size();
		R = M;
		for(int i=0; i<n; ++i)
			for(int j=0; j<n; ++j)
				R[i][j] = (i==j);
		return R;
	}

	for(; t; t>>=1, M=mMul(M,M))
		if( t&1 )
			R = (R.empty() ? M : mMul(R,M));
	return R;
}

class CandyBox { public:
	vector <double> expectedScore(int C, vector <int> score, int S) 
	{
		int N = score.size();

		vector< vector<double> > m(N, vector<double>(N));
		for(int i=0; i<N; ++i)
			for(int j=0; j<N; ++j) {
				double pOut  = 2.0/(N*(N*C-1));
				m[i][j] = (i==j ? 1-pOut*(N-1) : pOut);
			}
		m = mPow(m, S);

		double as = accumulate(score.begin(), score.end(), 0.0);
		double stay = m[0][0];
		double  out = (N==1 ? 0 : m[1][0]);

		vector<double> result(N);
		for(int i=0; i<N; ++i)
			result[i] = (as-score[i])*out + score[i]*stay;
		return result;
	}
};

// 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 vector <double>& Expected, const vector <double>& Received) {
 bool ok = true;
 for(int i=0; i<Expected.size(); ++i)
   if( abs(Expected[i]-Received[i])>1e-9 )
     ok = false;
 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(_, CandyBox().expectedScore(C, score, S));}
int main(){

CASE(0)
	int C = 10; 
	int score_[] = {1, 10};
	  vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); 
	int S = 0; 
	double __[] = {1.0, 10.0 };
	  vector <double> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(1)
	int C = 2; 
	int score_[] = {1, 10};
	  vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); 
	int S = 1; 
	double __[] = {4.0, 7.000000000000001 };
	  vector <double> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(2)
	int C = 1; 
	int score_[] = {1, 4, 10};
	  vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); 
	int S = 1; 
	double __[] = {5.0, 5.0, 5.0 };
	  vector <double> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(3)
	int C = 98; 
	int score_[] = {13, 82, 74, 78, 12, 71, 81, 80, 30};
	  vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); 
	int S = 154; 
	double __[] = {26.25622829378155, 74.87969915903301, 69.24219529059805, 72.06094722481552, 25.551540310227182, 67.12813133993495, 74.17501117547864, 73.47032319192427, 38.23592401420582 };
	  vector <double> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(4)
	int C = 1; 
	int score_[] = {1,1};
	  vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); 
	int S = 1; 
	double __[] = {1,1};
	  vector <double> _(__, __+sizeof(__)/sizeof(*__)); 
END
CASE(5)
	int C = 2; 
	int score_[] = {1};
	  vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_)); 
	int S = 10000; 
	double __[] = {1};
	  vector <double> _(__, __+sizeof(__)/sizeof(*__)); 
END
}
// END CUT HERE