Submission #1026602

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,x,n) for(int i=x; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()
#define X first
#define Y second
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

template<class A, size_t N, class T> void Fill(A (&a)[N], const T &v){ fill( (T*)a, (T*)(a+N), v ); }

const ll INF = 0x3fffffff;
const ll MOD = 1e9+7;

ll cmb_memo[10005][10005]={};
ll cmb(int n, int r){
	if( cmb_memo[n][r] ) return cmb_memo[n][r];
	if( r == 0 || r == n ) return 1;
	return cmb_memo[n][r] = (cmb(n-1,r) + cmb(n-1,r-1)) % MOD;
}

double memo[200]={};
double solve(int N){
//	cout << "solve N=" << N << endl;
	if( N <= 1 ) return 0;
	if( memo[N] ) return memo[N];
	double stay_rate=0.0, nex_e=0.0, nex_rate=0.0, sum=0.0;
	rep(g,N+1) rep(t,N+1-g) rep(p,N+1-g-t){
		if( g + t + p != N ) continue;
		double num = cmb(N, g) * cmb(N-g, t);
//		cout << "N=" << N << "\tg=" << g << " t=" << t << " p=" << p << " num=" << num << endl;
		sum += num;
		     if( g == 0 && t == 0 ) stay_rate += num;
		else if( t == 0 && p == 0 ) stay_rate += num;
		else if( p == 0 && g == 0 ) stay_rate += num;
		else if( g == t && t == p ) stay_rate += num;
		else if( g == 0 && t <= p ){ nex_e += solve(t); nex_rate += num; }
		else if( t == 0 && p <= g ){ nex_e += solve(p); nex_rate += num; }
		else if( p == 0 && g <= t ){ nex_e += solve(g); nex_rate += num; }
		else if( g == 0 && t > p  ){ nex_e += solve(p); nex_rate += num; }
		else if( t == 0 && p > g  ){ nex_e += solve(g); nex_rate += num; }
		else if( p == 0 && g > t  ){ nex_e += solve(t); nex_rate += num; }
		else if( g < t  && g < p  ){ nex_e += solve(g); nex_rate += num; }
		else if( t < g  && t < p  ){ nex_e += solve(t); nex_rate += num; }
		else if( p < g  && p < t  ){ nex_e += solve(p); nex_rate += num; }
		else if( g == t && t < p  ){ nex_e += solve(g); nex_rate += num; }
		else if( t == p && p < g  ){ nex_e += solve(t); nex_rate += num; }
		else if( p == g && g < t  ){ nex_e += solve(p); nex_rate += num; }
	}
	stay_rate /= sum;
	nex_rate /= sum;
//	cout << "stay_rate=" << stay_rate << "\tnex_e=" << nex_e << "\tnex_rate=" << nex_rate << endl;
	double rate=1.0;
	rep(i,100){
		//memo[N] += rate * (1.0-stay_rate) * ((double)(i+1) + nex_e);
		memo[N] += rate * nex_rate * ((double)(i+1) + nex_e);
		rate *= stay_rate;
	}
	return memo[N];
}

int main(){
	//ios_base::sync_with_stdio(0);
	int N, ans=0;

	cin >> N;

	printf("%.8f\n", solve(N) );

	return 0;
}

Submission Info

Judge Result