#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>
#ifdef __GNUC__
#include <ext/hash_map>
#define unordered_map __gnu_cxx::hash_map
#else
#include <unordered_map>
#endif
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class RandomColoring { public:
double getProbability(int N, int maxR, int maxG, int maxB, int startR, int startG, int startB, int d1, int d2)
{
const int dx = d1-1;
vector< vector< vector<double> > > p(maxR, vector<vector<double> >(maxG, vector<double>(maxB)));
p[startR][startG][startB] = 1.0;
for(int i=1; i<N; ++i)
{
for(int r=0; r<maxR; ++r)
for(int g=0; g<maxG; ++g)
for(int b=0; b<maxB; ++b) {
int c = cnt(maxR, maxG, maxB, r-d2, r+d2, g-d2, g+d2, b-d2, b+d2)
- (d1==0 ? 0 : cnt(maxR, maxG, maxB, r-dx, r+dx, g-dx, g+dx, b-dx, b+dx));
if( c )
p[r][g][b] /= c;
else
p[r][g][b] = 0;
}
vector< vector< vector<double> > > low = p;
for(int rgb=0; rgb<=maxR+maxG+maxB-3; ++rgb)
for(int r=0; r<maxR; ++r)
for(int g=0; g<maxG; ++g)
{
int b = rgb-r-g;
if( 0<=b && b<maxB ) {
low[r][g][b] =
p[r][g][b]
+ (r ? low[r-1][g][b] : 0)
+ (g ? low[r][g-1][b] : 0)
+ (b ? low[r][g][b-1] : 0)
- (r&&g ? low[r-1][g-1][b] : 0)
- (g&&b ? low[r][g-1][b-1] : 0)
- (b&&r ? low[r-1][g][b-1] : 0)
+ (r&&g&&b ? low[r-1][g-1][b-1] : 0);
}
}
vector< vector< vector<double> > > q = p;
for(int r=0; r<maxR; ++r)
for(int g=0; g<maxG; ++g)
for(int b=0; b<maxB; ++b)
{
q[r][g][b] =
zone(low, r-d2, r+d2, g-d2, g+d2, b-d2, b+d2)
- (d1==0 ? 0 : zone(low, r-dx, r+dx, g-dx, g+dx, b-dx, b+dx));
}
p.swap(q);
}
vector< vector< vector<double> > > low = p;
for(int rgb=0; rgb<=maxR+maxG+maxB-3; ++rgb)
for(int r=0; r<maxR; ++r)
for(int g=0; g<maxG; ++g)
{
int b = rgb-r-g;
if( 0<=b && b<maxB ) {
low[r][g][b] =
p[r][g][b]
+ (r ? low[r-1][g][b] : 0)
+ (g ? low[r][g-1][b] : 0)
+ (b ? low[r][g][b-1] : 0)
- (r&&g ? low[r-1][g-1][b] : 0)
- (g&&b ? low[r][g-1][b-1] : 0)
- (b&&r ? low[r-1][g][b-1] : 0)
+ (r&&g&&b ? low[r-1][g-1][b-1] : 0);
}
}
return 1.0 - (
zone(low, startR-d2, startR+d2, startG-d2, startG+d2, startB-d2, startB+d2)
- (d1==0 ? 0 : zone(low, startR-dx, startR+dx, startG-dx, startG+dx, startB-dx, startB+dx))
);
}
double zone(const vector< vector< vector<double> > >& low,
int r, int R, int g, int G, int b, int B) {
r = max(0, min<int>(low.size()-1, r));
R = max(0, min<int>(low.size()-1, R));
g = max(0, min<int>(low[0].size()-1, g));
G = max(0, min<int>(low[0].size()-1, G));
b = max(0, min<int>(low[0][0].size()-1, b));
B = max(0, min<int>(low[0][0].size()-1, B));
return low[R][G][B]
- (r ? low[r-1][G][B] : 0)
- (g ? low[R][g-1][B] : 0)
- (b ? low[R][G][b-1] : 0)
+ (r&&g ? low[r-1][g-1][B] : 0)
+ (g&&b ? low[R][g-1][b-1] : 0)
+ (b&&r ? low[r-1][G][b-1] : 0)
- (r&&g&&b ? low[r-1][g-1][b-1] : 0);
}
int cnt(int maxR, int maxG, int maxB,
int r, int R, int g, int G, int b, int B) {
r = max(0, min<int>(maxR-1, r));
R = max(0, min<int>(maxR-1, R));
g = max(0, min<int>(maxG-1, g));
G = max(0, min<int>(maxG-1, G));
b = max(0, min<int>(maxB-1, b));
B = max(0, min<int>(maxB-1, B));
return (R-r+1)*(G-g+1)*(B-b+1);
}
};
// 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 double& Expected, const double& Received) {
bool ok = (abs(Expected - Received) < 1e-9);
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(_, RandomColoring().getProbability(N, maxR, maxG, maxB, startR, startG, startB, d1, d2));}
int main(){
CASE(0)
int N = 2;
int maxR = 5;
int maxG = 1;
int maxB = 1;
int startR = 2;
int startG = 0;
int startB = 0;
int d1 = 0;
int d2 = 1;
double _ = 0.0;
END
CASE(1)
int N = 3;
int maxR = 5;
int maxG = 1;
int maxB = 1;
int startR = 2;
int startG = 0;
int startB = 0;
int d1 = 0;
int d2 = 1;
double _ = 0.22222222222222227;
END
CASE(2)
int N = 7;
int maxR = 4;
int maxG = 2;
int maxB = 2;
int startR = 0;
int startG = 0;
int startB = 0;
int d1 = 3;
int d2 = 3;
double _ = 1.0;
END
CASE(3)
int N = 10;
int maxR = 7;
int maxG = 8;
int maxB = 9;
int startR = 1;
int startG = 2;
int startB = 3;
int d1 = 0;
int d2 = 10;
double _ = 0.0;
END
CASE(4)
int N = 10;
int maxR = 7;
int maxG = 8;
int maxB = 9;
int startR = 1;
int startG = 2;
int startB = 3;
int d1 = 4;
int d2 = 10;
double _ = 0.37826245943967396;
END
CASE(5)
int N = 3;
int maxR = 3;
int maxG = 2;
int maxB = 2;
int startR = 1;
int startG = 0;
int startB = 0;
int d1 = 1;
int d2 = 2;
double _ = 0.09090909090909148;
END
/*
CASE(6)
int N = ;
int maxR = ;
int maxG = ;
int maxB = ;
int startR = ;
int startG = ;
int startB = ;
int d1 = ;
int d2 = ;
double _ = ;
END
CASE(7)
int N = ;
int maxR = ;
int maxG = ;
int maxB = ;
int startR = ;
int startG = ;
int startB = ;
int d1 = ;
int d2 = ;
double _ = ;
END
*/
}
// END CUT HERE