Submission #7512863

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

map<int, double> memo;

double comb(int a, int b){
    if(a < 2 * b) return comb(a, a-b);
    double res = 1;
    for(int i=a; i>a-b; i--){
        res *= i;
    }
    for(int i=2; i<=b; i++){
        res /= i;
    }
    return res;
}

double dfs(int N){
    if(N==1) return 0;
    if(N==2) return 3./2;
    if(memo.count(N)) return memo[N];
    double res = 0;
    for(int i=1; i<(N+2)/3; i++){
        res += 3 * comb(N, i) * comb(N-i, i) * dfs(2 * i);
    }
    res = 1 + res / pow(3, N);
    double p = 3 / pow(3, N);
    if(N%3==0){
        p += (comb(N, N/3) * comb(N-N/3, N/3)) / pow(3, N);
    }
    res /= 1-p;
    memo[N] = res;
    return res;
}

int main()
{
    int N;
    cin >> N;
    cout<<setprecision(10)<< dfs(N) << endl;;

    return 0;
}

Submission Info

Judge Result