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

Submission #16777954

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={}
def dp(k,depth):
if k in memo:return memo[k]
if k==0:return 0
if k==1:return 0
if k==2:return 1.5
if k==3:return 1.5
# 10人->10,5,4,3,2,1
# 100人->100,50,49,48,,,1
if depth>50:return 0
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,depth+1))*tmp*pow(3,-k)
st+=tmp
ret+=(1+dp(k,depth+1))*(pow(3,k)-st)*pow(3,-k)
memo[k]=ret
return ret
print(dp(n,0))```

#### Submission Info

Submission Time 2020-09-16 13:50:23+0900 C - ゲーマーじゃんけん persimmon_t01 PyPy3 (7.3.0) 100 1077 Byte AC 157 ms 79664 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 65 ms 61768 KB
input-003.txt 59 ms 61756 KB
input-004.txt 60 ms 62188 KB
input-005.txt 52 ms 62516 KB
input-006.txt 53 ms 62432 KB
input-007.txt 57 ms 62504 KB
input-008.txt 60 ms 62928 KB
input-009.txt 55 ms 62792 KB
input-010.txt 60 ms 63248 KB
input-011.txt 59 ms 63344 KB
input-012.txt 58 ms 63868 KB
input-013.txt 63 ms 65112 KB
input-014.txt 64 ms 65488 KB
input-015.txt 61 ms 65656 KB
input-016.txt 65 ms 67116 KB
input-017.txt 63 ms 69128 KB
input-018.txt 69 ms 70032 KB
input-019.txt 62 ms 70304 KB
input-020.txt 76 ms 72104 KB
input-021.txt 68 ms 74200 KB
input-022.txt 82 ms 74728 KB
input-023.txt 84 ms 74696 KB
input-024.txt 83 ms 74612 KB
input-025.txt 78 ms 74784 KB
input-026.txt 81 ms 74788 KB
input-027.txt 85 ms 74988 KB
input-028.txt 87 ms 74512 KB
input-029.txt 85 ms 75092 KB
input-030.txt 89 ms 74532 KB
input-031.txt 94 ms 74856 KB
input-032.txt 94 ms 74952 KB
input-033.txt 91 ms 75016 KB
input-034.txt 93 ms 74712 KB
input-035.txt 94 ms 75256 KB
input-036.txt 95 ms 75560 KB
input-037.txt 90 ms 74696 KB
input-038.txt 91 ms 74864 KB
input-039.txt 92 ms 74380 KB
input-040.txt 95 ms 74508 KB
input-041.txt 97 ms 74488 KB
input-042.txt 98 ms 74300 KB
input-043.txt 97 ms 75044 KB
input-044.txt 101 ms 75176 KB
input-045.txt 104 ms 79256 KB
input-046.txt 104 ms 75884 KB
input-047.txt 108 ms 75360 KB
input-048.txt 112 ms 77892 KB
input-049.txt 117 ms 77528 KB
input-050.txt 109 ms 75436 KB
input-051.txt 108 ms 75648 KB
input-052.txt 103 ms 75320 KB
input-053.txt 113 ms 75848 KB
input-054.txt 110 ms 77612 KB
input-055.txt 123 ms 78164 KB
input-056.txt 112 ms 75796 KB
input-057.txt 115 ms 77960 KB
input-058.txt 103 ms 75384 KB
input-059.txt 107 ms 75516 KB
input-060.txt 117 ms 78280 KB
input-061.txt 113 ms 75844 KB
input-062.txt 117 ms 78668 KB
input-063.txt 120 ms 77500 KB
input-064.txt 124 ms 78448 KB
input-065.txt 116 ms 77468 KB
input-066.txt 121 ms 78504 KB
input-067.txt 120 ms 77184 KB
input-068.txt 120 ms 76312 KB
input-069.txt 119 ms 77028 KB
input-070.txt 126 ms 76656 KB
input-071.txt 124 ms 76444 KB
input-072.txt 126 ms 76424 KB
input-073.txt 124 ms 76376 KB
input-074.txt 123 ms 76048 KB
input-075.txt 122 ms 75832 KB
input-076.txt 120 ms 76904 KB
input-077.txt 118 ms 76840 KB
input-078.txt 131 ms 78536 KB
input-079.txt 128 ms 78244 KB
input-080.txt 129 ms 79004 KB
input-081.txt 119 ms 76736 KB
input-082.txt 121 ms 76456 KB
input-083.txt 128 ms 78720 KB
input-084.txt 136 ms 78592 KB
input-085.txt 135 ms 79168 KB
input-086.txt 137 ms 79460 KB
input-087.txt 126 ms 77688 KB
input-088.txt 143 ms 77244 KB
input-089.txt 138 ms 78840 KB
input-090.txt 143 ms 79664 KB
input-091.txt 140 ms 79620 KB
input-092.txt 139 ms 77304 KB
input-093.txt 139 ms 78340 KB
input-094.txt 156 ms 79628 KB
input-095.txt 151 ms 78364 KB
input-096.txt 149 ms 77776 KB
input-097.txt 139 ms 78408 KB
input-098.txt 157 ms 79256 KB
input-099.txt 152 ms 79316 KB
input-100.txt 152 ms 79476 KB