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:

from collections import defaultdict

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

    memo = {0: 0, 1: D}

    def dfs(n):
        if n in memo:
            return memo[n]
        
        ret = min(n * D, 
                  dfs(n//2) + (n - n//2*2) * D + A,
                  dfs(-(-n//2)) + (-(-n//2)*2 - n) * D + A,
                  dfs(n//3) + (n - n//3*3) * D + B,
                  dfs(-(-n//3)) + (-(-n//3)*3 - n) * D + B,
                  dfs(n//5) + (n - n//5*5) * D + C,
                  dfs(-(-n//5)) + (-(-n//5)*5 - n) * D + C)

        memo[n] = ret
        return ret

    print(dfs(N))

Submission status: Accepted

Solution code:
def main():
    n , a , b , c , d = map(int,input().split())
    dic = {}
    def f(x):
        if x == 0:
            return 0
        elif x == 1:
            return d
        elif x in dic: #メモ化
            return dic[x]
        t1 = d*x                           #愚直に引いていく 
        t2 = d*(x%2)     + a + f(x//2)     #下げて2で割る
        t3 = d*(2-(x%2)) + a + f(-(-x//2)) #上げて2で割る
        t4 = d*(x%3)     + b + f(x//3)     #下げて3で割る
        t5 = d*(3-(x%3)) + b + f(-(-x//3)) #上げて3で割る
        t6 = d*(x%5)     + c + f(x//5)     #下げて5で割る
        t7 = d*(5-(x%5)) + c + f(-(-x//5)) #上げて5で割る
        t = min(t1,t2,t3,t4,t5,t6,t7) #どの操作が最小？
        dic[x] = t #メモ化
        return t
    print(f(n))
    return
    
t = int(input())
for i in range(t):
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def calc(n):
    if memo[n] != float('inf'):
        return memo[n]
    if n == 0:
        return 0
    if n == 1:
        return D
    ans = n * D
    for x, c in [(2, A), (3, B), (5, C)]:
        ans = min(ans, calc(n//x) + c + (n % x) * D)
        if n % x:
            ans = min(ans, calc(n//x + 1) + c + (x - n % x) * D)
    memo[n] = ans
    return memo[n]


t = int(input())
for _ in range(t):
    N, A, B, C, D = map(int, input().split())
    memo = defaultdict(lambda: float('inf'))
    print(calc(N))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
enum = enumerate
inf = 1001001002002002002

import random

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().rstrip().split()))

def vinput(rep=1, ty=int, cvt=list):
	return cvt(ty(input().rstrip()) for _ in "*"*rep)

def gcd(a: int, b: int):
	while b: a, b = b, a%b
	return a

def lcm(a: int, b: int):
	return a * b // gcd(a, b)

def bye(res):
	sT = "No Yes".split()
	print(sT[res])
	#exit(0)

def sol2(N,A,B,C,D):
	dM = dict({0: 0, 1: D})
	
	def dfs(n):
		if n in dM:
			return dM[n]

		res = min(
				D*n,
				D*(n%2) + A + dfs(n//2),
				D*(n%3) + B + dfs(n//3),
				D*(n%5) + C + dfs(n//5),
				D*(n%2) + A + dfs((n+1)//2),
				D*((3 - n%3)%3) + B + dfs((n+2)//3),
				D*((5 - n%5)%5) + C + dfs((n+4)//5)
			)

		dM[n] = res
		return res
	
	dfs(N)
	#print(dM)###
	print(dM[N])


def main():
	T, = linput()
	for _ in "*"*T:
		sol2(*linput())

def ran():
	vRan = [random.randint(1,10) for _ in "*"*5]
	print(vRan)
	sol2(*vRan)

if __name__ == "__main__":
	main()
	#ran()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
enum = enumerate
inf = 1001001002002002002

import random

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().rstrip().split()))

def vinput(rep=1, ty=int, cvt=list):
	return cvt(ty(input().rstrip()) for _ in "*"*rep)

def gcd(a: int, b: int):
	while b: a, b = b, a%b
	return a

def lcm(a: int, b: int):
	return a * b // gcd(a, b)

def bye(res):
	sT = "No Yes".split()
	print(sT[res])
	#exit(0)

def sol(N,A,B,C,D):
	res = inf
	at,bt,ct,dt = [0,]*4
	an,bn,cn,dn = [0,]*4
	cn = N
	for c in range(32):
		bn = cn
		for b in range(42):
			an = bn
			for a in range(63):
				dt = at+bt+ct+ an
				r = a*A+b*B+c*C+dt*D
				if res>r: print(a,b,c,dt,r)###
				res = min(res, r)
				if not an: break
				at += an%2
				an = an//2
			at = 0
			bt += 0<bn%3
			bn = bn//3 + (bn%3==2)
		bt = 0
		cMod5 = cn%5
		ct += min(5-cMod5, cMod5)
		cn = cn//5 + (cMod5>2)
	
	print(res)

def sol2(N,A,B,C,D):
	dM = dict({0: 0, 1: D})
	
	def dfs(n):
		if n in dM.keys():
			return dM[n]

		res = min(
				D*n,
				D*(n%2) + A + dfs(n//2),
				D*(n%3) + B + dfs(n//3),
				D*(n%5) + C + dfs(n//5),
				D*(n%2) + A + dfs((n+1)//2),
				D*((3 - n%3)%3) + B + dfs((n+2)//3),
				D*((5 - n%5)%5) + C + dfs((n+4)//5)
			)

		dM[n] = res
		return res
	
	dfs(N)
	#print(dM)###
	print(dM[N])


def main():
	T, = linput()
	for _ in "*"*T:
		sol2(*linput())

def ran():
	vRan = [random.randint(1,10) for _ in "*"*5]
	print(vRan)
	sol2(*vRan)

if __name__ == "__main__":
	main()
	#ran()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 5)


def main():
    INF = float('INF')

    from collections import defaultdict, deque
    t = int(readline())

    for _ in range(t):
        n, a, b, c, d = map(int, readline().split())
        memo = defaultdict(lambda: INF)
        memo[n] = 0
        que = deque()
        que.append((n, 0))
        ans = n * d

        while que:
            cur, score = que.popleft()
            ans = min(ans, score + cur*d)

            if cur == 0:
                continue

            if cur % 2 == 0:
                if score + a < memo[cur // 2] and a < cur // 2 * d:
                    memo[cur // 2] = score + a
                    que.append((cur // 2, score + a))
            else:
                diff1 = cur % 2
                diff2 = 2 - diff1
                nx1 = (cur - diff1) // 2
                nx2 = (cur + diff2) // 2
                cost1 = a + diff1 * d
                cost2 = a + diff2 * d
                if score + cost1 < memo[nx1]:
                    memo[nx1] = score + cost1
                    que.append((nx1, score + cost1))
                if score + cost2 < memo[nx2]:
                    memo[nx2] = score + cost2
                    que.append((nx2, score + cost2))

            if cur % 3 == 0:
                if score + b < memo[cur // 3] and b < 2 * cur // 3 * d:
                    memo[cur // 3] = score + b
                    que.append((cur // 3, score + b))
            else:
                diff1 = cur % 3
                diff2 = 3 - diff1
                nx1 = (cur - diff1) // 3
                nx2 = (cur + diff2) // 3
                cost1 = b + diff1 * d
                cost2 = b + diff2 * d
                if score + cost1 < memo[nx1]:
                    memo[nx1] = score + cost1
                    que.append((nx1, score + cost1))
                if score + cost2 < memo[nx2]:
                    memo[nx2] = score + cost2
                    que.append((nx2, score + cost2))

            if cur % 5 == 0:
                if score + c < memo[cur // 5] and c < 4 * cur // 5 * d:
                    memo[cur // 5] = score + c
                    que.append((cur // 5, score + c))
            else:
                diff1 = cur % 5
                diff2 = 5 - diff1
                nx1 = (cur - diff1) // 5
                nx2 = (cur + diff2) // 5
                cost1 = c + diff1 * d
                cost2 = c + diff2 * d
                if score + cost1 < memo[nx1]:
                    memo[nx1] = score + cost1
                    que.append((nx1, score + cost1))
                if score + cost2 < memo[nx2]:
                    memo[nx2] = score + cost2
                    que.append((nx2, score + cost2))

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict
import math
t = int(input())
def solve(n):
    if dist[n] != float('inf'):
        return dist[n]
    if n == 0:
        return 0
    if n == 1:
        return d
    ans = float('inf')
    for x,cost in ([5,c],[3,b],[2,a]):
        e = 0
        if n%x:
            e = 1 
        y = n%x
        ans = min(ans,solve(n//x) + cost + (e*d*y))

        if e ==1:
            ans = min(ans,solve(n//x+1) + cost + ((x-y)*d))
    dist[n] = min(ans,n*d)   
    return dist[n]

for i in range(t):
    n,a,b,c,d, = list(map(int,input().split()))
    dist = defaultdict(lambda: float('inf'))
    print(solve(n))

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import defaultdict
from heapq import *

def main():
	t=II()
	while t:
		t-=1
		n,a,b,c,d=MI()
		Q=[-n,0]
		heapify(Q)
		D=defaultdict(lambda:10**18)
		D[n]=0
		k=n+1
		while Q:
			now=-heappop(Q)
			#print(now,"a")
			if now==0:
				print(D[0])
				break

			if now<k:
				q2,r2=divmod(now,2)
				q3,r3=divmod(now,3)
				q5,r5=divmod(now,5)

				#print(now)
				if D[q5]>D[now]+c+r5*d:
					D[q5]=D[now]+c+r5*d
					heappush(Q,-q5)
				if r5!=0 and D[q5+1]>D[now]+c+(5-r5)*d:
					D[q5+1]=D[now]+c+(5-r5)*d
					heappush(Q,-q5-1)

				if D[q3]>D[now]+b+r3*d:
					D[q3]=D[now]+b+r3*d
					heappush(Q,-q3)
				if r3!=0 and D[q3+1]>D[now]+b+(3-r3)*d:
					D[q3+1]=D[now]+b+(3-r3)*d
					heappush(Q,-q3-1)

				if D[q2]>D[now]+a+r2*d:
					D[q2]=D[now]+a+r2*d
					heappush(Q,-q2)
				if r2!=0 and D[q2+1]>D[now]+a+(2-r2)*d:
					D[q2+1]=D[now]+a+(2-r2)*d
					heappush(Q,-q2-1)

				D[0]=min(D[0],D[now]+now*d)







if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import math
T = int(input())
for t in range(T):
    N, A, B, C, D = map(int, input().split())
    memo = {}

    def dist(n):
        if n == 0:
            return 0
        elif n == 1:
            return D
        elif n in memo:
            return memo[n]

        ret = min(
            D * n,
            D * abs(n - n//5*5) + C + dist(n//5),
            D * abs(n - (n+4)//5*5) + C + dist((n+4)//5),
            D * abs(n - n//3*3) + B + dist(n//3),
            D * abs(n - (n+2)//3*3) + B + dist((n+2)//3),
            D * abs(n - n//2*2) + A + dist(n//2),
            D * abs(n - (n+1)//2*2) + A + dist((n+1)//2)
        )

        memo[n] = ret
        return ret
    print(dist(N))

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


def solve():
    N, a, b, c, d = map(int, input().split())

    @lru_cache(maxsize=None)
    def F(n):
        if n == 0:
            return 0
        if n == 1:
            return d
        ans = n * d
        if n % 2 == 0:
            ans = min(ans, F(n//2) + a)
        if n % 2 == 1:
            up = F((n + 1) // 2) + a + d
            down = F((n - 1) // 2) + a + d
            ans = min(ans, up, down)
        if n % 3 == 0:
            ans = min(ans, F(n // 3) + b)
        if n % 3 == 1:
            up = F((n + 2) // 3) + b + d + d
            down = F((n - 1) // 3) + b + d
            ans = min(ans, up, down)
        if n % 3 == 2:
            up = F((n + 1) // 3) + b + d
            down = F((n - 2) // 3) + b + d + d
            ans = min(ans, up, down)
        if n % 5 == 0:
            ans = min(ans, F(n // 5) + c)
        if n % 5 == 1:
            up = F((n + 4) // 5) + c + d + d + d + d
            down = F((n - 1) // 5) + c + d
            ans = min(ans, up, down)
        if n % 5 == 2:
            up = F((n + 3) // 5) + c + d + d + d
            down = F((n - 2) // 5) + c + d + d
            ans = min(ans, up, down)
        if n % 5 == 3:
            up = F((n + 2) // 5) + c + d + d
            down = F((n - 3) // 5) + c + d + d + d
            ans = min(ans, up, down)
        if n % 5 == 4:
            up = F((n + 1) // 5) + c + d
            down = F((n - 4) // 5) + c + d + d + d + d
            ans = min(ans, up, down)
        return ans

    print(F(N))


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

Submission status: Accepted

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

Submission status: Accepted

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

T = int(input())
from collections import deque
INF = 10**18

def transit(n, i, p):
    if p == 1:
        num = ((n+(i-1))//i)*i
        cos = d * (num - n)
        num //= i
        cos += ci[i]
    else:
        num = (n//i)*i
        cos = d * (n - num)
        num //= i
        cos += ci[i]
    return (num, cos)

for _ in range(T):
    N, a2, a3, a5, d = map(int, input().split())
    ci = {}
    ci[2]=a2
    ci[3]=a3
    ci[5]=a5
    dp = {}
    def cost(n):
        if n == 0:
            return 0
        if n == 1:
            return d
        if n in dp:
            return dp[n]
        ret = n * d
        for i in [2,3,5]:
            num, cos = transit(n, i, 1)
            ret = min(ret, cos + cost(num))
            num, cos = transit(n, i, -1)
            ret = min(ret, cos + cost(num))
        dp[n] = ret
        return ret
    print(cost(N))

Submission status: Accepted

Solution code:
class Solver:
    def __init__(self, n, a, b, c, d):
        self.n = n
        self.a = a
        self.b = b
        self.c = c
        self.d = d
        self.dc = {}

    def coin(self, n):

        if n == 0:
            return 0
        elif n == 1:
            return self.d
        elif n == -1:
            return self.d
        elif n in self.dc.keys():
            return self.dc[n]
        else:
            coin1 = n * self.d
            coin2 = min(
                (n % 2) * self.d + self.a + self.coin((n - n % 2) // 2),
                ((-n) % 2) * self.d + self.a + self.coin((n + (-n) % 2) // 2),
            )
            coin3 = min(
                (n % 3) * self.d + self.b + self.coin((n - n % 3) // 3),
                ((-n) % 3) * self.d + self.b + self.coin((n + (-n) % 3) // 3),
            )
            coin5 = min(
                (n % 5) * self.d + self.c + self.coin((n - n % 5) // 5),
                ((-n) % 5) * self.d + self.c + self.coin((n + (-n) % 5) // 5),
            )
            result = min([coin2, coin3, coin5, coin1])
            self.dc[n] = result
            return result

    def solve(self):
        return self.coin(self.n)


# x = Solver(11, 1, 2, 4, 8).solve()
# x = Solver(29384293847243,454353412,332423423,934923490,1).solve()
# print(x)

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

for n, a, b, c, d in q:
    answer = Solver(n, a, b, c, d).solve()
    print(answer)

Submission status: Accepted

Solution code:
T=int(input())

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

    M={0:0,1:D}
    S={2:A,3:B,5:C}
    
    def f(N):
        if N in M:
            return M[N]
        
        R=D*N
        for k in S:
            p,q=N//k*k,(N+k-1)//k*k
            R=min(R,
                  D*abs(N-p)+S[k]+f(p//k),
                  D*abs(N-q)+S[k]+f(q//k)
                  )

        M[N]=R
        return R

    X.append(f(N))
print("\n".join(map(str,X)))

Submission status: Accepted

Solution code:
T=int(input())

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

    M={0:0,1:D}
    S={2:A,3:B,5:C}
    
    def f(N):
        if N in M:
            return M[N]
        
        R=D*N
        for k in S:
            p,q=N//k*k,(N+k-1)//k*k
            R=min(R,
                  D*abs(N-p)+S[k]+f(p//k),
                  D*abs(N-q)+S[k]+f(q//k)
                  )

        M[N]=R
        return R

    X.append(f(N))
print("\n".join(map(str,X)))

Submission status: Accepted

Solution code:
import math, collections, heapq
T = int(input())


def solve(N, A, B, C, D):
    dp = collections.defaultdict(lambda: float('inf'))
    dp[0] = 0
    dp[1] = D

    def calc(x):
        if x in dp:
            return dp[x]
        cand = []
        q, r = divmod(x, 2)
        if r == 1:
            cand += [calc(x // 2) + min(A + D, D * (x - x // 2))]
            cand += [calc(x // 2 + 1) + min(A + D, D * (x - x // 2 - 1))]
        else:
            cand += [calc(x // 2) + min(A, D * (x - x // 2))]
        q, r = divmod(x, 3)
        if r < 2:
            cand += [calc(x // 3) + min(B + D * r, D * (x - x // 3))]
        else:
            cand += [calc(x // 3 + 1) + min(B + D, D * (x - x // 3 - 1))]
        q, r = divmod(x, 5)
        if r < 3:
            cand += [calc(x // 5) + min(C + D * r, D * (x - x // 5))]
        else:
            cand += [
                calc(x // 5 + 1) + min(C + D * (5 - r), D * (x - x // 5 - 1))
            ]
        dp[x] = min(cand)
        return dp[x]

    print(calc(N))


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
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())))

Submission status: Accepted

Solution code:
# coding: utf-8
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())))

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
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):
            # base case
            if k == 0:
                return 0
            if k == 1:
                return d
            # recursion
            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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
        # print(now)
        # print(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))
                    # print(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(now,lst,coin)
    print(coin[0])

Submission status: Accepted

Solution code:
# 解説PDF読んで解説放送見てAC

# 逆から操作を考える（終点のNから考える）
# スカスカDP。なので配列を作らずに辞書で管理する必要がある

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  # 1減らすのが常に最善

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from heapq import heappop, heappush

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
# INF = sys.maxsize
INF = 10 ** 27 + 1
# INF = float("inf")


def dp(*x):  # debugprint
    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):
        # dp("put: n,c", 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
        # dp("visit: n", n, cost)

        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":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()