535b5a8c1c 2012-04-21        kinaba: #include <iostream>
535b5a8c1c 2012-04-21        kinaba: #include <sstream>
535b5a8c1c 2012-04-21        kinaba: #include <iomanip>
535b5a8c1c 2012-04-21        kinaba: #include <vector>
535b5a8c1c 2012-04-21        kinaba: #include <string>
535b5a8c1c 2012-04-21        kinaba: #include <map>
535b5a8c1c 2012-04-21        kinaba: #include <set>
535b5a8c1c 2012-04-21        kinaba: #include <algorithm>
535b5a8c1c 2012-04-21        kinaba: #include <numeric>
535b5a8c1c 2012-04-21        kinaba: #include <iterator>
535b5a8c1c 2012-04-21        kinaba: #include <functional>
535b5a8c1c 2012-04-21        kinaba: #include <complex>
535b5a8c1c 2012-04-21        kinaba: #include <queue>
535b5a8c1c 2012-04-21        kinaba: #include <stack>
535b5a8c1c 2012-04-21        kinaba: #include <cmath>
535b5a8c1c 2012-04-21        kinaba: #include <cassert>
535b5a8c1c 2012-04-21        kinaba: #include <cstring>
535b5a8c1c 2012-04-21        kinaba: #ifdef __GNUC__
535b5a8c1c 2012-04-21        kinaba: #include <ext/hash_map>
535b5a8c1c 2012-04-21        kinaba: #define unordered_map __gnu_cxx::hash_map
535b5a8c1c 2012-04-21        kinaba: #else
535b5a8c1c 2012-04-21        kinaba: #include <unordered_map>
535b5a8c1c 2012-04-21        kinaba: #endif
535b5a8c1c 2012-04-21        kinaba: using namespace std;
535b5a8c1c 2012-04-21        kinaba: typedef long long LL;
535b5a8c1c 2012-04-21        kinaba: typedef complex<double> CMP;
535b5a8c1c 2012-04-21        kinaba: 
535b5a8c1c 2012-04-21        kinaba: class RandomColoring { public:
535b5a8c1c 2012-04-21        kinaba: 	double getProbability(int N, int maxR, int maxG, int maxB, int startR, int startG, int startB, int d1, int d2)
535b5a8c1c 2012-04-21        kinaba: 	{
535b5a8c1c 2012-04-21        kinaba: 		const int dx = d1-1;
535b5a8c1c 2012-04-21        kinaba: 
535b5a8c1c 2012-04-21        kinaba: 		vector< vector< vector<double> > > p(maxR, vector<vector<double> >(maxG, vector<double>(maxB)));
535b5a8c1c 2012-04-21        kinaba: 		p[startR][startG][startB] = 1.0;
535b5a8c1c 2012-04-21        kinaba: 
535b5a8c1c 2012-04-21        kinaba: 		for(int i=1; i<N; ++i)
535b5a8c1c 2012-04-21        kinaba: 		{
535b5a8c1c 2012-04-21        kinaba: 			for(int r=0; r<maxR; ++r)
535b5a8c1c 2012-04-21        kinaba: 			for(int g=0; g<maxG; ++g)
535b5a8c1c 2012-04-21        kinaba: 			for(int b=0; b<maxB; ++b) {
535b5a8c1c 2012-04-21        kinaba: 				int c = cnt(maxR, maxG, maxB, r-d2, r+d2, g-d2, g+d2, b-d2, b+d2)
535b5a8c1c 2012-04-21        kinaba: 				- (d1==0 ? 0 : cnt(maxR, maxG, maxB, r-dx, r+dx, g-dx, g+dx, b-dx, b+dx));
535b5a8c1c 2012-04-21        kinaba: 				if( c )
535b5a8c1c 2012-04-21        kinaba: 					p[r][g][b] /= c;
535b5a8c1c 2012-04-21        kinaba: 				else
535b5a8c1c 2012-04-21        kinaba: 					p[r][g][b] = 0;
535b5a8c1c 2012-04-21        kinaba: 			}
535b5a8c1c 2012-04-21        kinaba: 
535b5a8c1c 2012-04-21        kinaba: 			vector< vector< vector<double> > > low = p;
535b5a8c1c 2012-04-21        kinaba: 			for(int rgb=0; rgb<=maxR+maxG+maxB-3; ++rgb)
535b5a8c1c 2012-04-21        kinaba: 			for(int r=0; r<maxR; ++r)
535b5a8c1c 2012-04-21        kinaba: 			for(int g=0; g<maxG; ++g)
535b5a8c1c 2012-04-21        kinaba: 			{
535b5a8c1c 2012-04-21        kinaba: 				int b = rgb-r-g;
535b5a8c1c 2012-04-21        kinaba: 				if( 0<=b && b<maxB ) {
535b5a8c1c 2012-04-21        kinaba: 					low[r][g][b] =
535b5a8c1c 2012-04-21        kinaba: 						p[r][g][b]
535b5a8c1c 2012-04-21        kinaba: 						+ (r ? low[r-1][g][b] : 0)
535b5a8c1c 2012-04-21        kinaba: 						+ (g ? low[r][g-1][b] : 0)
535b5a8c1c 2012-04-21        kinaba: 						+ (b ? low[r][g][b-1] : 0)
535b5a8c1c 2012-04-21        kinaba: 						- (r&&g ? low[r-1][g-1][b] : 0)
535b5a8c1c 2012-04-21        kinaba: 						- (g&&b ? low[r][g-1][b-1] : 0)
535b5a8c1c 2012-04-21        kinaba: 						- (b&&r ? low[r-1][g][b-1] : 0)
535b5a8c1c 2012-04-21        kinaba: 						+ (r&&g&&b ? low[r-1][g-1][b-1] : 0);
535b5a8c1c 2012-04-21        kinaba: 				}
535b5a8c1c 2012-04-21        kinaba: 			}
535b5a8c1c 2012-04-21        kinaba: 
535b5a8c1c 2012-04-21        kinaba: 			vector< vector< vector<double> > > q = p;
535b5a8c1c 2012-04-21        kinaba: 			for(int r=0; r<maxR; ++r)
535b5a8c1c 2012-04-21        kinaba: 			for(int g=0; g<maxG; ++g)
535b5a8c1c 2012-04-21        kinaba: 			for(int b=0; b<maxB; ++b)
535b5a8c1c 2012-04-21        kinaba: 			{
535b5a8c1c 2012-04-21        kinaba: 				q[r][g][b] =
535b5a8c1c 2012-04-21        kinaba: 					  zone(low, r-d2, r+d2, g-d2, g+d2, b-d2, b+d2)
535b5a8c1c 2012-04-21        kinaba: 					- (d1==0 ? 0 : zone(low, r-dx, r+dx, g-dx, g+dx, b-dx, b+dx));
535b5a8c1c 2012-04-21        kinaba: 			}
535b5a8c1c 2012-04-21        kinaba: 			p.swap(q);
535b5a8c1c 2012-04-21        kinaba: 		}
535b5a8c1c 2012-04-21        kinaba: 
535b5a8c1c 2012-04-21        kinaba: 		vector< vector< vector<double> > > low = p;
535b5a8c1c 2012-04-21        kinaba: 		for(int rgb=0; rgb<=maxR+maxG+maxB-3; ++rgb)
535b5a8c1c 2012-04-21        kinaba: 		for(int r=0; r<maxR; ++r)
535b5a8c1c 2012-04-21        kinaba: 		for(int g=0; g<maxG; ++g)
535b5a8c1c 2012-04-21        kinaba: 		{
535b5a8c1c 2012-04-21        kinaba: 			int b = rgb-r-g;
535b5a8c1c 2012-04-21        kinaba: 			if( 0<=b && b<maxB ) {
535b5a8c1c 2012-04-21        kinaba: 				low[r][g][b] =
535b5a8c1c 2012-04-21        kinaba: 					p[r][g][b]
535b5a8c1c 2012-04-21        kinaba: 					+ (r ? low[r-1][g][b] : 0)
535b5a8c1c 2012-04-21        kinaba: 					+ (g ? low[r][g-1][b] : 0)
535b5a8c1c 2012-04-21        kinaba: 					+ (b ? low[r][g][b-1] : 0)
535b5a8c1c 2012-04-21        kinaba: 					- (r&&g ? low[r-1][g-1][b] : 0)
535b5a8c1c 2012-04-21        kinaba: 					- (g&&b ? low[r][g-1][b-1] : 0)
535b5a8c1c 2012-04-21        kinaba: 					- (b&&r ? low[r-1][g][b-1] : 0)
535b5a8c1c 2012-04-21        kinaba: 					+ (r&&g&&b ? low[r-1][g-1][b-1] : 0);
535b5a8c1c 2012-04-21        kinaba: 			}
535b5a8c1c 2012-04-21        kinaba: 		}
535b5a8c1c 2012-04-21        kinaba: 
535b5a8c1c 2012-04-21        kinaba: 		return 1.0 - (
535b5a8c1c 2012-04-21        kinaba: 			zone(low, startR-d2, startR+d2, startG-d2, startG+d2, startB-d2, startB+d2)
535b5a8c1c 2012-04-21        kinaba: 			- (d1==0 ? 0 : zone(low, startR-dx, startR+dx, startG-dx, startG+dx, startB-dx, startB+dx))
535b5a8c1c 2012-04-21        kinaba: 		);
535b5a8c1c 2012-04-21        kinaba: 	}
535b5a8c1c 2012-04-21        kinaba: 
535b5a8c1c 2012-04-21        kinaba: 	double zone(const vector< vector< vector<double> > >& low,
535b5a8c1c 2012-04-21        kinaba: 		int r, int R, int g, int G, int b, int B) {
535b5a8c1c 2012-04-21        kinaba: 		r = max(0, min<int>(low.size()-1, r));
535b5a8c1c 2012-04-21        kinaba: 		R = max(0, min<int>(low.size()-1, R));
535b5a8c1c 2012-04-21        kinaba: 		g = max(0, min<int>(low[0].size()-1, g));
535b5a8c1c 2012-04-21        kinaba: 		G = max(0, min<int>(low[0].size()-1, G));
535b5a8c1c 2012-04-21        kinaba: 		b = max(0, min<int>(low[0][0].size()-1, b));
535b5a8c1c 2012-04-21        kinaba: 		B = max(0, min<int>(low[0][0].size()-1, B));
535b5a8c1c 2012-04-21        kinaba: 		return low[R][G][B]
535b5a8c1c 2012-04-21        kinaba: 				- (r ? low[r-1][G][B] : 0)
535b5a8c1c 2012-04-21        kinaba: 				- (g ? low[R][g-1][B] : 0)
535b5a8c1c 2012-04-21        kinaba: 				- (b ? low[R][G][b-1] : 0)
535b5a8c1c 2012-04-21        kinaba: 				+ (r&&g ? low[r-1][g-1][B] : 0)
535b5a8c1c 2012-04-21        kinaba: 				+ (g&&b ? low[R][g-1][b-1] : 0)
535b5a8c1c 2012-04-21        kinaba: 				+ (b&&r ? low[r-1][G][b-1] : 0)
535b5a8c1c 2012-04-21        kinaba: 				- (r&&g&&b ? low[r-1][g-1][b-1] : 0);
535b5a8c1c 2012-04-21        kinaba: 	}
535b5a8c1c 2012-04-21        kinaba: 
535b5a8c1c 2012-04-21        kinaba: 	int cnt(int maxR, int maxG, int maxB,
535b5a8c1c 2012-04-21        kinaba: 		int r, int R, int g, int G, int b, int B) {
535b5a8c1c 2012-04-21        kinaba: 		r = max(0, min<int>(maxR-1, r));
535b5a8c1c 2012-04-21        kinaba: 		R = max(0, min<int>(maxR-1, R));
535b5a8c1c 2012-04-21        kinaba: 		g = max(0, min<int>(maxG-1, g));
535b5a8c1c 2012-04-21        kinaba: 		G = max(0, min<int>(maxG-1, G));
535b5a8c1c 2012-04-21        kinaba: 		b = max(0, min<int>(maxB-1, b));
535b5a8c1c 2012-04-21        kinaba: 		B = max(0, min<int>(maxB-1, B));
535b5a8c1c 2012-04-21        kinaba: 		return (R-r+1)*(G-g+1)*(B-b+1);
535b5a8c1c 2012-04-21        kinaba: 	}
535b5a8c1c 2012-04-21        kinaba: };
535b5a8c1c 2012-04-21        kinaba: 
535b5a8c1c 2012-04-21        kinaba: // BEGIN CUT HERE
535b5a8c1c 2012-04-21        kinaba: #include <ctime>
535b5a8c1c 2012-04-21        kinaba: double start_time; string timer()
535b5a8c1c 2012-04-21        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
535b5a8c1c 2012-04-21        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
535b5a8c1c 2012-04-21        kinaba:  { os << "{ ";
535b5a8c1c 2012-04-21        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
535b5a8c1c 2012-04-21        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
535b5a8c1c 2012-04-21        kinaba: void verify_case(const double& Expected, const double& Received) {
535b5a8c1c 2012-04-21        kinaba:  bool ok = (abs(Expected - Received) < 1e-9);
535b5a8c1c 2012-04-21        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
535b5a8c1c 2012-04-21        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
535b5a8c1c 2012-04-21        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
535b5a8c1c 2012-04-21        kinaba: #define END	 verify_case(_, RandomColoring().getProbability(N, maxR, maxG, maxB, startR, startG, startB, d1, d2));}
535b5a8c1c 2012-04-21        kinaba: int main(){
535b5a8c1c 2012-04-21        kinaba: 
535b5a8c1c 2012-04-21        kinaba: CASE(0)
535b5a8c1c 2012-04-21        kinaba: 	int N = 2;
535b5a8c1c 2012-04-21        kinaba: 	int maxR = 5;
535b5a8c1c 2012-04-21        kinaba: 	int maxG = 1;
535b5a8c1c 2012-04-21        kinaba: 	int maxB = 1;
535b5a8c1c 2012-04-21        kinaba: 	int startR = 2;
535b5a8c1c 2012-04-21        kinaba: 	int startG = 0;
535b5a8c1c 2012-04-21        kinaba: 	int startB = 0;
535b5a8c1c 2012-04-21        kinaba: 	int d1 = 0;
535b5a8c1c 2012-04-21        kinaba: 	int d2 = 1;
535b5a8c1c 2012-04-21        kinaba: 	double _ = 0.0;
535b5a8c1c 2012-04-21        kinaba: END
535b5a8c1c 2012-04-21        kinaba: CASE(1)
535b5a8c1c 2012-04-21        kinaba: 	int N = 3;
535b5a8c1c 2012-04-21        kinaba: 	int maxR = 5;
535b5a8c1c 2012-04-21        kinaba: 	int maxG = 1;
535b5a8c1c 2012-04-21        kinaba: 	int maxB = 1;
535b5a8c1c 2012-04-21        kinaba: 	int startR = 2;
535b5a8c1c 2012-04-21        kinaba: 	int startG = 0;
535b5a8c1c 2012-04-21        kinaba: 	int startB = 0;
535b5a8c1c 2012-04-21        kinaba: 	int d1 = 0;
535b5a8c1c 2012-04-21        kinaba: 	int d2 = 1;
535b5a8c1c 2012-04-21        kinaba: 	double _ = 0.22222222222222227;
535b5a8c1c 2012-04-21        kinaba: END
535b5a8c1c 2012-04-21        kinaba: CASE(2)
535b5a8c1c 2012-04-21        kinaba: 	int N = 7;
535b5a8c1c 2012-04-21        kinaba: 	int maxR = 4;
535b5a8c1c 2012-04-21        kinaba: 	int maxG = 2;
535b5a8c1c 2012-04-21        kinaba: 	int maxB = 2;
535b5a8c1c 2012-04-21        kinaba: 	int startR = 0;
535b5a8c1c 2012-04-21        kinaba: 	int startG = 0;
535b5a8c1c 2012-04-21        kinaba: 	int startB = 0;
535b5a8c1c 2012-04-21        kinaba: 	int d1 = 3;
535b5a8c1c 2012-04-21        kinaba: 	int d2 = 3;
535b5a8c1c 2012-04-21        kinaba: 	double _ = 1.0;
535b5a8c1c 2012-04-21        kinaba: END
535b5a8c1c 2012-04-21        kinaba: CASE(3)
535b5a8c1c 2012-04-21        kinaba: 	int N = 10;
535b5a8c1c 2012-04-21        kinaba: 	int maxR = 7;
535b5a8c1c 2012-04-21        kinaba: 	int maxG = 8;
535b5a8c1c 2012-04-21        kinaba: 	int maxB = 9;
535b5a8c1c 2012-04-21        kinaba: 	int startR = 1;
535b5a8c1c 2012-04-21        kinaba: 	int startG = 2;
535b5a8c1c 2012-04-21        kinaba: 	int startB = 3;
535b5a8c1c 2012-04-21        kinaba: 	int d1 = 0;
535b5a8c1c 2012-04-21        kinaba: 	int d2 = 10;
535b5a8c1c 2012-04-21        kinaba: 	double _ = 0.0;
535b5a8c1c 2012-04-21        kinaba: END
535b5a8c1c 2012-04-21        kinaba: CASE(4)
535b5a8c1c 2012-04-21        kinaba: 	int N = 10;
535b5a8c1c 2012-04-21        kinaba: 	int maxR = 7;
535b5a8c1c 2012-04-21        kinaba: 	int maxG = 8;
535b5a8c1c 2012-04-21        kinaba: 	int maxB = 9;
535b5a8c1c 2012-04-21        kinaba: 	int startR = 1;
535b5a8c1c 2012-04-21        kinaba: 	int startG = 2;
535b5a8c1c 2012-04-21        kinaba: 	int startB = 3;
535b5a8c1c 2012-04-21        kinaba: 	int d1 = 4;
535b5a8c1c 2012-04-21        kinaba: 	int d2 = 10;
535b5a8c1c 2012-04-21        kinaba: 	double _ = 0.37826245943967396;
535b5a8c1c 2012-04-21        kinaba: END
535b5a8c1c 2012-04-21        kinaba: CASE(5)
535b5a8c1c 2012-04-21        kinaba: 	int N = 3;
535b5a8c1c 2012-04-21        kinaba: 	int maxR = 3;
535b5a8c1c 2012-04-21        kinaba: 	int maxG = 2;
535b5a8c1c 2012-04-21        kinaba: 	int maxB = 2;
535b5a8c1c 2012-04-21        kinaba: 	int startR = 1;
535b5a8c1c 2012-04-21        kinaba: 	int startG = 0;
535b5a8c1c 2012-04-21        kinaba: 	int startB = 0;
535b5a8c1c 2012-04-21        kinaba: 	int d1 = 1;
535b5a8c1c 2012-04-21        kinaba: 	int d2 = 2;
535b5a8c1c 2012-04-21        kinaba: 	double _ = 0.09090909090909148;
535b5a8c1c 2012-04-21        kinaba: END
535b5a8c1c 2012-04-21        kinaba: /*
535b5a8c1c 2012-04-21        kinaba: CASE(6)
535b5a8c1c 2012-04-21        kinaba: 	int N = ;
535b5a8c1c 2012-04-21        kinaba: 	int maxR = ;
535b5a8c1c 2012-04-21        kinaba: 	int maxG = ;
535b5a8c1c 2012-04-21        kinaba: 	int maxB = ;
535b5a8c1c 2012-04-21        kinaba: 	int startR = ;
535b5a8c1c 2012-04-21        kinaba: 	int startG = ;
535b5a8c1c 2012-04-21        kinaba: 	int startB = ;
535b5a8c1c 2012-04-21        kinaba: 	int d1 = ;
535b5a8c1c 2012-04-21        kinaba: 	int d2 = ;
535b5a8c1c 2012-04-21        kinaba: 	double _ = ;
535b5a8c1c 2012-04-21        kinaba: END
535b5a8c1c 2012-04-21        kinaba: CASE(7)
535b5a8c1c 2012-04-21        kinaba: 	int N = ;
535b5a8c1c 2012-04-21        kinaba: 	int maxR = ;
535b5a8c1c 2012-04-21        kinaba: 	int maxG = ;
535b5a8c1c 2012-04-21        kinaba: 	int maxB = ;
535b5a8c1c 2012-04-21        kinaba: 	int startR = ;
535b5a8c1c 2012-04-21        kinaba: 	int startG = ;
535b5a8c1c 2012-04-21        kinaba: 	int startB = ;
535b5a8c1c 2012-04-21        kinaba: 	int d1 = ;
535b5a8c1c 2012-04-21        kinaba: 	int d2 = ;
535b5a8c1c 2012-04-21        kinaba: 	double _ = ;
535b5a8c1c 2012-04-21        kinaba: END
535b5a8c1c 2012-04-21        kinaba: */
535b5a8c1c 2012-04-21        kinaba: }
535b5a8c1c 2012-04-21        kinaba: // END CUT HERE