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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
from collections import *

def f(n):
    if memo[n]!=-1:
        return memo[n]
    
    if n==0:
        memo[n] = 0
        return 0
        
    if n==1:
        memo[n] = D
        return D
        
    res = n*D
    
    for p, c in [(2, A), (3, B), (5, C)]:
        up = (n+p-1)//p*p
        down = n//p*p
        res = min(res, (up-n)*D+f(up//p)+c, (n-down)*D+f(down//p)+c)
    
    memo[n] = res
    return res

T = int(input())

for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    memo = defaultdict(lambda: -1)
    print(f(N))

Solution (Python):
T=int(input())
for i in range(T):
    N,A,B,C,D=map(int,input().split())

    M={0:0,1:D}

    def f(N):
        if N in M:
            return M[N]
        
        p,q=N//2*2,(N+1)//2*2
        r,s=N//3*3,(N+2)//3*3
        t,u=N//5*5,(N+4)//5*5
        R=min(D*N,
              D*abs(N-p)+A+f(p//2),
              D*abs(N-q)+A+f(q//2),
              
              D*abs(N-r)+B+f(r//3),
              D*abs(N-s)+B+f(s//3),
              
              D*abs(N-t)+C+f(t//5),
              D*abs(N-u)+C+f(u//5),
              )

        M[N]=R
        return R
    
    print(f(N))

Solution (Python):

from collections import defaultdict


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]

    ret = []
    for n, a, b, c, d in NABCD:
        ABC = ((2, a), (3, b), (5, c))
        dp = defaultdict(lambda: n*d)
        stack = [(n, 0)]
        while stack:
            rem, cost = stack.pop()
            if min(dp[0], dp[rem]) <= cost:
                continue

            dp[rem] = cost
            dp[0] = min(dp[0], cost+rem*d)

            if 0 < rem:
                for x, y in ABC:
                    div, m = divmod(rem, x)
                    if div:
                        stack.append((div, d*m+cost+y))
                    if m:
                        stack.append((div+1, d*(x-m)+cost+y))

        ret.append(str(dp[0]))

    return '\n'.join(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):

from collections import defaultdict


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]

    ret = []
    for n, a, b, c, d in NABCD:
        ABC = ((2, a), (3, b), (5, c))
        dp = defaultdict(lambda: n*d)
        stack = [(n, 0)]
        while stack:
            rem, cost = stack.pop()
            if min(dp[0], dp[rem]) <= cost:
                continue

            dp[rem] = cost
            dp[0] = min(dp[0], cost+rem*d)

            if 0 < rem:
                for x, y in ABC:
                    l, h = rem//x, -(-rem//x)
                    stack.append((l, d*abs(l*x-rem)+cost+y*(0 < l)))
                    stack.append((h, d*abs(h*x-rem)+cost+y))

        ret.append(str(dp[0]))

    return '\n'.join(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
def resolve():
    for _ in range(int(input())):
        n, a, b, c, d = map(int, input().split())

        @lru_cache(None)
        def dfs(k):
            
            if k == 0:
                return 0
            if k == 1:
                return d
            
            res = k * d
            for p, cost in zip([2, 3, 5], [a, b, c]):
                q, r = divmod(k, p)
                if r == 0:
                    res = min(res, dfs(q) + cost)
                else:
                    res = min(res, dfs(q) + cost + d * r, dfs(q + 1) + cost + d * (p - r))
            return res

        print(dfs(n))
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
from functools import lru_cache

@lru_cache(maxsize=None)
def solve(n, a, b, c, d):
    if n == 0:
        return 0
    if n == 1:
        return d
    res = 10**18
    res = min(res, d * n)
    res = min(res, d * (n - n // 2 * 2) + a + solve(n // 2, a, b, c, d))
    res = min(res, d * (n - n // 3 * 3) + b + solve(n // 3, a, b, c, d))
    res = min(res, d * (n - n // 5 * 5) + c + solve(n // 5, a, b, c, d))
    res = min(res, d * ((n + 2 - 1) // 2 * 2 - n) + a + solve((n + 2 - 1) // 2, a, b, c, d))
    res = min(res, d * ((n + 3 - 1) // 3 * 3 - n) + b + solve((n + 3 - 1) // 3, a, b, c, d))
    res = min(res, d * ((n + 5 - 1) // 5 * 5 - n) + c + solve((n + 5 - 1) // 5, a, b, c, d))
    return res

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

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

for i in range(t):
    n,a,b,c,d=nabcd[i]
    lst=[-n]
    coin=defaultdict(lambda: float('inf'))
    coin[n]=0
    dic={}
    while lst:
        now=-heapq.heappop(lst)
        
        
        if now==1:
            coin[0]=min(coin[0],coin[now]+d)
            break

        if now in dic:
            continue
        else:
            dic[now]=1
    
        if now%2==0:
            heapq.heappush(lst,-now//2)
            coin[now//2]=min(coin[now//2],coin[now]+min(a,now//2*d))
        else:
            heapq.heappush(lst,-(now+1)//2)
            coin[(now+1)//2]=min(coin[(now+1)//2],coin[now]+min(a+d,(now-(now+1)//2)*d))
            if (now-1)//2>0:
                heapq.heappush(lst,-(now-1)//2)
                coin[(now-1)//2]=min(coin[(now-1)//2],coin[now]+min(a+d,(now-(now-1)//2)*d))

        for j in range(3):
            if (now+j)%3==0:
                if j==0:
                    heapq.heappush(lst,-(now+j)//3)
                    coin[(now+j)//3]=min(coin[(now+j)//3],coin[now]+min(b+j*d,(now-(now+j)//3)*d))
                    
                else:
                    heapq.heappush(lst,-(now+j)//3)
                    coin[(now+j)//3]=min(coin[(now+j)//3],coin[now]+min(b+j*d,(now-(now+j)//3)*d))
                    if (now+j-3)//3>0:
                        heapq.heappush(lst,-(now+j-3)//3)
                        coin[(now+j-3)//3]=min(coin[(now+j-3)//3],coin[now]+min(b+(3-j)*d,(now-(now+j-3)//3)*d))
        
        for j in range(5):
            if (now+j)%5==0:
                if j==0:
                    heapq.heappush(lst,-(now+j)//5)
                    coin[(now+j)//5]=min(coin[(now+j)//5],coin[now]+min(c+j*d,(now-(now+j)//5)*d))
                else:
                    heapq.heappush(lst,-(now+j)//5)
                    coin[(now+j)//5]=min(coin[(now+j)//5],coin[now]+min(c+j*d,(now-(now+j)//5)*d))
                    if (now+j-5)//5>0:
                        heapq.heappush(lst,-(now+j-5)//5)
                        coin[(now+j-5)//5]=min(coin[(now+j-5)//5],coin[now]+min(c+(5-j)*d,(now-(now+j-5)//5)*d))
        
    print(coin[0])

Solution (Python):





def calc_cost(n, ans_dict):

    min_cost = n * d

    inc_2 = (n + 2 - 1) // 2
    if inc_2 not in ans_dict:
        ans_dict[inc_2] = calc_cost(inc_2, ans_dict)
    min_cost = min(min_cost, d * (inc_2 * 2 - n) + a + ans_dict[inc_2])

    dec_2 = n // 2
    if dec_2 not in ans_dict:
        ans_dict[dec_2] = calc_cost(dec_2, ans_dict)
    min_cost = min(min_cost, d * (- dec_2 * 2 + n) + a + ans_dict[dec_2])

    inc_3 = (n + 3 - 1) // 3
    if inc_3 not in ans_dict:
        ans_dict[inc_3] = calc_cost(inc_3, ans_dict)
    min_cost = min(min_cost, d * (inc_3 * 3 - n) + b + ans_dict[inc_3])

    dec_3 = n // 3
    if dec_3 not in ans_dict:
        ans_dict[dec_3] = calc_cost(dec_3, ans_dict)
    min_cost = min(min_cost, d * (- dec_3 * 3 + n) + b + ans_dict[dec_3])

    inc_5 = (n + 5 - 1) // 5
    if inc_5 not in ans_dict:
        ans_dict[inc_5] = calc_cost(inc_5, ans_dict)
    min_cost = min(min_cost, d * (inc_5 * 5 - n) + c + ans_dict[inc_5])

    dec_5 = n // 5
    if dec_5 not in ans_dict:
        ans_dict[dec_5] = calc_cost(dec_5, ans_dict)
    min_cost = min(min_cost, d * (- dec_5 * 5 + n) + c + ans_dict[dec_5])

    ans_dict[n] = min_cost
    return min_cost

n_testcase = int(input())
for i in range(n_testcase):
    n, a, b, c, d = list(map(int, input().split()))

    
    ans_dict = {}

    ans_dict[0] = 0
    ans_dict[1] = d  

    ans = calc_cost(n, ans_dict)
    print(ans)

Solution (Python):
from collections import defaultdict
import heapq
T=int(input())
for testcase in range(T):
    N,A,B,C,D=map(int,input().split())
    dist=defaultdict(lambda:10**23)
    dist[N]=0
    q=[]
    heapq.heappush(q,(0,N,0))
    while(len(q)!=0):
        nowdist,num,onestreak=heapq.heappop(q)
        if dist[num]<nowdist:
            continue
        if dist[0]>dist[num]+num*D:
            dist[0]=dist[num]+num*D
            heapq.heappush(q,(dist[0],0,num*D))
        if num%2==0 and (dist[num//2]>dist[num]+A):
            dist[num//2]=dist[num]+A
            heapq.heappush(q,(dist[num//2],num//2,0))
        if num%3==0 and (dist[num//3]>dist[num]+B):
            dist[num//3]=dist[num]+B
            heapq.heappush(q,(dist[num//3],num//3,0))
        if num%5==0 and (dist[num//5]>dist[num]+C):
            dist[num//5]=dist[num]+C
            heapq.heappush(q,(dist[num//5],num//5,0))
        if onestreak<5 and (dist[num+1]>dist[num]+D):
            dist[num+1]=dist[num]+D
            heapq.heappush(q,(dist[num+1],num+1,onestreak+1))
        if onestreak<5 and num>=1 and (dist[num-1]>dist[num]+D):
            dist[num-1]=dist[num]+D
            heapq.heappush(q,(dist[num-1],num-1,onestreak+1))
    print(dist[0])

Solution (Python):

import sys
from heapq import heappop, heappush

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline

INF = 10 ** 27 + 1



def dp(*x):  
    print(*x)


def solve(N, A, B, C, D):
    "void()"

    MIN_COST = min(A, B, C, D)

    to_visit = [-N]
    cost = {N: 0}

    answer = 1e+99

    def put(n, c):
        
        cost[n] = min(cost.get(n, INF), c)
        heappush(to_visit, -n)

    visited = N + 1
    while to_visit:
        n = -heappop(to_visit)
        if n == visited:
            continue
        

        visited = n
        c = cost[n]
        put(0, c + n * D)

        if n % 2 == 0:
            put(n // 2, c + A)
        else:
            put((n+1) // 2, c + A + D)
            put((n-1) // 2, c + A + D)

        if n % 3 == 0:
            put(n // 3, c + B)
        elif n % 3 == 1:
            put((n-1) // 3, c + B + D)
            put((n+2) // 3, c + B + D * 2)
        else:
            put((n+1) // 3, c + B + D)
            put((n-2) // 3, c + B + D * 2)

        if n % 5 == 0:
            put(n // 5, c + C)
        elif n % 5 == 1:
            put((n-1) // 5, c + C + D)
            put((n+4) // 5, c + C + D * 4)
        elif n % 5 == 2:
            put((n-2) // 5, c + C + D * 2)
            put((n+3) // 5, c + C + D * 3)
        elif n % 5 == 3:
            put((n+2) // 5, c + C + D * 2)
            put((n-3) // 5, c + C + D * 3)
        elif n % 5 == 4:
            put((n+1) // 5, c + C + D)
            put((n-4) // 5, c + C + D * 4)

    return cost[0]


def main():
    """
    >>> solve(4, 1000000000, 1000000000, 1000000000, 1)
    4
    >>> solve(4, 1, 1000000000, 1000000000, 1)
    3
    >>> solve(8, 1, 1000000000, 1000000000, 1)
    4
    """
    T = int(input())
    for t in range(T):
        print(solve(*[int(x) for x in input().split()]))


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())
    input = f.readline
    read = f.read


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):
import heapq

T = int(input())

for i in range(T):
    N,A,B,C,D=map(int,input().split())
    Q=[]
    Q.append((0,N))
    Dict={}
    heapq.heapify(Q)
    while 1 not in Dict:
        q0,q1=heapq.heappop(Q)
        if q1 not in Dict:
            Dict[q1]=q0
            if q1%2==0:
                heapq.heappush(Q,(q0+min(A,D*(q1//2)),q1//2))
            else:
                heapq.heappush(Q,(q0+min(D+A,D*(q1+1)//2),q1//2))
                heapq.heappush(Q,(q0+min(D+A,D*(q1+1)//2),q1//2+1))
            if q1%3==0:
                heapq.heappush(Q,(q0+min(B,D*(q1//3)*2),q1//3))
            else:
                M=q1%3
                m=3-M
                heapq.heappush(Q,(q0+min(M*D+B,(q1-q1//3)*D),q1//3))
                heapq.heappush(Q,(q0+min(m*D+B,(q1-(q1+3)//3)*D),(q1+3)//3))
            if q1%5==0:
                heapq.heappush(Q,(q0+min(C,D*(q1//5)*4),q1//5))
            else:
                M=q1%5
                m=5-M
                heapq.heappush(Q,(q0+min(M*D+C,(q1-q1//5)*D),q1//5))
                heapq.heappush(Q,(q0+min(m*D+C,(q1-(q1+5)//5)*D),(q1+5)//5))
    print(Dict[1]+D)

Solution (Python):
import math
t = int(input())
C = [list(map(int, input().split())) for i in range(t)]
di = [2, 3, 5]

nmax = 10**18

def a1(x, co):
    global D
    
    if x in D:
        
        return D[x]
    else:
        ans = float("inf")
        for j in range(3):
            ans = min(ans, a1(x//di[j], co) + d*(x%di[j]) + co[j])
            if x > x//di[j] + 1:
                ans = min(ans, a1(x//di[j] + 1, co) + d*(di[j] - (x%di[j])) + co[j])
        ans = min(ans, d*x)
        D[x] = ans
        
        return ans

for ii in range(t):
    n,a,b,c,d = C[ii]
    co = [a,b,c]
    D = {0:0, 1:d}
    print(a1(n, co))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def main(N, c2, c3, c5, c):
    m = dict()
    m[0] = 0
    m[1] = c

    def f(n):
        if n in m: return m[n]
        res = c * n
        e5 = n % 5
        e3 = n % 3
        e2 = n % 2
        if e5 != 0:
            res = min(res, (5 - e5) * c + f(n // 5 + 1) + c5)
        if e3 != 0:
            res = min(res, (3 - e3) * c + f(n // 3 + 1) + c3)
        if e2 != 0:
            res = min(res, (2 - e2) * c + f(n // 2 + 1) + c2)
        if n >= 5:
            res = min(res, e5 * c + f(n // 5) + c5)
        if n >= 3:
            res = min(res, e3 * c + f(n // 3) + c3)
        if n >= 2:
            res = min(res, e2 * c + f(n // 2) + c2)
        m[n] = res
        return res

    return f(N)

if __name__ == '__main__':
    input = sys.stdin.readline
    T = int(input())
    for t in range(T):
        n, a, b, c, d = map(int, input().split())
        ans = main(n, a, b, c, d)
        print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def main(N, c2, c3, c5, c):
    m = dict()
    m[0] = 0
    m[1] = c

    def f(n):
        if n in m: return m[n]
        res = c * n
        e5 = n % 5
        e3 = n % 3
        e2 = n % 2
        if e5 != 0:
            res = min(res, (5 - e5) * c + f(n // 5 + 1) + c5)
        if e3 != 0:
            res = min(res, (3 - e3) * c + f(n // 3 + 1) + c3)
        if e2 != 0:
            res = min(res, (2 - e2) * c + f(n // 2 + 1) + c2)
        if n >= 5:
            res = min(res, e5 * c + f(n // 5) + c5)
        if n >= 3:
            res = min(res, e3 * c + f(n // 3) + c3)
        if n >= 2:
            res = min(res, e2 * c + f(n // 2) + c2)
        m[n] = res
        return res

    return f(N)

if __name__ == '__main__':
    input = sys.stdin.readline
    T = int(input())
    for t in range(T):
        n, a, b, c, d = map(int, input().split())
        ans = main(n, a, b, c, d)
        print(ans)

Solution (Python):
import sys

readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from heapq import heappop, heappush

t = readint()

ans = []

for _ in range(t):
    n,a,b,c,d = readints()
    x = [0,0,a,b,0,c]
    h = [(0,n)]
    dct = dict()
    while 1:
        cost,num = heappop(h)
        if num == 1:
            break
        for i in (2,3,5):
            new_cost = cost + min(x[i]+(num%i)*d,(num-num//i)*d)
            new_num = num//i
            if new_num not in dct or new_cost<dct[new_num]:
                heappush(h,(new_cost,new_num))
                dct[new_num] = new_cost
            new_cost = cost + min(x[i]+(i-num%i)*d,(num-num//i-1)*d)
            new_num = num//i+1
            if new_num not in dct or new_cost<dct[new_num]:
                heappush(h,(new_cost,new_num))
                dct[new_num] = new_cost

    ans.append(cost+d)

printrows(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)
t=int(input())

def dfs(i):
	if i==0:
		return 0
	if i in memo:
		return memo[i]
	ret=i*d
	if i%2==0:
		ret=min(ret,dfs(i//2)+a)
	else:
		ret=min(ret,dfs((i-1)//2)+a+d)
		if not i==1:
			ret=min(ret,dfs((i+1)//2)+a+d)
	if i%3==0:
		ret=min(ret,dfs(i//3)+b)
	elif i%3==1:
		ret=min(ret,dfs((i-1)//3)+b+d)
	else:
		ret=min(ret,dfs((i+1)//3)+b+d)
	if i%5==0:
		ret=min(ret,dfs(i//5)+c)
	elif i%5==1:
		ret=min(ret,dfs((i-1)//5)+c+d)
	elif i%5==2:
		ret=min(ret,dfs((i-2)//5)+c+2*d)
	elif i%5==3:
		ret=min(ret,dfs((i+2)//5)+c+2*d)
	else:
		ret=min(ret,dfs((i+1)//5)+c+d)
	memo[i]=ret
	return ret

ans=[]
for _ in range(t):
	n,a,b,c,d=map(int,input().split())
	memo={}
	ans.append(dfs(n))
print("\n".join(map(str,ans)))

Solution (Python):
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, A, B, C, D = map(int, rl().split())
    
    @lru_cache(maxsize=None)
    def calc(t):
        if t == 0:
            return 0
        if t == 1:
            return D
        
        res = min(
            D * t,
            D * abs(t - t // 5 * 5) + C + calc(t // 5),
            D * abs(t - (t + 4) // 5 * 5) + C + calc((t + 4) // 5),
            D * abs(t - t // 3 * 3) + B + calc(t // 3),
            D * abs(t - (t + 2) // 3 * 3) + B + calc((t + 2) // 3),
            D * abs(t - t // 2 * 2) + A + calc(t // 2),
            D * abs(t - (t + 1) // 2 * 2) + A + calc((t + 1) // 2)
        )
        return res
    
    return calc(N)


if __name__ == '__main__':
    T = int(rl())
    ans = []
    for _ in range(T):
        ans.append(solve())
    print(*ans, sep='\n')

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict
t = int(input())
def chmin(a,b):
  a = min(a,b)
def calc(x):
  ret = d*x
  if dc[x] < 10**36:
    return dc[x]
  if x:
    ret = min(ret,calc(x//2)+a+d*(x%2))
  if x%2 and x > 1:
    ret = min(ret,calc(x//2+1)+a+d)
  if x:
    ret = min(ret,calc(x//3)+b+d*(x%3))
  if x%3 and x > 1:
    ret = min(ret,calc(x//3+1)+b+d*(3-x%3))
  if x:
    ret = min(ret,calc(x//5)+c+d*(x%5))
  if x%5 and x > 1:
    ret = min(ret,calc(x//5+1)+c+(5-x%5)*d)
  dc[x] = ret
  return ret
for _ in range(t):
  n,a,b,c,d = map(int,input().split())
  ans = n*d
  dc = defaultdict(lambda:10**36)
  if n == 1:
    print(ans)
  else:
    dc[0] = 0
    dc[1] = d
    print(min(ans,calc(n)))

Solution (Python):
from functools import lru_cache


@lru_cache(None)
def f(x):
    if x == 0:
        return 0
    if x == 1:
        return D
    res = D*x
    for i in [2, 3, 5]:
        res = min(res, f(x//i)+x%i*D+coins[i], f(-(-x//i))+(i-x%i)*D+coins[i])
    return res


T = int(input())
for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    coins = {2: A, 3: B, 5: C}
    print(f(N))
    f.cache_clear()

Solution (Python):
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)))

Solution (Python):
T = int(input())

def solve():
    def dist(x):
        if x == 0:
            return 0
        if x == 1:
            return D
        if x in dic:
            return dic[x]
        tmp = min(
            D * x,
            D * abs(x - x // 5 * 5) + C + dist(x // 5),
            D * abs(x - (x + 5 - 1) // 5 * 5) + C + dist((x + 5 - 1) // 5),
            D * abs(x - x // 3 * 3) + B + dist(x // 3),
            D * abs(x - (x + 3 - 1) // 3 * 3) + B + dist((x + 3 - 1) // 3),
            D * abs(x - x // 2 * 2) + A + dist(x // 2),
            D * abs(x - (x + 2 - 1) // 2 * 2) + A + dist((x + 2 - 1) // 2)
        )
        dic[x] = tmp
        return tmp

    N, A, B, C, D = map(int, input().split())
    
    dic = dict()
    print (dist(N))

for _ in range(T):
    solve()

Solution (Python):
from functools import lru_cache

def solve(N, A, B, C, D):
    @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)
        else:
            ret = min(ret, f(q) + B + D*r, f(q + 1) + B + D*(3-r))
        q, r = divmod(N, 5)
        if r == 0:
            ret = min(ret, f(q) + C)
        else:
            ret = min(ret, f(q) + C + D*r, f(q + 1) + C + D*(5-r))
        return ret

    return f(N)

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

Solution (Python):
peak = int(1e18)
A, B, C, D = 0, 0, 0, 0
memo = {}
def PtW(n):
    if n == 0:
        return 0
    if n == 1:
        return D
    if n in memo:
        return memo[n]
    m = peak
    if n * D < peak:
        m = n * D
    u2, d2 = n // 2 + (n % 2 != 0), n // 2
    u3, d3 = n // 3 + (n % 3 != 0), n // 3
    u5, d5 = n // 5 + (n % 5 != 0), n // 5
    m = min(m, abs(u2*2-n)*D+A+PtW(u2))
    m = min(m, abs(d2*2-n)*D+A+PtW(d2))
    m = min(m, abs(u3*3-n)*D+B+PtW(u3))
    m = min(m, abs(d3*3-n)*D+B+PtW(d3))
    m = min(m, abs(u5*5-n)*D+C+PtW(u5))
    m = min(m, abs(d5*5-n)*D+C+PtW(d5))
    memo[n] = m
    return m
T = int(input())
for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    memo = {}
    print(PtW(N))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

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

    def cost(N):
        if N in memo:
            return memo[N]
        ans = N * d
        ks = [2, 3, 5]
        abc = [a, b, c]
        for i in range(3):
            k = ks[i]
            coin = abc[i]
            div, mod = divmod(N, k)
            pay = mod * d + coin
            ans = min(ans, pay + cost(div))
            if mod == 0:
                continue
            pay = (k - mod) * d + coin
            ans = min(ans, pay + cost(div + 1))
        memo[N] = ans
        return ans

    print(cost(n))

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
t = int(input())
l = [list(map(int,input().split())) for _ in range(t)]

def f(n):
    if n in memo:
        return memo[n]
    else:
        temp = min(
            d*n,
            d*(n-(n//2)*2)+a+f(n//2),
            d*(((n+1)//2)*2-n)+a+f((n+1)//2),
            d*(n-(n//3)*3)+b+f(n//3),
            d*(((n+2)//3)*3-n)+b+f((n+2)//3),
            d*(n-(n//5)*5)+c+f(n//5),
            d*(((n+4)//5)*5-n)+c+f((n+4)//5)
        )
        memo[n] = temp
        return temp

for i in range(t):
    n,a,b,c,d = l[i]
    memo = {}
    memo[1] = d
    memo[0] = 0
    print(f(n))

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
t = int(input())
l = [list(map(int,input().split())) for _ in range(t)]

def f(n):
    if n in memo:
        return memo[n]
    else:
        temp = min(
            d*n,
            d*(n-(n//2)*2)+a+f(n//2),
            d*(((n+1)//2)*2-n)+a+f((n+1)//2),
            d*(n-(n//3)*3)+b+f(n//3),
            d*(((n+2)//3)*3-n)+b+f((n+2)//3),
            d*(n-(n//5)*5)+c+f(n//5),
            d*(((n+4)//5)*5-n)+c+f((n+4)//5)
        )
        memo[n] = temp
        return temp

for i in range(t):
    n,a,b,c,d = l[i]
    memo = {}
    memo[1] = d
    memo[0] = 0
    print(f(n))

Solution (Python):
dp = {}
n,a,b,c,d = 0,0,0,0,0

def get(n):
	global dp,a,b,c,d
	if (n in dp.keys()): return dp[n]
	dp[n] = d * n
	if(n >= 2): dp[n] = min(dp[n], get(n // 2) + (n % 2) * d + a)
	dp[n] = min(dp[n], get(n // 2 + 1) + (2 - n % 2) * d + a)
	if(n >= 3): dp[n] = min(dp[n], get(n // 3) + (n % 3) * d + b)
	dp[n] = min(dp[n], get(n // 3 + 1) + (3 - n % 3) * d + b)
	if(n >= 5): dp[n] = min(dp[n], get(n // 5) + (n % 5) * d + c)
	dp[n] = min(dp[n], get(n // 5 + 1) + (5 - n % 5) * d + c)
	
	return dp[n]

def solve():
	global dp, n, a, b, c, d
	n,a,b,c,d = [*map(int,input().split())]
	dp = {}

	print(get(n))

cas = int(input())
for ca in range(cas):
    solve()

Solution (Python):
memo = dict()


def calc(n):
    if n == 0:
        return 0
    if n == 1:
        return d
    if n in memo:
        return memo[n]

    ret = min(n * d,
              a + calc(n//2) + (n % 2) * d,
              a + calc((n+1)//2) + ((2 - (n % 2)) % 2) * d,
              b + calc(n//3) + (n % 3) * d,
              b + calc((n+2)//3) + ((3 - (n % 3)) % 3) * d,
              c + calc(n//5) + (n % 5) * d,
              c + calc((n+4)//5) + ((5 - (n % 5)) % 5) * d)

    memo[n] = ret
    return ret


t = int(input())
for i in range(t):
    n, a, b, c, d = map(int, input().split())
    print(calc(n))
    memo = dict()

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    t = int(ipt())

    for _ in [0]*t:
        n,a,b,c,d = map(int,ipt().split())
        dp = defaultdict(lambda:-1)
        dp[0] = 0
        dp[1] = d

        def calc(n):
            mi = d*n
            for i,x in {(2,a),(3,b),(5,c)}:
                if dp[n//i] == -1:
                    dp[n//i] = calc(n//i)
                if mi > d*(n-n//i*i)+x+dp[n//i]:
                    mi = d*(n-n//i*i)+x+dp[n//i]
                if not n%i == 0:
                    if dp[n//i+1] == -1:
                        dp[n//i+1] = calc(n//i+1)
                    if mi > d*((n//i+1)*i-n)+x+dp[n//i+1]:
                        mi = d*((n//i+1)*i-n)+x+dp[n//i+1]
            return mi

        print(calc(n))

    return



if __name__ == '__main__':
    main()

Solution (Python):
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)

t = int(input())
for _ in range(t):
    
    n, a, b, c, d = map(int, input().split())
    @lru_cache(None)
    def solve(n):
        tmp = n * d
        if n == 0:
            return 0
        if n == 1:
            return d
            
        if n % 2 == 0:
            tmp = min(tmp, solve(n // 2) + a)
        else:
            tmp = min(tmp, solve(n // 2) + a + d)
            tmp = min(tmp, solve(n // 2 + 1) + a + d)
        
        r = n % 3
        if r == 0:
            tmp = min(tmp, solve(n // 3) + b)
        elif r == 1:
            tmp = min(tmp, solve(n // 3) + b + d)
        else:
            tmp = min(tmp, solve(n // 3 + 1) + b + d)
        
        r = n % 5
        if r == 0:
            tmp = min(tmp, solve(n // 5) + c)
        elif r == 1:
            tmp = min(tmp, solve(n // 5) + c + d)
        elif r == 2:
            tmp = min(tmp, solve(n // 5) + c + d + d)
        elif r == 3:
            tmp = min(tmp, solve(n // 5 + 1) + c + d + d)    
        else:
            tmp = min(tmp, solve(n // 5 + 1) + c + d)
            
        return tmp
    
    ans = solve(n)
    print(ans)