Submission #7470335

---

Source Code Expand

class comb():
  F = [1, 1]
  def __init__(self, num):
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i))
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] // (self.F[n - k] * self.F[k])

def nasu(x, y, n):
  return com.com(n, x) * com.com(n - x, y)


N = int(input())

DP = [0] * (N + 1)
DP[0] = 0
DP[1] = 0
com = comb(N)

for i in range(2, N + 1):
  T = [0] * (i + 1)
  for g in range(i + 1):
    for c in range(i - g + 1):
      F = False
      p = i - c - g
      if max(g, c, p) == i:
        T[-1] += 1
        continue
      if g == 0:
        T[min(c, p)] += nasu(min(c, p), 0, i)
      elif c == 0:
        T[min(g, p)] += nasu(min(g, p), 0, i)
      elif p == 0:
        T[min(g, c)] += nasu(min(g, c), 0, i)
      else:
        if g == c and c == p:
          T[-1] += nasu(g, c, i)
          continue
        if g != c and g != p and c != p:
          if min(g, c, p) == g:
            T[g] += nasu(g, c, i)
          elif min(g, c, p) == c:
            T[c] += nasu(c, g, i)
          else:
            T[p] += nasu(p, g, i)
        if g == c:
          if p == min(g, p):
            T[p] += nasu(p, g, i)
          else:
            T[g] += nasu(g, c, i)
        elif g == p:
          if c == min(g, c):
            T[c] += nasu(c, g, i)
          else:
            T[g] += nasu(g, p, i)
        elif c == p:
          if g == min(g, c):
            T[g] += nasu(g, c, i)
          else:
            T[c] += nasu(c, p, i)
  su = pow(3, i)
  lp = T[-1]
  #print(i, T, su)
  for j in range(i):
    if T[j] == 0: continue
    DP[i] += (DP[j] + su / (su - lp)) * T[j]
  DP[i] /= (su - lp)
#print(DP)
print(DP[-1])

Submission Info

Judge Result