Submission #324811

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long double ldb;
typedef long long ll;

ldb cdp[111][111];

ldb C(int n,int r)
{
  if( n==r || r==0 ) return 1;
  if(cdp[n][r]>=0)return cdp[n][r];
  return cdp[n][r]=C(n-1,r)+C(n-1,r-1);
}

ldb dp[111];
ldb f(int a)
{
  ldb ret=1;
  while( a-- ) ret *= 3;
  return ret;
}

ldb solve(int n)
{
  if(n==1) return 0;
  if(dp[n]>=0)return dp[n];
  ldb res=1;
  ldb cnt[111] = {};
  //ldb b = pow(3,n);
  ldb b = f(n);
  for( int i = 0; i <= n; i++ ) {
    for( int j = 0; j <= n-i; j++ ) {
      int k = n-j-i;
      int v[]={i,j,k},m=114514;
      for( int ii = 0; ii < 3; ii++ ) if(v[ii]>0&&v[ii]<m) m=v[ii];
      //cnt[m] += 1;
      ldb p = 1*C(n,i)*C(n-i,j);
      //printf("%d %d %d %.0Lf %d\n",i,j,k,p,m);
      switch( count(v,v+3,m) ) {
      case 1:
        if( m == n ) {
          cnt[n] += p;
        } else {
          cnt[m] += p;
        }
        break;
      case 2:
        cnt[m] += p;
        break;
      case 3:
        cnt[n] += p;
        break;
      }
    }
  }
  //for( int i = 1; i <= n; i++ ) {
  //printf("%d:%.0Lf\n",n,cnt[i]);
  //}
  for( int i = n-1; i >= 1; i-- ) {
    res += ((cnt[i]/b)*solve(i));
  }
  res /= (1-cnt[n]/b);
  return dp[n]=res;
}

int main(void)
{
  int n;
  scanf("%d",&n);
  for(int i=0;i<111;i++)for(int j=0;j<111;j++)cdp[i][j]=-1;
  for(int i=0;i<111;i++)dp[i]=-1;
  /*
  srand(time(0));
  ll res = 0;
  const ll a = 100000000*n;
  for( int i = 0; i < a; i++ ) {
    res += sim(n);
  }
  printf("%lld %.10Lf\n",res,ld(res)/a);
  */
  printf("%.10Lf\n",solve(n));
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:71:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
                 ^

Judge Result