Contest Duration: ~ (local time) (120 minutes)

Submission #16778665

Source Code Expand

Copy
```import sys
sys.setrecursionlimit(10**7)

n=int(input())

cmb=[[1]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
cmb[i][1]=i
for j in range(2,i):
cmb[i][j]=cmb[i][j-1]*(i-j+1)
cmb[i][j]//=j

memo={}
memo[0]=0.
memo[1]=0.
def dp(k):
if k in memo:return memo[k]
ret=0
st=0
for i in range(1,1+k//2):
tmp=0
# i,k-i,0
if i<k-i:tmp+=cmb[k][i]*6
# i,i,k-2*i
if i<k-i*2:tmp+=cmb[k][i]*cmb[k-i][i]*3
# i,i,0
if 2*i==k:tmp+=cmb[k][i]*3
# i,j,k-i-j
for j in range(i+1,k):
if i<k-i-j:
tmp+=cmb[k][i]*cmb[k-i][j]*3
else:
break
ret+=(1+dp(i))*tmp*pow(3,-k)
st+=tmp
ret+=(pow(3,k)-st)*pow(3,-k)
ret/=1-(pow(3,k)-st)*pow(3,-k)
memo[k]=ret
return ret
print(dp(n))
```

#### Submission Info

Submission Time 2020-09-16 14:47:59+0900 C - ゲーマーじゃんけん persimmon_t01 PyPy3 (7.3.0) 100 890 Byte AC 229 ms 74584 KB

#### Judge Result

Set Name All
Score / Max Score 100 / 100
Status
 AC × 99
Set Name Test Cases
All input-002.txt, input-003.txt, input-004.txt, input-005.txt, input-006.txt, input-007.txt, input-008.txt, input-009.txt, input-010.txt, input-011.txt, input-012.txt, input-013.txt, input-014.txt, input-015.txt, input-016.txt, input-017.txt, input-018.txt, input-019.txt, input-020.txt, input-021.txt, input-022.txt, input-023.txt, input-024.txt, input-025.txt, input-026.txt, input-027.txt, input-028.txt, input-029.txt, input-030.txt, input-031.txt, input-032.txt, input-033.txt, input-034.txt, input-035.txt, input-036.txt, input-037.txt, input-038.txt, input-039.txt, input-040.txt, input-041.txt, input-042.txt, input-043.txt, input-044.txt, input-045.txt, input-046.txt, input-047.txt, input-048.txt, input-049.txt, input-050.txt, input-051.txt, input-052.txt, input-053.txt, input-054.txt, input-055.txt, input-056.txt, input-057.txt, input-058.txt, input-059.txt, input-060.txt, input-061.txt, input-062.txt, input-063.txt, input-064.txt, input-065.txt, input-066.txt, input-067.txt, input-068.txt, input-069.txt, input-070.txt, input-071.txt, input-072.txt, input-073.txt, input-074.txt, input-075.txt, input-076.txt, input-077.txt, input-078.txt, input-079.txt, input-080.txt, input-081.txt, input-082.txt, input-083.txt, input-084.txt, input-085.txt, input-086.txt, input-087.txt, input-088.txt, input-089.txt, input-090.txt, input-091.txt, input-092.txt, input-093.txt, input-094.txt, input-095.txt, input-096.txt, input-097.txt, input-098.txt, input-099.txt, input-100.txt
Case Name Status Exec Time Memory
input-002.txt 229 ms 61480 KB
input-003.txt 54 ms 61700 KB
input-004.txt 58 ms 61940 KB
input-005.txt 59 ms 61564 KB
input-006.txt 59 ms 61560 KB
input-007.txt 63 ms 61724 KB
input-008.txt 57 ms 61744 KB
input-009.txt 58 ms 61588 KB
input-010.txt 55 ms 61520 KB
input-011.txt 56 ms 61504 KB
input-012.txt 53 ms 61804 KB
input-013.txt 51 ms 61612 KB
input-014.txt 56 ms 61808 KB
input-015.txt 59 ms 61628 KB
input-016.txt 53 ms 61756 KB
input-017.txt 58 ms 61660 KB
input-018.txt 60 ms 61612 KB
input-019.txt 61 ms 61708 KB
input-020.txt 51 ms 61704 KB
input-021.txt 57 ms 61968 KB
input-022.txt 58 ms 62088 KB
input-023.txt 60 ms 61912 KB
input-024.txt 61 ms 61688 KB
input-025.txt 60 ms 61696 KB
input-026.txt 58 ms 61872 KB
input-027.txt 58 ms 61724 KB
input-028.txt 58 ms 61984 KB
input-029.txt 58 ms 61880 KB
input-030.txt 53 ms 61792 KB
input-031.txt 58 ms 62072 KB
input-032.txt 61 ms 62288 KB
input-033.txt 56 ms 62072 KB
input-034.txt 61 ms 61908 KB
input-035.txt 58 ms 61952 KB
input-036.txt 59 ms 61936 KB
input-037.txt 52 ms 62396 KB
input-038.txt 57 ms 62252 KB
input-039.txt 58 ms 62000 KB
input-040.txt 55 ms 62040 KB
input-041.txt 56 ms 62112 KB
input-042.txt 59 ms 62368 KB
input-043.txt 53 ms 62184 KB
input-044.txt 59 ms 62420 KB
input-045.txt 62 ms 62460 KB
input-046.txt 52 ms 62488 KB
input-047.txt 53 ms 62624 KB
input-048.txt 62 ms 64408 KB
input-049.txt 61 ms 64308 KB
input-050.txt 54 ms 65032 KB
input-051.txt 62 ms 65360 KB
input-052.txt 59 ms 65148 KB
input-053.txt 55 ms 65324 KB
input-054.txt 64 ms 65300 KB
input-055.txt 61 ms 68608 KB
input-056.txt 61 ms 65492 KB
input-057.txt 67 ms 65420 KB
input-058.txt 61 ms 65412 KB
input-059.txt 61 ms 65488 KB
input-060.txt 65 ms 68572 KB
input-061.txt 56 ms 65504 KB
input-062.txt 65 ms 65700 KB
input-063.txt 68 ms 65572 KB
input-064.txt 67 ms 65936 KB
input-065.txt 69 ms 65952 KB
input-066.txt 59 ms 65932 KB
input-067.txt 64 ms 66672 KB
input-068.txt 60 ms 66804 KB
input-069.txt 65 ms 67112 KB
input-070.txt 68 ms 66840 KB
input-071.txt 65 ms 74284 KB
input-072.txt 64 ms 69920 KB
input-073.txt 60 ms 67160 KB
input-074.txt 68 ms 68076 KB
input-075.txt 68 ms 67832 KB
input-076.txt 62 ms 67956 KB
input-077.txt 75 ms 74488 KB
input-078.txt 69 ms 68964 KB
input-079.txt 73 ms 70876 KB
input-080.txt 63 ms 68412 KB
input-081.txt 64 ms 70900 KB
input-082.txt 70 ms 71148 KB
input-083.txt 71 ms 70140 KB
input-084.txt 83 ms 74584 KB
input-085.txt 73 ms 71172 KB
input-086.txt 65 ms 71380 KB
input-087.txt 73 ms 71124 KB
input-088.txt 75 ms 71136 KB
input-089.txt 75 ms 72108 KB
input-090.txt 76 ms 73844 KB
input-091.txt 77 ms 73908 KB
input-092.txt 76 ms 72064 KB
input-093.txt 74 ms 73868 KB
input-094.txt 72 ms 73996 KB
input-095.txt 77 ms 73888 KB
input-096.txt 78 ms 73960 KB
input-097.txt 76 ms 73904 KB
input-098.txt 82 ms 74012 KB
input-099.txt 81 ms 73988 KB
input-100.txt 78 ms 74204 KB