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

Submission status: Accepted

Solution code:
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
    # print(x,D)
    if x in D:
        # print("rt")
        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
        # print("wr")
        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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)
	# print(f'n {n} {dp[n]}')
	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()

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
t = int(input())
l=[list(map(int,input().split())) for i in range(t)]
from collections import defaultdict

def solve(n):
    if n==1:
        return d
    if n==0:
        return 0
    if memo[n] != -1:
        return memo[n]

    ret = []
    ret.append(d*n)

    if n%2==0:
        ret.append(a + solve(n//2))
    else:
        ret.append(d + a + solve((n+1)//2))
        ret.append(d + a + solve((n-1)//2))

    if n%3==0:
        ret.append(b + solve(n//3))
    else:
        if (n+1)%3==0:
            ret.append(d + b + solve((n+1)//3))
        else:
            ret.append(d + b + solve((n-1)//3))

    if n%5==0:
        ret.append(c + solve(n//5))
    else:
        if (n-2)%5==0:
            ret.append(2*d + c + solve((n-2)//5))
        elif (n-1)%5==0:
            ret.append(d + c + solve((n-1)//5))
        elif (n+1)%5==0:
            ret.append(d + c + solve((n+1)//5))
        elif (n+2)%5==0:
            ret.append(2*d + c + solve((n+2)//5))

    memo[n]=min(ret)

    return min(ret)

for tmp in l:
    n,a,b,c,d=tmp

    memo=defaultdict(lambda: -1)
    ans = solve(n)
    print(ans)

Submission status: Accepted

Solution code:
# A - Pay to Win
import sys
sys.setrecursionlimit(10000)

T = int(input())
a = [list(map(int,input().split())) for _ in range(T)]
memo = {}

# N,A,B,C,D
def solve(N,A,B,C,D):
    if N==0:
        return 0
    if N==1:
        return D
    if N in memo:
        return memo[N]
    ans = min(
        D*N,
        (N-2*(N//2))*D+A+solve(N//2,A,B,C,D),
        (2*((N+1)//2)-N)*D+A+solve((N+1)//2,A,B,C,D),
        (N-3*(N//3))*D+B+solve(N//3,A,B,C,D),
        (3*((N+2)//3)-N)*D+B+solve((N+2)//3,A,B,C,D),
        (N-5*(N//5))*D+C+solve(N//5,A,B,C,D),
        (5*((N+4)//5)-N)*D+C+solve((N+4)//5,A,B,C,D),
    )
    memo[N] = ans
    return ans

for i in range(T):
    memo = {}
    (N,A,B,C,D) = a[i]
    print(solve(N,A,B,C,D))

Submission status: Accepted

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: Accepted

Solution code:
import sys
input=sys.stdin.readline
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: Accepted

Solution code:

MEMO = {}

def solve(N, A, B, C, D):
    # 戦略
    # 0からNを作るのではなく、
    # Nから+-1, /2, /3, /5 の操作を繰り返して
    # 0にたどり着くことを考える

    if N == 0:
        return 0
    elif N == 1:
        return D
    elif N in MEMO:
        return MEMO[N]
    
    # 例: N = 13 の場合
    # 0から13にたどり着くまでに、次の7通りが考えられる
    # 1. 0から+1を13回繰り返す: コスト = D * 13
    # 2. 6を2倍して+1: コスト = [0から6を作るコスト] + A + D * (13 - 12)
    # 3. 7を2倍して-1: コスト = [0から7を作るコスト] + A + D * (14 - 13)
    # 4. 4を3倍して+1: コスト = [0から4を作るコスト] + B + D * (13 - 12)
    # 5. 5を3倍して-2: コスト = [0から5を作るコスト] + B + D * (15 - 13)
    # 6. 2を5倍して+3: コスト = [0から2を作るコスト] + C + D * (13 - 10)
    # 7. 3を5倍して-2: コスト = [0から3を作るコスト] + C + D * (15 - 13)

    min_score = D * N # case 1

    # # case 2, 3
    # div2_1 = N // 2
    # div2_2 = (N + 1) // 2
    # min_score = min(min_score, solve(div2_1, A, B, C, D) + A + D * abs(N - 2 * div2_1))
    # min_score = min(min_score, solve(div2_2, A, B, C, D) + A + D * abs(N - 2 * div2_2))

    # # case 4, 5
    # div3_1 = N // 3
    # div3_2 = (N + 2) // 3
    # min_score = min(min_score, solve(div3_1, A, B, C, D) + B + D * abs(N - 3 * div3_1))
    # min_score = min(min_score, solve(div3_2, A, B, C, D) + B + D * abs(N - 3 * div3_2))

    # # case 6, 7
    # div5_1 = N // 5
    # div5_2 = (N + 4) // 5
    # min_score = min(min_score, solve(div5_1, A, B, C, D) + C + D * abs(N - 5 * div5_1))
    # min_score = min(min_score, solve(div5_2, A, B, C, D) + C + D * abs(N - 5 * div5_2))

    # 丁寧に書くと上のようになるが、
    # 面倒なので下のようにしてまとめる
    div_score = {2: A, 3: B, 5: C}

    for d, s in div_score.items():
        div1 = N // d
        div2 = (N + d - 1) // d
        min_score = min(min_score, solve(div1, A, B, C, D) + s + D * abs(N - d * div1))
        min_score = min(min_score, solve(div2, A, B, C, D) + s + D * abs(N - d * div2))

    # 再帰呼び出しで同じNについて何回も計算する可能性があるので、
    # 1度計算した値はメモしておく
    MEMO[N] = min_score
    return min_score


def main():
    T = int(input())
    queries = []
    for t in range(T):
        queries.append(list(map(int, input().split())))
    
    ans = []
    for N, A, B, C, D in queries:
        MEMO.clear()
        ans.append(solve(N, A, B, C, D))

    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def examA():
    T = I()
    ans = [inf]*T
    for t in range(T):
        N, A, B, C, D = LI()
        num = [[2,A],[3,B],[5,C]]
        dp = defaultdict(lambda: inf)
        dp[N] = 0
        que = deque()
        que.append(N)
        while(que):
            now = que.pop()
            if now==0:
                continue
            cur = dp[now] + D*now
            if cur<dp[0]:
                dp[0] = cur
            cur = dp[now]
            for n,K in num:
                curn = cur + (now % n) * D + K
                if curn < dp[(now - now % n) // n]:
                    dp[(now - now % n) // n] = curn
                    que.append((now - now % n) // n)
                curn_ = cur + (-now % n) * D + K
                if curn_ < dp[(now + (-now % n)) // n]:
                    dp[(now + (-now % n)) // n] = curn_
                    que.append((now + (-now % n)) // n)
        ans[t] = dp[0]
    for v in ans:
        print(v)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return


import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examA()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
import heapq

T = int(input())
for t in range(T):
    N,A,B,C,D = map(int,input().split())
    q = [(0,N)]
    heapq.heapify(q)
    seen = set()
    while q:
        cost, n = heapq.heappop(q)
        if n in seen:
            continue
        seen.add(n)
        if n == 0:
            print(cost)
            break

        heapq.heappush(q, (cost + n * D, 0))
        if n % 2 ==0:
            heapq.heappush(q, (cost + A, n // 2))
        else: # odd number
            heapq.heappush(q, (cost + D + A, (n + 1) // 2))
            heapq.heappush(q, (cost + D + A, (n - 1) // 2))
        if n % 3 ==0:
            heapq.heappush(q, (cost + B, n // 3))
        else:
            rest = n % 3
            heapq.heappush(q, (cost + rest * D + B, (n - rest) // 3))
            heapq.heappush(q, (cost + (3-rest) * D + B, (n - rest + 3) // 3))

        if n % 5 ==0:
            heapq.heappush(q, (cost + C, n // 5))
        else:
            rest = n % 5
            heapq.heappush(q, (cost + rest * D + C, (n - rest) // 5))
            heapq.heappush(q, (cost + (5-rest) * D + C, (n - rest + 5) // 5))

Submission status: Accepted

Solution code:
from decimal import Decimal
import math
import sys
sys.setrecursionlimit(10**9)


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

    memo = dict()
    memo[0] = 0
    memo[1] = d

    def solve(v):
        if v in memo:
            return memo[v]

        if v > 10**16:
            v = Decimal(v)

        memo[v] = min(solve(math.floor(v / 5)) + c + (v - math.floor(v / 5) * 5) * d,
                      solve(math.ceil(v / 5)) + c + (math.ceil(v / 5) * 5 - v) * d,
                      solve(math.floor(v / 3)) + b + (v - math.floor(v / 3) * 3) * d,
                      solve(math.ceil(v / 3)) + b + (math.ceil(v / 3) * 3 - v) * d,
                      solve(math.floor(v / 2)) + a + (v - math.floor(v / 2) * 2) * d,
                      solve(math.ceil(v / 2)) + a + (math.ceil(v / 2) * 2 - v) * d,
                      v * d)
        return memo[v]

    print(solve(n))

Submission status: Accepted

Solution code:
t = int(input())
for i in range(t):
    n, a, b, c, d = map(int, input().split())
    e = {}
    def coin(n):
        if n == 0:
            return 0
        if n == 1:
            return d
        if n in e:
            return e[n]
        f = min(
            d*n,
            d*abs(n-n//5*5)+c+coin(n//5),
            d*abs(n-(n+4)//5*5)+c+coin((n+4)//5),
            d*abs(n-n//3*3)+b+coin(n//3),
            d*abs(n-(n+2)//3*3)+b+coin((n+2)//3),
            d*abs(n-n//2*2)+a+coin(n//2),
            d*abs(n-(n+1)//2*2)+a+coin((n+1)//2)
        )
        e[n] = f
        return f
    print(coin(n))

Submission status: Accepted

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

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

 
for i in range(t):
    N = l[i][0]
    A = l[i][1]
    B = l[i][2]
    C = l[i][3]
    D = l[i][4]
    @lru_cache(maxsize=10**18)
    def min_coin(n):
        if(n == 0):
            return 0
        elif(n == 1):
            return D
        else:
            if(n%2 == 0):
                a = min_coin(n//2)
            else:
                a = min(min_coin(n//2)+D,min_coin(n//2+1)+D)
            if(n%3 == 0):
                b = min_coin(n//3)
            elif(n%3 == 1):
                b = min(min_coin(n//3)+D,min_coin(n//3+1)+D*2)
            else:
                b = min(min_coin(n//3)+D*2,min_coin(n//3+1)+D)
            if(n%5 == 0):
                c = min_coin(n//5)
            else:
                re = n%5
                c = min(min_coin(n//5)+D*re,min_coin(n//5+1)+D*(5-re))
            return min(a+A,b+B,c+C,D*n)   
    print(int(min_coin(N)))

Submission status: Accepted

Solution code:
from collections import defaultdict


def calc(case):
    # /2, /3, /5, +-1
    N, A, B, C, D = case
    memo = defaultdict(int)
    x = N
    def dp(n):
        if n == 0:
            return 0
        elif n == 1:
            return D
        elif n == 2:
            return D + min([A, D])
        for k in [2, 3, 5]:
            for i in [0, 1]:
                if memo[n // k + i] == 0:
                    memo[n // k + i] = dp(n // k + i)
        ret = min([
            n * D, 
            A + (n % 2) * D + memo[n // 2],
            A + (2 - n % 2) * D + memo[n // 2 + 1],
            B + (n % 3) * D + memo[n // 3],
            B + (3 - n % 3) * D + memo[n // 3 + 1],
            C + (n % 5) * D + memo[n // 5],
            C + (5 - n % 5) * D + memo[n // 5 + 1]
        ])
        return ret
    return dp(N)


def main():
    T = int(input())
    cases = [list(map(int, input().split())) for _ in range(T)]
    for case in cases:
        print(calc(case))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
class dfs:
    def __init__(self,n,a,b,c,d):
        self.N = n
        self.A = a
        self.B = b
        self.C = c
        self.D = d
        self.ans = self.N * self.D
        self.memory = defaultdict(int)
        self.Q = deque([[self.N,0]])
    def dfs(self):
        while self.Q:
            num,cost = self.Q.popleft()
            if self.memory[num] > cost :
                pass
            else:
                if num == 0:
                    self.ans = min(self.ans,cost)
                elif num == 1:
                    self.ans = min(self.ans,cost+self.D)
                else:
                    for step,a_cost in [[2,self.A],[3,self.B],[5,self.C]]:
                        if num % step != 0:
                            temp_num = (num//step)+1
                            temp_cost = cost + (((num//step)+1)*step - num) * self.D + a_cost
                            self.memo_check_append(temp_num,temp_cost)
                        temp_num = num//step
                        temp_cost = cost + (num - (num//step)*step) * self.D + a_cost
                        self.memo_check_append(temp_num,temp_cost)
                    self.ans = min(self.ans,cost + num * self.D)
        return self.ans
    def memo_check_append(self,n,c):
        if self.memory[n] > c or self.memory[n] == 0:
            self.Q.append([n,c])
            self.memory[n] = c

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