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:
mod = 1000000007
eps = 10 ** -9
inf = 10 ** 40


def main():
    import sys
    from heapq import heappush, heappop
    input = sys.stdin.readline

    for t in range(int(input())):
        N, a, b, c, d = map(int, input().split())
        que = []

        heappush(que, -N)
        seen = {N: 0}
        while que:
            n = -heappop(que)
            if n == 1:
                seen[0] = seen[1] + d
                break
            # 2
            n2_minor = n // 2
            if n % 2 == 0:
                if n2_minor not in seen:
                    seen[n2_minor] = seen[n] + min(a, n2_minor * d)
                    heappush(que, -n2_minor)
                else:
                    seen[n2_minor] = min(seen[n2_minor], seen[n] + min(a, n2_minor * d))
            else:
                if n2_minor not in seen:
                    seen[n2_minor] = seen[n] + min(a, n2_minor * d) + d
                    heappush(que, -n2_minor)
                else:
                    seen[n2_minor] = min(seen[n2_minor], seen[n] + min(a, n2_minor * d) + d)
                n2_major = n2_minor + 1
                if n2_major not in seen:
                    seen[n2_major] = seen[n] + min(a, n2_major * d) + d
                    heappush(que, -n2_major)
                else:
                    seen[n2_major] = min(seen[n2_major], seen[n] + min(a, n2_major * d) + d)

            # 3
            n3_minor = n // 3
            if n % 3 == 0:
                if n3_minor not in seen:
                    seen[n3_minor] = seen[n] + min(b, n3_minor * 2 * d)
                    heappush(que, -n3_minor)
                else:
                    seen[n3_minor] = min(seen[n3_minor], seen[n] + min(b, n3_minor * 2 * d))
            else:
                mod3 = n % 3
                if n3_minor not in seen:
                    seen[n3_minor] = seen[n] + min(b, n3_minor * 2 * d) + d * mod3
                    heappush(que, -n3_minor)
                else:
                    seen[n3_minor] = min(seen[n3_minor], seen[n] + min(b, n3_minor * 2 * d) + d * mod3)
                n3_major = n3_minor + 1
                if n3_major not in seen:
                    seen[n3_major] = seen[n] + min(b, n3_major * 2 * d) + d * (3 - mod3)
                    heappush(que, -n3_major)
                else:
                    seen[n3_major] = min(seen[n3_major], seen[n] + min(b, n3_major * 2 * d) + d * (3 - mod3))

            # 5
            n5_minor = n // 5
            if n % 5 == 0:
                if n5_minor not in seen:
                    seen[n5_minor] = seen[n] + min(c, d * n5_minor * 4)
                    heappush(que, -n5_minor)
                else:
                    seen[n5_minor] = min(seen[n5_minor], seen[n] + min(c, d * n5_minor * 4))
            else:
                mod5 = n % 5
                if n5_minor not in seen:
                    seen[n5_minor] = seen[n] + min(c, d * n5_minor * 4) + d * mod5
                    heappush(que, -n5_minor)
                else:
                    seen[n5_minor] = min(seen[n5_minor], seen[n] + min(c, d * n5_minor * 4) + d * mod5)
                n5_major = n5_minor + 1
                if n5_major not in seen:
                    seen[n5_major] = seen[n] + min(c, d * n5_major * 4) + d * (5 - mod5)
                    heappush(que, -n5_major)
                else:
                    seen[n5_major] = min(seen[n5_major], seen[n] + min(c, d * n5_major * 4) + d * (5 - mod5))
        print(seen[0])
        # if t == 0:
        #    print(seen)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(10**6)


@lru_cache(maxsize=None)
def dp(n):
    if n == 1:
        return D
    cand = []
    if n % 2 == 0:
        cand.append(dp(n // 2) + A)
    if n % 2 == 1:
        cand.append(dp((n-1) // 2) + A + D)
        cand.append(dp((n+1) // 2) + A + D)
    if n % 3 == 0:
        cand.append(dp(n // 3) + B)
    if n % 3 == 1:
        cand.append(dp((n-1) // 3) + B + D)
        cand.append(dp((n+2) // 3) + B + 2 * D)
    if n % 3 == 2:
        cand.append(dp((n+1) // 3) + B + D)
        if n - 2 != 0:
            cand.append(dp((n-2) // 3) + B + 2 * D)
    if n % 5 == 0:
        cand.append(dp(n // 5) + C)
    if n % 5 == 1:
        cand.append(dp((n-1) // 5) + C + D)
        cand.append(dp((n+4) // 5) + C + 4 * D)
    if n % 5 == 2:
        if n - 2 != 0:
            cand.append(dp((n-2) // 5) + C + 2 * D)
        cand.append(dp((n+3) // 5) + C + 3 * D)
    if n % 5 == 3:
        if n - 3 != 0:
            cand.append(dp((n-3) // 5) + C + 3 * D)
        cand.append(dp((n+2) // 5) + C + 2 * D)
    if n % 5 == 4:
        cand.append(dp((n+1) // 5) + C + D)
        if n - 4 != 0:
            cand.append(dp((n-4) // 5) + C + 4 * D)
    cand.append(D * n)
    return min(cand)


T = int(input())
for i in range(T):
    N, A, B, C, D = [int(_) for _ in input().split()]
    dp.cache_clear()
    print(dp(N))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# import bisect
# import heapq
# import math
# import random
# from collections import Counter, defaultdict, deque
# from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache
# from itertools import combinations, combinations_with_replacement, product, permutations
# from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


# @mt
def slv(N, A, B, C, D):
    if N == 1:
        return D

    @lru_cache(maxsize=None)
    def f(n):
        ans = n*D
        for i in range(-5, 6 if n > 10 else 1):
            m = n + i
            i = abs(i)
            if m < 0:
                continue
            if m == 0:
                ans = min(ans, D*i)
                continue

            if m % 5 == 0:
                ans = min(ans, f(m//5) + C + D*i)
                # ans = min(ans, f(m//5) + 4*(m//5)*D + D*i)
            if m % 3 == 0:
                ans = min(ans, f(m//3) + B + D*i)
                # ans = min(ans, f(m//3) + 2*(m//3)*D + D*i)
            if m % 2 == 0:
                ans = min(ans, f(m//2) + A + D*i)
                # ans = min(ans, f(m//2) + (m//2)*D + D*i)
        return ans

    return f(N)


def main():
    T = read_int()
    for _ in range(T):
        N, A, B, C ,D = read_int_n()
        print(slv(N, A, B, C, D))

    # N, A, B, C, D = 29384293847243, 454353412, 332423423, 934923490, 1
    # print(slv(N, A, B, C, D))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def dfs(N, A, B, C, D, memo):
    if (N in memo):
        return memo[N]
    
    if (N == 0):
        return 0
    
    if (N == 1):
        return D
    
    ans = N * D
    if (N % 2 == 0):
        ans = min(ans, dfs(N // 2, A, B, C, D, memo) + A)
    else:
        rem = N % 2
        ans = min(ans, dfs((N - rem) // 2, A, B, C, D, memo) + A + rem * D)
        ans = min(ans, dfs((N + 2 - rem) // 2, A, B, C, D, memo) + A + (2 - rem) * D)
    
    if (N % 3 == 0):
        ans = min(ans, dfs(N // 3, A, B, C, D, memo) + B)
    else:
        rem = N % 3
        ans = min(ans, dfs((N - rem) // 3, A, B, C, D, memo) + B + rem * D)
        ans = min(ans, dfs((N + 3 - rem) // 3, A, B, C, D, memo) + B + (3 - rem) * D)
    
    if (N % 5 == 0):
        ans = min(ans, dfs(N // 5, A, B, C, D, memo) + C)
    else:
        rem = N % 5
        ans = min(ans, dfs((N - rem) // 5, A, B, C, D, memo) + C + rem * D)
        ans = min(ans, dfs((N + 5 - rem) // 5, A, B, C, D, memo) + C + (5 - rem) * D)
    
    memo[N] = ans
    return ans


def solve(N, A, B, C, D):
    memo = dict()
    ans = dfs(N, A, B, C, D, memo)
    print(ans)


T = int(input())
for _ in range(T):
    N, A, B, C, D = list(map(int, input().split()))
    solve(N, A, B, C, D)

Submission status: Accepted

Solution code:
import heapq

ans = []

T = int(input())
for i in range(T):
    N,A,B,C,D = map(int,input().split())
    Q = {}
    queue = []
    for i in range(N,N+1):
        Q[i] = abs(i-N)*D
        heapq.heappush(queue,-i)
    while 1:
        q = -heapq.heappop(queue)
        if q == 0:
            break
        a = q//2
        b = q//3
        c = q//5
        a_V = min(Q[q]+A+D*(q%2),Q[q]+(q-a)*D)
        b_V = min(Q[q]+B+D*(q%3),Q[q]+(q-b)*D)
        c_V = min(Q[q]+C+D*(q%5),Q[q]+(q-c)*D)
        a_2 = (q+1)//2
        b_2 = (q+2)//3
        c_2 = (q+4)//5
        a_V_2 = min(Q[q]+(a_2*2-q)*D+A,Q[q]+abs(q-a_2)*D)
        b_V_2 = min(Q[q]+(b_2*3-q)*D+B,Q[q]+abs(q-b_2)*D)
        c_V_2 = min(Q[q]+(c_2*5-q)*D+C,Q[q]+abs(q-c_2)*D)
        
        if a in Q:
            if Q[a] > a_V:
                Q[a] = a_V
        else:
            heapq.heappush(queue,-a)
            Q[a] = a_V
        
        if b in Q:
            if Q[b] > b_V:
                Q[b] = b_V
        else:
            heapq.heappush(queue,-b)
            Q[b] = b_V        
        
        if c in Q:
            if Q[c] > c_V:
                Q[c] = c_V
        else:
            heapq.heappush(queue,-c)
            Q[c] = c_V

        if a_2 in Q:
            if Q[a_2] > a_V_2:
                Q[a_2] = a_V_2
        else:
            heapq.heappush(queue,-a_2)
            Q[a_2] = a_V_2
        
        if b_2 in Q:
            if Q[b_2] > b_V_2:
                Q[b_2] = b_V_2
        else:
            heapq.heappush(queue,-b_2)
            Q[b_2] = b_V_2
        
        if c_2 in Q:
            if Q[c_2] > c_V_2:
                Q[c_2] = c_V_2
        else:
            heapq.heappush(queue,-c_2)
            Q[c_2] = c_V_2

        
        #print(q,Q,c_2,c_V_2)
    #print(Q[0])
    ans.append(Q[0])
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import defaultdict

def small(N, A, B, C, D):
    if N == 1:
        return D
    elif N == 2:
        return min(2*D, D+A)
    elif N == 3:
        return min(3*D, D+B, 2*D+A)
    else:
        assert False

def solve(N, A, B, C, D):
    if N <= 3:
        return small(N, A, B, C, D)
    visited = set()
    #visited.add(N)
    dist = {}
    dist[N] = 0
    q = []
    heappush(q, (0, N))
    def update(d2, d, cost):
        nonlocal q
        nonlocal dist
        if not d2 in dist or dist[d2] > dist[d] + cost:
            dist[d2] = dist[d] + cost
            heappush(q, (dist[d2], d2))
            # if d2 == 0:
            #     print(f'{d}->{d2}, cost={cost}')
    while len(q) > 0:
        _prov_cost, d = heappop(q)
        if d in visited:
            continue
        else:
            visited.add(d)
        #dから行けるところ->2,3,5で割れるようにする方法
        mod2 = d % 2
        mod3 = d % 3
        mod5 = d % 5
        if mod2 == 0:
            update(d//2, d, A)
        if mod3 == 0:
            update(d//3, d, B)
        if mod5 == 0:
            update(d//5, d, C)
        #if mod2 * mod3 * mod5 != 0:  #2でも3でも5でも割れない場合、2か3か5で割りに行く
            
        #奇数なので、上下を足す。11->10->5->6より11->12->6のほうが安い
        #ただし、割りに行く値よりD重ねたほうがいい場合もある
        #11->10->5はD+Aと(11-5)*Dとコストが安い方
        update((d-1)//2, d, min(D+A, (d - (d-1)//2)*D))
        #11->12->6はD+Aと(12-5)*Dとコストが安い方
        update((d+1)//2, d, min(D+A, (d - (d+1)//2)*D))
        #3で割りに行く
        _d2 = (d-mod3)//3
        update(_d2, d, min(mod3*D+B, (d-_d2)*D))
        _d2 = (d+(3-mod3))//3
        update(_d2, d, min((3-mod3)*D+B, (d-_d2)*D))
        #5で割りに行く
        _d2 = (d-mod5)//5
        update(_d2, d, min(mod5*D+C, (d-_d2)*D))
        _d2 = (d+(5-mod5))//5
        update(_d2, d, min((5-mod5)*D+C, (d-_d2)*D))
        '''
        if d % 5 == 1:
            update((d-1)//3, D+C)
            update((d+4)//5, 4*D+C)
        elif d % 5 == 2:
            update((d-2)//3, 2*D+C)
            update((d+3)//5, 3*D+C)
        '''

        #print('q:', q)
        #print('q for nonvisited:', [x for x in q if not x[1] in visited])
        #print('dist:', dist)
    #print(dist)
    return dist[0]
            #heappush(q, (D, d+1))
            #heappush(q, (D, d-1))

    

    

def main():
    T = int(input())
    for _ in range(T):
        N, A, B, C, D = tuple(int(c) for c in input().split(' '))
        print(solve(N, A, B, C, D))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    pq = [(0, N)]
    used = set()
    while pq:
        c, x = heappop(pq)
        if x in used:
            continue
        used.add(x)
        if x == 1:
            print(c + D)
            break
        heappush(pq, (c + D * (x - 1), 1))
        if x % 2 == 0:
            heappush(pq, (c + A, x // 2))
        else:
            heappush(pq, (c + D + A, (x - 1) // 2))
            heappush(pq, (c + D + A, (x + 1) // 2))
        if x >= 3:
            if x % 3 == 0:
                heappush(pq, (c + B, x // 3))
            else:
                heappush(pq, (c + D * (x % 3) + B, x // 3))
                heappush(pq, (c + D * (3 - x % 3) + B, x // 3 + 1))
        if x >= 5:
            if x % 5 == 0:
                heappush(pq, (c + C, x // 5))
            else:
                heappush(pq, (c + D * (x % 5) + C, x // 5))
                heappush(pq, (c + D * (5 - x % 5) + C, x // 5 + 1))
        else:
            heappush(pq, (c + D * (5 - x) + C, 1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n, b, c, d, a = nm()
    g = dict()
    def calc(x):
        if x < 2:
            return a * x
        if x in g:
            return g[x]
        y1 = x // 5
        ret1 = min(a * (x % 5) + d, a * (x - y1)) + calc(y1)
        y2 = (x - 1)//5 + 1
        ret2 = min(a * (y2 * 5 - x) + d, a * (x - y2)) + calc(y2)
        y3 = x // 3
        ret3 = min(a * (x % 3) + c, a * (x - y3)) + calc(y3)
        y4 = (x - 1)//3 + 1
        ret4 = min(a * (y4 * 3 - x) + c, a * (x - y4)) + calc(y4)
        y5 = x // 2
        ret5 = min(a * (x % 2) + b, a * (x - y5)) + calc(y5)
        y6 = (x - 1)//2 + 1
        ret6 = min(a * (y6 * 2 - x) + b, a * (x - y6)) + calc(y6)
        g[x] = min([ret1, ret2, ret3, ret4, ret5, ret6])
        return g[x]
    print(calc(n))
    return

T = ni()
for _ in range(T):
    solve()

Submission status: Accepted

Solution code:
memo = {}

bases = [2, 3, 5]
baseCost = [-1, -1, -1]
d = -1

def getAns(x):
    if x == 0:
        return 0
    if x in memo:
        return memo[x]
    memo[x] = -1
    ans = x * d
    for k in range(3):
        for delta in range(-bases[k] + 1, bases[k]):
            afterMul = x + delta
            if afterMul >= 0 and afterMul % bases[k] == 0:
                if afterMul // bases[k] in memo and memo[afterMul // bases[k]] == -1:
                    continue
                ans = min(ans, getAns(afterMul // bases[k]) + abs(delta) * d + baseCost[k])
    memo[x] = ans
    return ans

t = int(input())
for i in range(t):
    memo = {}
    n, a, b, c, dx = map(int, input().split())
    baseCost = [a, b, c]
    d = dx
    print(getAns(n))

Submission status: Accepted

Solution code:

from collections import defaultdict
T = int(input())


def dfs(n, b):

    if dp[n] != 0:
        return dp[n]

    if n == 1:
        return D
    elif n == 0:
        return 0

    ans = 10**30

    # ..2
    if n % 2 != 0:
        t = n // 2 * 2 + 2
        tmp = dfs(t // 2, n) + min(A, t // 2 * 2 * D) + D * abs(n - t)
        ans = min(ans, tmp)
        t = n // 2 * 2 + 0
        tmp = dfs(t // 2, n) + min(A, t // 2 * 2 * D) + D * abs(n - t)
        ans = min(ans, tmp)
    elif n % 2 == 0:
        t = n
        tmp = dfs(t // 2, n) + min(A, t // 2 * D)
        ans = min(ans, tmp)

    # ..3
    if n % 3 != 0:
        t = n // 3 * 3 + 3
        tmp = dfs(t // 3, n) + min(B, t // 3 * 2 * D) + D * abs(n - t)
        ans = min(ans, tmp)
        t = n // 3 * 3 + 0
        tmp = dfs(t // 3, n) + min(B, t // 3 * 2 * D) + D * abs(n - t)
        ans = min(ans, tmp)
    else:
        t = n
        tmp = dfs(t // 3, n) + min(B, t // 3 * 2 * D) + D * abs(n - t)
        ans = min(ans, tmp)

    # ..5
    if n % 5 != 0:
        t = n // 5 * 5 + 5
        tmp = dfs(t // 5, n) + min(C, t // 5 * 4 * D) + D * abs(n - t)
        ans = min(ans, tmp)

        t = n // 5 * 5 + 0
        tmp = dfs(t // 5, n) + min(C, t // 5 * 4 * D) + D * abs(n - t)
        ans = min(ans, tmp)
    else:
        t = n
        tmp = dfs(t // 5, n) + min(C, t // 5 * 4 * D) + D * abs(n - t)
        ans = min(ans, tmp)

    dp[n] = ans

    return ans


for _ in range(T):
    N, A, B, C, D = list(map(int, input().split()))

    dp = defaultdict(int)
    print(dfs(N, -1))

Submission status: Accepted

Solution code:
from collections import defaultdict as dd, deque

t = int(input())

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

    todo = [(n, 0)]

    best = 10**100
    cheap = dd(lambda: 10**100)
    while todo:
        #print(todo)
        x,cost = todo.pop()
        if x < 0 or cost >= best:
            continue
        if x == 0:
            best = min(best, cost)
            continue
        if x in cheap and cheap[x] <= cost:
            continue
        cheap[x] = cost

        todo.append((0, cost + x*d))
        for i in range(x-1, x+2):
            if i%2 == 0:
                dist = abs(i - x)
                todo.append((i//2, cost + dist*d + a))
        for i in range(x-2, x+3):
            if i%3 == 0:
                dist = abs(i - x)
                todo.append((i//3, cost + dist*d + b))
        for i in range(x-4, x+5):
            if i%5 == 0:
                dist = abs(i - x)
                todo.append((i//5, cost + dist*d + c))
    print(best)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


def solve(n, a, b, c, d):
    q = [(0, n)]
    checked = set()
    ans = n * d + 1
    while q:
        cost, x = heappop(q)
        if cost >= ans:
            break
        if x in checked:
            continue
        checked.add(x)
        ans = min(ans, cost + d * x)
        if x == 0:
            continue

        div, mod = divmod(x, 2)
        if mod == 0:
            if div not in checked:
                heappush(q, (cost + a, div))
        else:
            if div not in checked:
                heappush(q, (cost + a + d, div))
            if div + 1 not in checked:
                heappush(q, (cost + a + d, div + 1))

        div, mod = divmod(x, 3)
        if mod == 0:
            if div not in checked:
                heappush(q, (cost + b, div))
        else:
            if div not in checked:
                heappush(q, (cost + b + mod * d, div))
            if div + 1 not in checked:
                heappush(q, (cost + b + (3 - mod) * d, div + 1))

        div, mod = divmod(x, 5)
        if mod == 0:
            if div not in checked:
                heappush(q, (cost + c, div))
        else:
            if div not in checked:
                heappush(q, (cost + c + mod * d, div))
            if div + 1 not in checked:
                heappush(q, (cost + c + (5 - mod) * d, div + 1))

    return ans


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from collections import deque
from collections import defaultdict
import heapq
INF = float("inf")


def main():
    T = int(input())
    for _ in range(T):
        N, A, B, C, D = map(int, input().split())
        d = defaultdict(lambda: INF)
        stack = [(0, N)]
        d[N] = 0
        while len(stack) > 0:
            c, n = heapq.heappop(stack)
            if c > d[1]:
                break
            # print(c, n)
            cost = [A, B, C]
            for i, p in enumerate((2, 3, 5)):
                # A,B,Cのアクションを行う場合
                if n % p == 0 and d[n//p] > c+cost[i]:
                    d[n//p] = c+cost[i]
                    heapq.heappush(stack, (c+cost[i], n//p))

                # Dの扱い
                # A,B,Cのアクションの代わりとして行う場合
                if cost[i] > (n-n//p)*D and d[n//p] > c+(n-n//p)*D:
                    d[n//p] = c+(n-n//p)*D
                    heapq.heappush(stack, (c+(n-n//p)*D, n//p))

                # Dの扱い
                # A、B,Cのアクションと連携して行う場合
                if n % p != 0:
                    m = n % p
                    # m回Dを行って、pを行う
                    if d[(n-m)//p] > c+cost[i]+m*D:
                        d[(n-m)//p] = c+cost[i]+m*D
                        heapq.heappush(stack, (c+cost[i]+m*D, (n-m)//p))
                    # p-m回Dを行って、pを行う
                    m = p - m
                    if d[(n+m)//p] > c+cost[i]+m*D:
                        d[(n+m)//p] = c+cost[i]+m*D
                        heapq.heappush(stack, (c+cost[i]+m*D, (n+m)//p))

            #         # if n % 2 == 0:
            #         #     if A > (n//2)*D:
            #         #         if d[n//2] > c+(n//2)*D:
            #         #             d[n//2] = c+(n//2)*D
            #         #             heapq.heappush(stack, (c+(n//2)*D, n//2))
            #         #     else:
            #         #         if d[n//2] > c+A:
            #         #             d[n//2] = c+A
            #         #             heapq.heappush(stack, (c+A, n//2))
            #         # if n % 3 == 0:
            #         #     if B > (n-n//3)*D:
            #         #         if d[n//3] > c+(n-n//3)*D:
            #         #             d[n//3] = c+(n-n//3)*D
            #         #             heapq.heappush(stack, (c+(n-n//3)*D, n//3))
            #         #     else:
            #         #         if d[n//3] > c+B:
            #         #             d[n//3] = c+B
            #         #             heapq.heappush(stack, (c+B, n//3))
            #         # if n % 5 == 0:
            #         #     if C > (n-n//5)*D:
            #         #         if d[n//5] > c+(n-n//5)*D:
            #         #             d[n//5] = c+(n-n//5)*D
            #         #             heapq.heappush(stack, (c+(n-n//5)*D, n//5))
            #         #     if d[n//5] > c+C:
            #         #         d[n//5] = c+C
            #         #         heapq.heappush(stack, (c+C, n//5))
            # if n % 2 == 1:
            #     if d[(n-1)//2] > c+A+D:
            #         d[(n-1)//2] = c+A+D
            #         heapq.heappush(stack, (c+A+D, (n-1)//2))
            #     if d[(n+1)//2] > c+D+A:
            #         d[(n+1)//2] = c+D+A
            #         heapq.heappush(stack, (c+D+A, (n+1)//2))
            # if n % 3 != 0:
            #     m = n % 3
            #     if d[(n-m)//3] > c+B+m*D:
            #         d[(n-m)//3] = c+B+m*D
            #         heapq.heappush(stack, (c+B+m*D, (n-m)//3))
            #     if d[(n-m+3)//3] > c+B+(3-m)*D:
            #         d[(n-m+3)//3] = c+B+(3-m)*D
            #         heapq.heappush(stack, (c+B+(3-m)*D, (n-m+3)//3))
            # if n % 5 != 0:
            #     m = n % 5
            #     if d[(n-m)//5] > c+C+m*D:
            #         d[(n-m)//5] = c+C+m*D
            #         heapq.heappush(stack, (c+C+m*D, (n-m)//5))
            #     if d[(n-m+5)//5] > c+C+(5-m)*D:
            #         d[(n-m+5)//5] = c+C+(5-m)*D
            #         heapq.heappush(stack, (c+C+(5-m)*D, (n-m+5)//5))

        print(d[1]+D)
        # return

        # 一番効率の良いアプローチで攻める貪欲ではどうか→組み合わせ次第
        # 作戦
        # Nが小さければDPができる。→あるiに到達するために必要なコインの最小数
        # 10**3程度までは貪欲で近づいて良さそうなイメージがある。そこから貪欲とする
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

t = int(input())

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

    di = {0:0, 1:d}
    def _f(_n):
        if _n in di:
            return di[_n]
        nn = _n * d
        n5 = (_n % 5) * d + c + _f(_n // 5)
        if _n % 5 != 0:
            n5 = min(n5, (-_n % 5) * d + c + _f((_n // 5) + 1))
        n3 = (_n % 3) * d + b + _f(_n // 3)
        if _n % 3 != 0:
            n3 = min(n3, (-_n % 3) * d + b + _f((_n // 3) + 1))
        n2 = (_n % 2) * d + a + _f(_n // 2)
        if _n % 2 != 0:
            n2 = min(n2, (_n % 2) * d + a + _f((_n // 2) + 1))

        ret = min(nn, n2, n3, n5)
        di[_n] = ret
        return ret


    print(_f(n))

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

def a(N,A,B,C,D):
    E = defaultdict(lambda:N*D)
    arr = [(2,A),(3,B),(5,C)]
    # Nから0までのコストを計算する
    # ヒープは最小の要素が先頭に来る
    # D[0]を超えたら打ち切る
    aa = 0
    bb = 0
    num = 0
    H = [N]
    E[N] = 0
    while len(H) != 0:
        num = heapq.heappop(H)
        if E[num] >= E[0]:
            continue
        E[0] = min(E[0],E[num] + D * num)
        for k,v in arr:
            aa = num // k
            bb = E[num] + D * (num - aa * k) + v
            if E[aa] > bb:
                E[aa] = bb
                heapq.heappush(H,aa)
            aa += 1
            bb = E[num] + D * (aa * k - num) + v
            if E[aa] > bb:
                E[aa] = bb
                heapq.heappush(H,aa)
    print(E[0])

T = int(input())
A = [0]*T
for i in range(T):
    A[i] = tuple(map(int,input().split()))
    
for i in range(T):
    a(*A[i])