Problem p02669 (python)

Fixed submission:

#from collections import defaultdict
#from pprint import pprint
#from collections import deque
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
#import numpy as np
#import math
# = map(int,input().split())

# = list(map(int,input().split()))

# = [list(map(int,input().split())) for _ in range(XXXX)]

def func(i):
    if i == 0:
        return 0
    elif i == 1:
        return d
    elif i in memo:
        return memo[i]
    else:
        min_val = int(min(
            d*i,
            d*abs(i-i//2*2) + a + func(i//2),
            d*abs(i-(i+1)//2*2) + a + func((i+1)//2),
            d*abs(i-i//3*3) + b + func(i//3),
            d*abs(i-(i+2)//3*3) + b + func((i+2)//3),
            d*abs(i-i//5*5) + c + func(i//5),
            d*abs(i-(i+4)//5*5) + c + func((i+4)//5)
        ))

    memo[i] = min_val
    return min_val



t = int(input())

nabcd = [list(map(int,input().split())) for _ in range(t)]


for i in range(t):
    n = nabcd[i][0]
    a = nabcd[i][1]
    b = nabcd[i][2]
    c = nabcd[i][3]
    d = nabcd[i][4]

    memo = {}


    print(func(n))
    #print(memo)

Buggy submission (verdict: Runtime Error):
#from collections import defaultdict
#from pprint import pprint
#from collections import deque
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
import numpy as np

# = map(int,input().split())

# = list(map(int,input().split()))

# = [list(map(int,input().split())) for _ in range(XXXX)]

t = int(input())

nabcd = [list(map(int,input().split())) for _ in range(t)]

for i in range(t):
    n = nabcd[i][0]
    a = nabcd[i][1]
    b = nabcd[i][2]
    c = nabcd[i][3]
    d = nabcd[i][4]

#配るDPで考える。
    dp = [10**10 for _ in range(5*(n-1)+1)]
    dp[0] = 0
    dp[1] = d
    j = 1
    while j < n:
        #print(j)
        #pt_a = pt_b = pt_c = pt_d = 10 ** 10
        pt_a = pt_b = pt_c = pt_d = float("inf")

        if dp[j] == 10**10:
            j += 1
            continue

        dp[j*2] = min(dp[j*2],dp[j] + a)

        dp[j*3] = min(dp[j*3],dp[j] + b)

        dp[j*5] = min(dp[j*5],dp[j] + c)

        dp[j+1] = min(dp[j+1],dp[j] + d)

        #if not j-1 in dp:
        #    dp[j-1] = dp[j] + d
        #    j -= 1
        #    continue
        #else:
        #    if dp[j-1] > dp[j] + d:
        #        dp[j-1] = dp[j] + d
        #        j -= 1
        #        continue
        j += 1
            
    
    print(dp[n])
    #print(dp[n])

    result = float("inf")

    for k in range(0,5*(n-1)+1-n):
        if n+k in dp:
            result = min(result,dp[n+k]+k*d)


    print(result)





#
#    #i進めるときに使うコインの最小値をdp[i]
#    dp = dict()
#    dp[0] = 0
#    dp[1] = d
#    j = 2
#    while True:
#        #print(j)
#        #pt_a = pt_b = pt_c = pt_d = float("inf")
#        pt_a = pt_b = pt_c = pt_d = 10 ** 10
#
#        if j >= a and j % 2 == 0:
#            pt_a = dp[j/2] + a
#        
#        if j >= b and j % 3 == 0:
#            pt_b = dp[j/3] + b
#
#        if j >= c and j % 5 == 0:
#            pt_c = dp[j/5] + c
#        
#        pt_d = dp[j-1] + d
#        if not j in dp:
#            dp[j] = min(pt_a,pt_b,pt_c,pt_d)
#        else:
#            dp[j] = min(dp[j],pt_a,pt_b,pt_c,pt_d)
#
#
#        if dp[j-1] > dp[j]+d:
#            dp[j-1] = dp[j]+d
#            j = j-1
#        else:
#            if j == n:
#                break
#            else:
#                j += 1
#
#    print(dp[n])
#
#    #切り上げ
#    end_point = (n-1)*5
#    j += 1
#    while True:
#        #pt_a = pt_b = pt_c = pt_d = float("inf")
#        pt_a = pt_b = pt_c = pt_d = 10 ** 10
#        if j >= a and j % 2 == 0:
#            pt_a = dp[j/2] + a
#        
#        if j >= b and j % 3 == 0:
#            pt_b = dp[j/3] + b
#
#        if j >= c and j % 5 == 0:
#            pt_c = dp[j/5] + c
#        
#        pt_d = dp[j-1] + d
#        if not j in dp:
#            dp[j] = min(pt_a,pt_b,pt_c,pt_d)
#        else:
#            dp[j] = min(dp[j],pt_a,pt_b,pt_c,pt_d)
#
#        if dp[j-1] > dp[j]+d:
#            dp[j-1] = dp[j]+d
#            j = j-1
#        else:
#            if j > dp[n]+end_point:
#                break
#            else:
#                j += 1
#    
#    print(dp[n])












# コインi枚で進める最大量がdp[i]と考えたとき
#    dp = defaultdict(int)
#    dp[d] = 1
#    j = d
#    while True:
#        j += 1
#        pt_a = pt_b = pt_c = pt_d = float("inf")
#        #aのパターン
#        if j >= a:
#            pt_a = dp[j-a]*2
#        
#        #bのパターン
#        if j >= b:
#            pt_b = dp[j-b]*3
#
#        #cのパターン
#        if j >= c:
#            pt_c = dp[j-c]*5
#
#        #dのパターン
#        pt_d = min(dp[j-d]+1,dp[j-d]-1)
#
#        pt_a = dp[i-1] + 1
#        if i>2 and i % 2 == 0:
#            pt_b = dp[i%2]

        



    #if n % 5 == 0:
    #    pass
    #elif n % 3 == 0:
    #    pass
    #elif n % 2 == 0:
    #    pass