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][c2][c3][c5] += add
                    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
Task D - サイコロ
User noymer
Language Python (3.8.2)
Score 4
Code Size 1613 Byte
Status AC
Exec Time 176 ms
Memory 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