Submission #2491044

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
#define double long double

struct Precision{
  Precision(){
    cout<<fixed<<setprecision(12);
  }
}precision_beet;

double dp2[111][111][111];
void calc(){
  for(Int i=0;i<111;i++)
    for(Int j=0;j<111;j++)
      for(Int k=0;k<111;k++)
	dp2[i][j][k]=0;
  dp2[0][0][0]=1;
  for(Int n=0;n<111;n++){
    for(Int i=0;i<=n;i++){
      for(Int j=0;i+j<=n;j++){
	Int k=n-(i+j);
	dp2[i+1][j][k]+=dp2[i][j][k]/3;
	dp2[i][j+1][k]+=dp2[i][j][k]/3;
	dp2[i][j][k+1]+=dp2[i][j][k]/3;
      }
    }	
  }
};

double dp[111];
Int used[111];
double dfs(Int n){
  if(n==1) return 0;
  if(used[n]) return dp[n];
  used[n]=1;
  double &res=dp[n];
  res=1;
  double pre=1.0;
  for(Int i=1;i*2<n;i++){
    res+=dp2[i][n-i][0]*6*dfs(i);
    pre-=dp2[i][n-i][0]*6;
  }
  if(n%2==0){
    res+=dp2[n/2][n/2][0]*3*dfs(n/2);
    pre-=dp2[n/2][n/2][0]*3;
  }
  res/=1.0-pre;
  return res;
}

//INSERT ABOVE HERE
signed main(){
  memset(used,0,sizeof(used));
  calc();
  
  Int n;
  cin>>n;
  cout<<dfs(n)<<endl;
  
  //for(Int i=1;i<100;i++) cout<<dfs(i)<<endl;
  return 0;
}

Submission Info

Judge Result