Problem:


Score : 400 points

Problem Statement

You start with the number 0 and you want to reach the number N.

You can change the number, paying a certain amount of coins, with the following operations:

Multiply the number by 2, paying A coins.

Multiply the number by 3, paying B coins.

Multiply the number by 5, paying C coins.

Increase or decrease the number by 1, paying D coins.

You can perform these operations in arbitrary order and an arbitrary number of times.

What is the minimum number of coins you need to reach N?

You have to solve T testcases.

Constraints

1 \le T \le 10

1 \le N \le 10^{18}

1 \le A, B, C, D \le 10^9

All numbers N, A, B, C, D are integers.

Input

The input is given from Standard Input. The first line of the input is

T

Then, T lines follow describing the T testcases.
Each of the T lines has the format

N A B C D

Output

For each testcase, print the answer on Standard Output followed by a newline.

Sample Input 1

5
11 1 2 4 8
11 1 2 2 8
32 10 8 5 4
29384293847243 454353412 332423423 934923490 1
900000000000000000 332423423 454353412 934923490 987654321

Sample Output 1

20
19
26
3821859835
23441258666

For the first testcase, a sequence of moves that achieves the minimum cost of 20 is:

Initially x = 0.

Pay 8 to increase by 1 (x = 1).

Pay 1 to multiply by 2 (x = 2).

Pay 1 to multiply by 2 (x = 4).

Pay 2 to multiply by 3 (x = 12).

Pay 8 to decrease by 1 (x = 11).

For the second testcase, a sequence of moves that achieves the minimum cost of 19 is:

Initially x = 0.

Pay 8 to increase by 1 (x = 1).

Pay 1 to multiply by 2 (x = 2).

Pay 2 to multiply by 5 (x = 10).

Pay 8 to increase by 1 (x = 11).



Sample input:
5
11 1 2 4 8
11 1 2 2 8
32 10 8 5 4
29384293847243 454353412 332423423 934923490 1
900000000000000000 332423423 454353412 934923490 987654321


Sample output:
20
19
26
3821859835
23441258666

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

T = ri()
P = []
for i in range(T):
    P.append(rl())

import heapq

def solve(N, A, B, C, D):
    heap = []
    heapq.heappush(heap, (0, N))
    visited = {}

    while heap:
        #print(heap)
        c, n = heapq.heappop(heap)
        if n == 0:
            return c
        cands = [(A, 2), (B, 3), (C, 5), (D, 1)]
        for cost, div in cands:
            ncs = []
            if div == 1:
                next_n = 0
                next_c = D*n
                ncs.append((next_n, next_c))
            elif n % div == 0:
                next_n = n // div
                next_c = cost
                ncs.append((next_n, next_c))
            else:
                r = n % div
                next_n = (n-r) // div
                next_c = cost + r*D
                ncs.append((next_n, next_c))
                next_n = (n+r) // div
                next_c = cost + (div-r)*D
                ncs.append((next_n, next_c))
            for next_n, next_c in ncs:
                next_c += c
                if next_n in visited:
                    if visited[next_n] <= next_c:
                        continue
                visited[next_n] = next_c
                heapq.heappush(heap, (next_c, next_n))
    return -1

for p in P:
    ans = solve(*p)
    print(ans)

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

T = int(input())


@lru_cache(maxsize=None)
def dfs(n, A, B, C, D):
    # 1
    ans = n * D

    for mul, pt in [(2, A), (3, B), (5, C)]:
        if n % mul == 0:
            n1 = n // mul
            a = dfs(n1, A, B, C, D) + pt
            ans = min(a, ans)
        elif mul <= n:
            md = n % mul
            n1 = (n - md) // mul
            n2 = (n + mul - md) // mul
            a = dfs(n1, A, B, C, D) + (D * md) + pt
            b = dfs(n2, A, B, C, D) + ((mul - md) * D) + pt
            ans = min(a, b, ans)

    return ans


def solve():
    N, A, B, C, D = map(int, input().split())

    ans = dfs(N, A, B, C, D)
    return ans


ans = []
for _ in range(T):
    t = solve()
    ans.append(t)

print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

from heapq import *
def solve():
    n,a,b,c,d = [int(i) for i in readline().split()]

    ans = 10**18
    q = [(0,n)] #(そこまでの距離、点)
    dic = {n:0}
    while q:
        cost,v = heappop(q)
        if dic[v] < cost: continue

        ans = min(ans,cost+d*v)
        for x in [2,3,5]:
            for y in range(-x+1,x):
                if (v+y)%x==0:
                    nv = (v+y)//x
                    nc = cost + d*abs(y) + a*(x==2) + b*(x==3) + c*(x==5)
                    if nv not in dic or nc < dic[nv]:
                        dic[nv] =  nc
                        heappush(q,(nc,nv))
                    

    print(ans)
    return



t = int(input())
for _ in range(t):
    solve()

Submission status: Accepted

Solution code:
from math import inf


def main(N, A, B, C, D):
    if N == 1:
        return D
    if N in dp:
        return dp[N]
    r = inf
    if N % 2 != 0:
        r = min(
            A + main(N // 2 + 1, A, B, C, D) + D,
            A + main(N // 2, A, B, C, D) + D,
            r
        )
    else:
        r = min(
            A + main(N // 2, A, B, C, D),
            r
        )
    if N % 3 != 0:
        r = min(
            B + main(N // 3 + 1, A, B, C, D) + (3 - N % 3) * D,
            B + main(N // 3, A, B, C, D) + (N % 3 * D),
            r
        )
    else:
        r = min(
            B + main(N // 3, A, B, C, D),
            r
        )
    if N % 5 != 0:
        r = min(
            C + main(N // 5 + 1, A, B, C, D) + (5 - N % 5) * D,
            C + main(N // 5, A, B, C, D) + (N % 5 * D),
            r
        )
    else:
        r = min(
            C + main(N // 5, A, B, C, D),
            r
        )
    r = min(N * D, r)
    dp[N] = r
    return r

T = int(input())
q_list = [[int(s) for s in input().split()] for _ in range(T)]
for q in q_list:
    dp = {0: 0}
    print(main(*q))

Submission status: Accepted

Solution code:
from functools import lru_cache

z = 0
n = 0
a = 0
b = 0
c = 0
d = 0

@lru_cache(maxsize=None)
def solve(x):
    global a
    global b
    global c
    global d

    if x==0:
        return 0
    if x==1:
        return d

    ans = d*x
    for p in [2,3,5]:
        m = x%p
        nxt = x//p
        A = a
        if p == 3:
            A = b
        if p == 5:
            A = c
        if nxt < x:
            cst = m*d + min(A, (nxt*p-nxt)*d) + solve(nxt)
            ans = min(ans, cst)
        nxt = (x+p-m)//p
        if nxt < x:
            cst = min((p-m)*d + A + solve(nxt), (x-nxt)*d + solve(nxt))
            ans = min(ans, cst)

    #print(x, ans)
    return ans

z = int(input())

for _ in range(z):
    n, a, b, c, d = map(int, input().split())
    print(solve(n))
    solve.cache_clear()

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify, heappush as hpush, heappop as hpop

def dijkstra(n, E, i0=0):
    h = [[0, i0]]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        d, i = hpop(h)
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] > nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return D






T = int(input())
for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    S = set()
    E = []
    Q = deque([N])
    while Q:
        x = deque.popleft(Q)
        if x in S: continue
        S.add(x)
        if x == 0: continue
        if x <= 10:
            nx = 0
            dd = D * x
            deque.append(Q, nx)
            E.append((x, nx, dd))
        if x % 2 == 0:
            nx = x // 2
            dd = min(A, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
        elif x > 1:
            nx = x // 2
            dd = min(A + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
            nx = x // 2 + 1
            dd = min(A + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
        if x % 3 == 0:
            nx = x // 3
            dd = min(B, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
        elif x % 3 == 1:
            nx = x // 3
            dd = min(B + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
        else:
            nx = x // 3 + 1
            dd = min(B + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
        if x % 5 == 0:
            nx = x // 5
            dd = min(C, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
        elif x % 5 == 1:
            nx = x // 5
            dd = min(C + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
        elif x % 5 == 2:
            nx = x // 5
            dd = min(C + D * 2, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
        elif x % 5 == 3:
            nx = x // 5 + 1
            dd = min(C + D * 2, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
            
        elif x % 5 == 4:
            nx = x // 5 + 1
            dd = min(C + D, (x - nx) * D)
            deque.append(Q, nx)
            E.append((x, nx, dd))
    
    # print("E =", len(E), E)
    A = []
    for a, b, d in E:
        A.append(a)
        A.append(b)
    A = sorted(list(set(A)))
    I = {a: i for i, a in enumerate(A)}
    E = [(I[a], I[b], d) for a, b, d in E]
    NN = len(A)
    # print("E =", len(E), E)
    EE = [[] for _ in range(NN)]
    for a, b, d in E:
        EE[a].append((b, d))
    print(dijkstra(NN, EE, I[N])[0])
    
    # print("-----")

Submission status: Accepted

Solution code:
import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


T = int(sys.stdin.buffer.readline())
NABCD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(T)]


def solve2(N, A, B, C, D):
    heap = []
    dist = defaultdict(lambda: INF)
    dist[0] = 0
    dist[N] = D * N
    heapq.heappush(heap, (0, 0))
    while heap:
        cnt, n = heapq.heappop(heap)
        if dist[N] <= cnt:
            break
        if dist[n] < cnt:
            continue
        if n == N:
            break
        if n > N:
            dist[n] = cnt + abs(N - n)
        if cnt + A < dist[n * 2]:
            dist[n * 2] = cnt + A
            heapq.heappush(heap, (cnt + A, n * 2))
        if cnt + B < dist[n * 3]:
            dist[n * 3] = cnt + B
            heapq.heappush(heap, (cnt + B, n * 3))
        if cnt + C < dist[n * 5]:
            dist[n * 5] = cnt + C
            heapq.heappush(heap, (cnt + C, n * 5))
        if cnt + D < dist[n + 1]:
            dist[n + 1] = cnt + D
            heapq.heappush(heap, (cnt + D, n + 1))
        if cnt + D < dist[n - 1] and n - 1 > 0:
            dist[n - 1] = cnt + D
            heapq.heappush(heap, (cnt + D, n - 1))
    return dist[N]


def solve(N, A, B, C, D):
    dist = defaultdict(lambda: INF)
    dist[N] = 0
    # dist[0] = N * D
    heap = [(0, N)]
    while heap:
        cnt, n = heapq.heappop(heap)
        if dist[n] < cnt:
            continue
        if n <= 5:
            dist[0] = min(dist[0], cnt + n * D)

        if cnt + abs(n - n // 2) * D < dist[n // 2]:
            dist[n // 2] = cnt + abs(n - n // 2) * D
            heapq.heappush(heap, (cnt + abs(n - n // 2) * D, n // 2))
        if cnt + abs(n - n // 3) * D < dist[n // 3]:
            dist[n // 3] = cnt + abs(n - n // 3) * D
            heapq.heappush(heap, (cnt + abs(n - n // 3) * D, n // 3))
        if cnt + abs(n - n // 5) * D < dist[n // 5]:
            dist[n // 5] = cnt + abs(n - n // 5) * D
            heapq.heappush(heap, (cnt + abs(n - n // 5) * D, n // 5))

        l = n // 2 * 2
        d = A + abs(l - n) * D
        if A < abs(n - l // 2) * D and cnt + d < dist[l // 2]:
            dist[l // 2] = cnt + d
            heapq.heappush(heap, (cnt + d, l // 2))
        r = l + 2
        d = A + abs(r - n) * D
        if A < abs(n - r // 2) * D and cnt + d < dist[r // 2]:
            dist[r // 2] = cnt + d
            heapq.heappush(heap, (cnt + d, r // 2))

        l = n // 3 * 3
        d = B + abs(l - n) * D
        if B < abs(n - l // 3) * D and cnt + d < dist[l // 3]:
            dist[l // 3] = cnt + d
            heapq.heappush(heap, (cnt + d, l // 3))
        r = l + 3
        d = B + abs(r - n) * D
        if B < abs(n - r // 3) * D and cnt + d < dist[r // 3]:
            dist[r // 3] = cnt + d
            heapq.heappush(heap, (cnt + d, r // 3))

        l = n // 5 * 5
        d = C + abs(l - n) * D
        if C < abs(n - l // 5) * D and cnt + d < dist[l // 5]:
            dist[l // 5] = cnt + d
            heapq.heappush(heap, (cnt + d, l // 5))
        r = l + 5
        d = C + abs(r - n) * D
        if C < abs(n - r // 5) * D and cnt + d < dist[r // 5]:
            dist[r // 5] = cnt + d
            heapq.heappush(heap, (cnt + d, r // 5))

    return dist[0]


for r in NABCD:
    ans = solve(*r)
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

class Data:
    def __init__(self, a, b, c, d):
        self.A = a
        self.B = b
        self.C = c
        self.D = d

def solve(N, d, cache):
    if N in cache:
        return cache[N]

    if N == 0:
        return 0
    if N == 1:
        return d.D

    ans = d.D * N

    for (n, coeff) in ((2, d.A), (3, d.B), (5, d.C)):
        if N % n == 0:
            ans1 = coeff + solve(N // n, d, cache)
            ans = min(ans, ans1)
        else:
            left = N % n
            ans2 = d.D * left + coeff + solve((N - left) // n, d, cache)

            right = n - left
            ans3 = d.D * right + coeff + solve((N + right) // n, d, cache)

            ans = min(ans, ans2, ans3)

    cache[N] = ans
    return ans
    

def main():
    T = int(input())
    for t in range(T):
        N, A, B, C, D = map(int, input().split())
        d = Data(A, B, C, D)
        cache = {}
        print(solve(N, d, cache))


main()

Submission status: Accepted

Solution code:
from functools import lru_cache
inf = 10**18
T = int(input())
for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    @lru_cache(maxsize=None)
    def solve(N):
        #print(N)
        if N==0:
            return 0
        elif N==1:
            return D
        elif N==2:
            return min(D*2, D+A)
        # elif N==3:
        #     return min(D*3, D+B, D+A+D)
        # elif N==4:
        #     return min(D*4, D+A+A, D+D+A, D+B+D, D+C+D)
        # elif N==5:
        #     return min(D*5, solve(2)+D*3, D+A*3+D*3, solve(3)+D*2, solve(4)+D, D+A+B+D, D+C)
        # elif N==6:
        #     return min(
        #         D*6,
        #         solve(1)+D*5
        #     )
        res = D*N
        for v, cost in zip([2,3,5], [A,B,C]):
            q, m = divmod(N, v)
            if m==0:
                res = min(res, solve(q)+cost)
            else:
                res = min(res, solve(q)+cost+m*D, solve(q+1)+cost+(v-m)*D)
        return res
    print(solve(N))

Submission status: Accepted

Solution code:

t=int(input())
for nt in range(t):
    n,a,b,c,d=[int(k) for k in input().strip().split(" ")]
    r={0:0}
    z=[0,0,a,b,0,c]
    steps=0
    def solve(k):
        #print("solving for",k)
        global r
     #   global steps
        if k in r:
            return r[k]
        else:
            res=k*d
            for i in [2,3,5]:
                if not k%i:
                    res=min(res,z[i]+solve(k//i))
                else:
                    res=min(res,solve(k//i)+z[i]+d*(k%i))
                    if (k//i+1)<k:
                        res=min(res,solve(k//i+1)+z[i]+d*(i-k%i))
     #   print("solved for",k,res)
     #   steps+=1
        r[k]=res
        return res
    print(solve(n))
    #print("steps",steps)

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_ints():
    return map(int, input().split(' '))


t = read_int()
for case_num in range(t):
    n, a, b, c, d = read_ints()

    @lru_cache(None)
    def solve(t):
        if t == 0:
            return 0
        if t == 1:
            return d
        ans = d * t
        if t % 2 == 0:
            ans = min(ans, solve(t // 2) + a)
        else:
            ans = min(ans, solve(t // 2) + a + d, solve(t // 2 + 1) + a + d)

        if t % 3 == 0:
            ans = min(ans, solve(t // 3) + b)
        else:
            rem = t % 3
            ans = min(ans, solve(t // 3) + b + d * rem,
                      solve(t // 3 + 1) + b + (3 - rem) * d)

        if t % 5 == 0:
            ans = min(ans, solve(t // 5) + c)
        else:
            rem = t % 5
            ans = min(ans, solve(t // 5) + c + d * rem,
                      solve(t // 5 + 1) + c + (5 - rem) * d)
        return ans

    print(solve(n))

Submission status: Accepted

Solution code:
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
import sys
sys.setrecursionlimit(10**6)
t=N()
INF=float("inf")
def f(n):
    if n in dp:
        return dp[n]
    r=INF
    for i,j in zip([2,3,5],[a,b,c]):
        x=(n//i)*i
        y=n-x
        r=min(r,f(x//i)+min(j+y*d,(n-x//i)*d))
        x=((n+i-1)//i)*i
        y=x-n
        r=min(r,f(x//i)+min(j+y*d,(n-x//i)*d))
    dp[n]=r
    return r
for i in range(t):
    dp=dict()
    n,a,b,c,d=NM()
    dp[2]=min(d*2,d+a)
    dp[1]=d
    dp[0]=0
    print(f(n))

Submission status: Accepted

Solution code:
import functools
def solve(N, A, B, C, D):
    @functools.lru_cache(None)
    def dp(N):
        if N<=0:
            return float('inf')
        if N == 1:
            return 0
        ans = (N-1)*D
        # BY TWO
        mod_2 = N % 2
        if not mod_2:
            ans = min(ans, dp(N//2)+A)
        else:
            ans =min(ans, dp((N+(2-mod_2))//2)+(A+D*(2-mod_2)))
            ans = min(dp((N-mod_2)//2)+(A+D*mod_2), ans)
        mod_3 = N % 3
        if not mod_3:
            ans = min(ans, dp(N//3)+B)
        else:
            ans =min(ans, dp((N+(3-mod_3))//3)+(B+D*(3-mod_3)))
            ans = min(dp((N-mod_3)//3)+(B+D*mod_3), ans)
        mod_5 = N % 5
        if not mod_5:
            ans = min(ans, dp(N//5)+C)
        else:
            ans =min(ans, dp((N+(5-mod_5))//5)+(C+D*(5-mod_5)))
            ans = min(dp((N-mod_5)//5)+(C+D*mod_5), ans)
        return ans
        
    return dp(N)+D
t = int(input())
for _ in range(t):
    N, A, B, C, D = list(map(int, input().split()))
    print(solve(N, A, B, C, D))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
T = int(input())
for _ in range(T):
    N,A,B,C,D = map(int,input().split())
    INF = float('inf')
    mem = {}
    def solve(n):
        if n==0: return 0
        if n==1: return D
        if n in mem: return mem[n]
        tmp = n*D
        if n%2==0:
            tmp = min(tmp, solve(n//2) + A)
        else:
            tmp = min(tmp, solve(n//2) + A+D, solve(n//2+1) + A+D)
        if n%3==0:
            tmp = min(tmp, solve(n//3) + B)
        else:
            d = n%3
            u = 3-d
            tmp = min(tmp, solve(n//3) + B+d*D, solve(n//3+1) + B+u*D)
        if n%5==0:
            tmp = min(tmp, solve(n//5) + C)
        else:
            d = n%5
            u = 5-d
            tmp = min(tmp, solve(n//5) + C+d*D, solve(n//5+1) + C+u*D)
        mem[n] = tmp
        return tmp
    print(solve(N))

Submission status: Accepted

Solution code:
import sys

divs = [2, 3, 5]

t = int(input())

for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    costs = [a, b, c]

    dp = {}

    def dfs(x):
        if x in dp:
            return dp[x]

        # print(x, file=sys.stderr)

        if x == 0:
            dp[x] = 0
            return dp[x]

        ret = x * d
        for i in range(-4, 5):
            if x - i < 0:
                continue

            nx = x - i
            for cost, div in zip(costs, divs):
                if nx % div != 0 or nx // div >= x:
                    continue

                ret = min(ret, dfs(nx // div) + cost + abs(i) * d)

        dp[x] = ret
        return ret

    print(dfs(n))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

INF = 10**30
def calc(k):
    if k in D:
        return D[k]
    if not k:
        return 0
    res = k*d
    if k != k//2 + 1:
        res = min(res, calc(k//2 + 1) + a + d*(2-k%2))
    if k != k//3 + 1:
        res = min(res, calc(k//3 + 1) + b + d*(3-k%3))
    if k != k//5 + 1:
        res = min(res, calc(k//5 + 1) + c + d*(5-k%5))
    
    if k >= 2:
        res = min(res, calc(k//2) + a + d*(k%2))
    if k >= 3:
        res = min(res, calc(k//3) + b + d*(k%3))
    if k >= 5:
        res = min(res, calc(k//5) + c + d*(k%5))
    D[k] = res
    return res
T = int(readline())
Ans = [None]*T
for qu in range(T):
    n, a, b, c, d = map(int, readline().split())
    D = dict()
    Ans[qu] = calc(n)
print('\n'.join(map(str, Ans)))

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def solve(N, A, B, C, D):
    INF = 10**18

    @lru_cache(None)
    def f(N):
        if N == 0:
            return 0
        if N == 1:
            return D
        ret = D * N
        q, r = divmod(N, 2)
        if r == 0:
            ret = min(ret, f(q) + A)
        else:
            ret = min(ret, f(q) + A + D, f(q + 1) + A + D)
        q, r = divmod(N, 3)
        if r == 0:
            ret = min(ret, f(q) + B)
        elif r == 1:
            ret = min(ret, f(q) + B + D)
        else:
            ret = min(ret, f(q + 1) + B + D)
        q, r = divmod(N, 5)
        if r == 0:
            ret = min(ret, f(q) + C)
        elif r == 1:
            ret = min(ret, f(q) + C + D)
        elif r == 2:
            ret = min(ret, f(q) + C + D + D)
        elif r == 3:
            ret = min(ret, f(q + 1) + C + D + D)
        else:
            ret = min(ret, f(q + 1) + C + D)
        return ret

    return f(N)

T = int(readline())
for _ in range(T):
    n, a, b, c, d = map(int, readline().split())
    print(solve(n, a, b, c, d))

Submission status: Runtime Error

Solution code:
ansl = []
for _ in range(int(input())):
    n,a,b,c,d = map(int, input().split())
    INF = 10**30
    dp = [INF]*(n+1)
    dp[n] = 0

    for i in range(n,1,-1):
        if i%2 == 0: dp[i//2] = min(dp[i//2], dp[i]+a)
        if i%3 == 0: dp[i//3] = min(dp[i//3], dp[i]+b)
        if i%5 == 0: dp[i//5] = min(dp[i//5], dp[i]+c)

        if i >= 1: dp[i-1] == min(dp[i-1], dp[i]+d)
        if i >= 2: dp[i-2] == min(dp[i-2], dp[i]+d*2)
        if i >= 3: dp[i-3] == min(dp[i-3], dp[i]+d*3)
        if i >= 4: dp[i-4] == min(dp[i-4], dp[i]+d*4)
        dp[0] = min(dp[0], dp[i]-i*d)

    ansl.append(dp[0])

for a in ansl: print(a)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

def main(A):
    return 0

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8[:])')(main)
    cc.compile()

if sys.argv[-1] == 'ONLINE_JUDGE':
    cc_export()
    exit(0)
if sys.argv[-1] != 'LOCAL':
    from my_module import main

A = np.ones(10, dtype=np.int32)
ans = main(A)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

def main(A):
    return 0

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8[:])')(main)
    cc.compile()

if sys.argv[-1] == 'ONLINE_JUDGE':
    cc_export()
    exit(0)
if sys.argv[-1] != 'LOCAL':
    from my_module import solve

A = np.ones(10, dtype=np.int32)
ans = main(A)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

if sys.argv[-1] == 'ONLINE_JUDGE':
    cc_export()
    exit(0)
if sys.argv[-1] != 'LOCAL':
    from my_module import solve

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8[:])')(main)
    cc.compile()

def main(A):
    return 0

A = np.ones(10, dtype=np.int32)
ans = main(A)
print(ans)

Submission status: Runtime Error

Solution code:
def main()
  def dfs(x):
    m=x//2
    if m not in dp or dp[m]>dp[x]+abs(2*m-x)*d+a:
      dp[m]=dp[x]+abs(2*m-x)*d+a
      dfs(m)
    m=0--x//2
    if m not in dp or dp[m]>dp[x]+abs(2*m-x)*d+a:
      dp[m]=dp[x]+abs(2*m-x)*d+a
      dfs(m)
    m=x//3
    if m not in dp or dp[m]>dp[x]+abs(3*m-x)*d+b:
      dp[m]=dp[x]+abs(3*m-x)*d+b
      dfs(m)
    m=0--x//3
    if m not in dp or dp[m]>dp[x]+abs(3*m-x)*d+b:
      dp[m]=dp[x]+abs(3*m-x)*d+b
      dfs(m)
    m=x//5
    if m not in dp or dp[m]>dp[x]+abs(5*m-x)*d+c:
      dp[m]=dp[x]+abs(5*m-x)*d+c
      dfs(m)
    m=0--x//5
    if m not in dp or dp[m]>dp[x]+abs(5*m-x)*d+c:
      dp[m]=dp[x]+abs(5*m-x)*d+c
      dfs(m)
  def solve():
    dp[n]=0
    dfs(n)
    return min(dp[i]+abs(i)*d for i in dp)
  for _ in range(int(input())):
    n,a,b,c,d=map(int,input().split())
    dp={}
    print(solve())
if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import math
import heapq

T = int(f.input())
test_cases = [list(map(int,input().split())) for _ in range(T)]


for test_num in range(T):
    hq = []
    kake_patterns = [2,3,5]
    cost_patterns = [test_cases[test_num][1],test_cases[test_num][2],test_cases[test_num][3]]
    plmi_cost = test_cases[test_num][4]
    heapq.heappush(hq,-test_cases[test_num][0])
    memo = defaultdict(int)
    memo[test_cases[test_num][0]] = 0
    memo[0] = plmi_cost*test_cases[test_num][0]
    
    while len(hq)>0:
        checking = heapq.heappop(hq)
        checking = -checking
        cost = memo[checking]
        
        if checking in [0,1]:
            continue
        for i,kake in enumerate(kake_patterns):
            devided1 = math.floor(checking/kake)
            devided2 = math.ceil(checking/kake)
            
            added_cost1 = cost + abs(math.floor(checking/kake)*kake-checking)*plmi_cost + cost_patterns[i]
            added_cost2 = cost + abs(math.ceil(checking/kake)*kake - checking)*plmi_cost + cost_patterns[i]
            
            if devided1 in memo:
                if added_cost1 < memo[devided1]:
                    memo[devided1] = added_cost1
            else:
                memo[devided1] = added_cost1
                heapq.heappush(hq,-devided1)
            
            if devided2 in memo:
                if added_cost2 < memo[devided2]:
                    memo[devided2] = added_cost2
            else:
                memo[devided2] = added_cost2
                heapq.heappush(hq,-devided2)
            
            if added_cost1 + devided1*plmi_cost < memo[0]:
                memo[0] = added_cost1 + devided1*plmi_cost
            if added_cost2 + devided2*plmi_cost < memo[0]:
                memo[0] = added_cost2 + devided2*plmi_cost
            
    print(memo[0])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import math
import heapq

f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")

T = int(f.readline())
test_cases = [list(map(int,f.readline().split())) for _ in range(T)]


for test_num in range(T):
    hq = []
    kake_patterns = [2,3,5]
    cost_patterns = [test_cases[test_num][1],test_cases[test_num][2],test_cases[test_num][3]]
    plmi_cost = test_cases[test_num][4]
    heapq.heappush(hq,-test_cases[test_num][0])
    memo = defaultdict(int)
    memo[test_cases[test_num][0]] = 0
    memo[0] = plmi_cost*test_cases[test_num][0]
    
    while len(hq)>0:
        checking = heapq.heappop(hq)
        checking = -checking
        cost = memo[checking]
        
        if checking in [0,1]:
            continue
        for i,kake in enumerate(kake_patterns):
            devided1 = math.floor(checking/kake)
            devided2 = math.ceil(checking/kake)
            
            added_cost1 = cost + abs(math.floor(checking/kake)*kake-checking)*plmi_cost + cost_patterns[i]
            added_cost2 = cost + abs(math.ceil(checking/kake)*kake - checking)*plmi_cost + cost_patterns[i]
            
            if devided1 in memo:
                if added_cost1 < memo[devided1]:
                    memo[devided1] = added_cost1
            else:
                memo[devided1] = added_cost1
                heapq.heappush(hq,-devided1)
            
            if devided2 in memo:
                if added_cost2 < memo[devided2]:
                    memo[devided2] = added_cost2
            else:
                memo[devided2] = added_cost2
                heapq.heappush(hq,-devided2)
            
            if added_cost1 + devided1*plmi_cost < memo[0]:
                memo[0] = added_cost1 + devided1*plmi_cost
            if added_cost2 + devided2*plmi_cost < memo[0]:
                memo[0] = added_cost2 + devided2*plmi_cost
            
    print(memo[0])