Contest Duration: - (local time) (300 minutes) Back to Home

Submission #18352622

Source Code Expand

Copy
```#!/usr/bin/env python3
# from typing import *

dp = {}
dp[0, 0, 0, 0] = 1

def dfs(n, k2, k3, k5):
if (n, k2, k3, k5) in dp:
return dp[n, k2, k3, k5]

dfs(n-1, k2, k3, k5) \
+ dfs(n-1, k2-1, k3, k5) \
+ dfs(n-1, k2, k3-1, k5) \
+ dfs(n-1, k2-2, k3, k5) \
+ dfs(n-1, k2, k3, k5-1) \
+ dfs(n-1, k2-1, k3-1, k5)

# def solve(a: int, b: int) -> float:
def solve(N, D):
k2 = 0
k3 = 0
k5 = 0
while D % 2 == 0:
D = D // 2
k2+=1
while D % 3 == 0:
D = D // 3
k3+=1
while D % 5 == 0:
D = D // 5
k5+=1

if D != 1:
return 0

dp = [[[[0 for _ in range(k5+1)] for _ in range(k3+1)] for _ in range(k2+1)] for _ in range(N+1)]

dp[0][0][0][0] = 1
for n in range(N):
for c2 in range(k2+1):
for c3 in range(k3+1):
for c5 in range(k5+1):

p = dp[n][c2][c3][c5]
add = p / 6

dp[n+1][min(c2+1, k2)][c3][c5] += add
dp[n+1][c2][min(c3+1, k3)][c5] += add
dp[n+1][min(c2+2, k2)][c3][c5] += add
dp[n+1][c2][c3][min(c5+1, k5)] += add
dp[n+1][min(c2+1, k2)][min(c3+1, k3)][c5] += add

return dp[N][k2][k3][k5]

# generated by online-judge-template-generator v4.7.1 (https://github.com/online-judge-tools/template-generator)
def main():
a, b = map(int, input().split())
a1 = solve(a, b)
print(a1)

if __name__ == '__main__':
main()
```

#### Submission Info

Submission Time 2020-11-23 00:51:44+0900 D - サイコロ noymer Python (3.8.2) 4 1613 Byte AC 176 ms 14004 KB

#### Judge Result

Set Name All
Score / Max Score 4 / 4
Status
 AC × 13
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 90, 91
Case Name Status Exec Time Memory
00 AC 28 ms 9020 KB
01 AC 149 ms 12464 KB
02 AC 68 ms 9928 KB
03 AC 74 ms 10108 KB
04 AC 48 ms 9416 KB
05 AC 176 ms 12700 KB
06 AC 152 ms 14004 KB
07 AC 96 ms 12952 KB
08 AC 71 ms 10108 KB
09 AC 37 ms 9572 KB
10 AC 21 ms 9120 KB
90 AC 22 ms 9272 KB
91 AC 18 ms 9272 KB