提出 #18352622


ソースコード 拡げる

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()

提出情報

提出日時
問題 D - サイコロ
ユーザ noymer
言語 Python (3.8.2)
得点 4
コード長 1613 Byte
結果 AC
実行時間 176 ms
メモリ 14004 KB

ジャッジ結果

セット名 All
得点 / 配点 4 / 4
結果
AC × 13
セット名 テストケース
All 00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 90, 91
ケース名 結果 実行時間 メモリ
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