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: Time Limit Exceeded

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def __str__(self):
        return  str(self.edges)
 
    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)

show_flg=False
show_flg=True
ans=0


T=I()
for _ in range(T):
    n,a,b,c,d=LI()
    dc=defaultdict(int)
    dc[0]=inf
    q=[(n,0)]
    while q:
        cur,p=q.pop()
        if cur%5>2:
            if 1+cur//5 not in dc:
                q.append((1+cur//5,p+c+d*(5-cur%5)))
                dc[1+cur//5]=p+c+d*(5-cur%5)
            else:
                if dc[1+cur//5]>p+c+d*(5-cur%5):
                    q.append((1+cur//5,p+c+d*(5-cur%5)))
        else:
            if cur//5 not in dc:
                q.append((cur//5,p+c+d*(cur%5)))
                dc[cur//5]=p+c+d*(cur%5)
            else:
                if dc[cur//5]>p+c+d*(cur%5):
                    q.append((cur//5,p+c+d*(cur%5)))
        
        if cur%3>1:
            if 1+cur//3 not in dc:
                q.append((1+cur//3,p+b+d*(3-cur%3)))
                dc[1+cur//3]=p+b+d*(3-cur%3)
            else:
                if dc[1+cur//3]>p+b+d*(3-cur%3):
                    q.append((1+cur//3,p+b+d*(3-cur%3)))
        else:
            if cur//3 not in dc:
                q.append((cur//3,p+b+d*(cur%3)))
                dc[cur//3]=p+b+d*(cur%3)
            else:
                if dc[cur//3]>p+b+d*(cur%3):
                    q.append((cur//3,p+b+d*(cur%3)))
        

        if 1+cur//2 not in dc:
            q.append((1+cur//2,p+a+d*(cur%2)))  
            dc[1+cur//2]=p+a+d*(2-cur%2)
        else:
            if dc[1+cur//2]>p+a+d*(cur%2):
                q.append((1+cur//2,p+a+d*(cur%2)))

        if cur//2 not in dc:
            q.append((cur//2,p+a+d*(cur%2)))
            dc[cur//2]=p+a+d*(cur%2)
        else:
            if dc[cur//2]>p+a+d*(cur%2):
                q.append((cur//2,p+a+d*(cur%2)))
        
        
        
        dc[0]=min(dc[0],p+d*cur)
        
    print(dc[0])

Submission status: Time Limit Exceeded

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

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

    def dfs(m, cost):
        if m not in memo or memo[m] > cost:
            memo[m] = cost
            memo[0] = min(memo[0], cost + m * d)

            if m > 0:
                dfs(m // 2, cost + (m % 2) * d + a)
                dfs(m // 3, cost + (m % 3) * d + b)
                dfs(m // 5, cost + (m % 5) * d + c)

                dfs((m + (2 - m % 2) % 2) // 2, cost + (2 - m % 2) % 2 * d + a)
                dfs((m + (3 - m % 3) % 3) // 3, cost + (3 - m % 3) % 3 * d + b)
                dfs((m + (5 - m % 5) % 5) // 5, cost + (5 - m % 5) % 5 * d + c)

    dfs(n, 0)
    print(memo[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
#	ans = 10**20
#	for i in range(61):
#		for j in range(39):
#			if pow(2, i) * pow(3, j) > 10**19:
#				continue
#			for k in range(27):
#				if pow(2, i) * pow(3, j) * pow(5, k) > 10**19:
#					continue
#				for l in range(1, 6):
#					g = abs(n - l * pow(2, i) * pow(3, j) * pow(5, k))
#					res = a*i + b*j + c*k + (g+l) * d
#					ans = min(ans, res)
#	print(ans)
	dp = dict()
	dp[n] = 0

	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	def dfs(x):
		if x == 0:
			return
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add((x+1)//2, v):
				dfs((x+1)//2)

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				dfs(x//3+1)

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				dfs(x//5+1)
		return
	dfs(n)
	print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
#	ans = 10**20
#	for i in range(61):
#		for j in range(39):
#			if pow(2, i) * pow(3, j) > 10**19:
#				continue
#			for k in range(27):
#				if pow(2, i) * pow(3, j) * pow(5, k) > 10**19:
#					continue
#				for l in range(1, 6):
#					g = abs(n - l * pow(2, i) * pow(3, j) * pow(5, k))
#					res = a*i + b*j + c*k + (g+l) * d
#					ans = min(ans, res)
#	print(ans)
	dp = dict()
	dp[n] = 0

	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	def dfs(x):
		if x == 0:
			return
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add((x+1)//2, v):
				dfs((x+1)//2)

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				dfs(x//3+1)

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//5 + 1)) + dp[x]
			if add(x//5+1, v):
				dfs(x//5+1)
		return
	dfs(n)
	print(dp[0])

Submission status: Time Limit Exceeded

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

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

    def dfs(m, cost):
        if m not in memo or memo[m] > cost:
            memo[m] = cost
            memo[0] = min(memo[0], cost + m * d)

            if m > 0:
                dfs(m // 2, cost + (m % 2) * d + a)
                dfs(m // 3, cost + (m % 3) * d + b)
                dfs(m // 5, cost + (m % 5) * d + c)

                dfs((m + (2 - m % 2)) // 2, cost + (2 - m % 2) * d + a)
                dfs((m + (3 - m % 3)) // 3, cost + (3 - m % 3) * d + b)
                dfs((m + (5 - m % 5)) // 5, cost + (5 - m % 5) * d + c)

    dfs(n, 0)
    print(memo[0])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)

# def dfs(t,ans):
#     global a,b,c,d fin
#     if t % 5 == 0:
#         if c > 4*t//5 * d:
#             fin = min(fin,ans+4*t//5*d)
#         else:
#             dfs(t//5,ans+c)
#     if t % 3 == 0:
#         if b > 2*t//3 * d:
#             fin = min(fin,ans+2*t//3*d)
#         else:
#             dfs(t//3,ans+b)
#     if t % 2 == 0:
#         if a > t//2 * d:
#             fin = min(fin,ans+t//2*d)
#         else:
#             dfs(t//2,ans+a)
def solve(t,ans):
    global a,b,c,d,fin,al,dic1
    # print(t)
    dic1[t] = ans
    if t < 5:
        if t==1:
            fin = min(fin,ans+d)
        elif t == 2:
            fin = min(fin,ans+2*d,ans+a+d,)
        elif t == 3:
            fin = min(fin,ans+3*d,ans+b+d,ans+a+2*d)
        else:
            fin = min(fin,ans+2*d+c,ans+4*d,ans+2*d+b,ans+2*a+d,ans+a+2*d)
    else:
        fb,fc = 1,1
        if t % 5 == 0:
            fc = 0
            if c > 4*t//5 * d:
                fin = min(fin,ans+t*d)
            else:
                if t//5 not in dic1:
                    solve(t//5,ans+c)
                elif dic1[t//5] > ans+c:
                    solve(t//5,ans+c)
        if t % 3 == 0:
            fb = 0
            if b > 2*t//3 * d:
                fin = min(fin,ans+t*d)
            else:
                if t//3 not in dic1:
                    solve(t//3,ans+b)
                elif dic1[t//3] > ans+b:
                    solve(t//3,ans+b)

        if t % 2 == 0:
            if a > t//2 * d:
                fin = min(fin,ans+t*d)
            else:
                if t//2 not in dic1:
                    solve(t//2,ans+a)
                elif dic1[t//2] > ans+a:
                    solve(t//2,ans+a)
  
        for i in al:
            u = t+i
            ans_temp = ans + d*abs(i)
            if u % 5 == 0 and fc == 1:
                fc = 0
                if c > 4*u//5 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//5 not in dic1:
                        solve(u//5,ans_temp+c)
                    elif dic1[u//5] > ans_temp+c:
                        solve(u//5,ans_temp+c)
            if u % 3 == 0 and fb == 1:
                fb = 0
                if b > 2*u//3 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//3 not in dic1:
                        solve(u//3,ans_temp+b)
                    elif dic1[u//3] > ans_temp+b:
                        solve(u//3,ans_temp+b)

            if u % 2 == 0:
                if a > u//2 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//2 not in dic1:
                        solve(u//2,ans_temp+a)
                    elif dic1[u//2] > ans_temp+a:
                        solve(u//2,ans_temp+a)
        # while fa or fb or fc:
        #     u = t+cnt
        #     ans_temp = ans + d*abs(i)
        #     if u % 5 == 0:
        #         if c > 4*u//5 * d:
        #             fin = min(fin,ans_temp+u*d)
        #         else:
        #             solve(u//5,ans_temp+c)
        #     if u % 3 == 0:
        #         if b > 2*u//3 * d:
        #             fin = min(fin,ans_temp+u*d)
        #         else:
        #             solve(u//3,ans_temp+b)
        #     if u % 2 == 0:
        #         if a > u//2 * d:
        #             fin = min(fin,ans_temp+u*d)
        #         else:
        #             solve(u//2,ans_temp+a)
            # if u == 1:
            #     fin = min(fin,ans_temp+d)
t = int(input())
al = [1,-1,2,-2]


for i in range(t):
    n,a,b,c,d = map(int,input().split())
    fin = 10**30
    dic1 = {}
    solve(n,0)
    print(fin)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop
from collections import defaultdict, deque
sys.setrecursionlimit(10**9)


def solve(n, a, b, c, d):
    MAX = n * max(a, b, c, d) + 1
    memo = defaultdict(lambda: MAX)

    def dfs(m, cost):
        if memo[m] <= cost:
            return
        memo[m] = cost

        if m > 0:
            dfs(m // 2, cost + (m % 2) * d + a)
            dfs(m // 3, cost + (m % 3) * d + b)
            dfs(m // 5, cost + (m % 5) * d + c)

            dfs((m + (2 - m % 2)) // 2, cost + (2 - m % 2) * d + a)
            dfs((m + (3 - m % 3)) // 3, cost + (3 - m % 3) * d + b)
            dfs((m + (5 - m % 5)) // 5, cost + (5 - m % 5) * d + c)

            dfs(0, cost + m * d)

    dfs(n, 0)
    return memo[0]


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

Submission status: Time Limit Exceeded

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

def solve(t,ans):
    global a,b,c,d,fin,al,dic1
    if t < 5:
        if t==1:
            fin = min(fin,ans+d)
        elif t == 2:
            fin = min(fin,ans+2*d,ans+a+d,)
        elif t == 3:
            fin = min(fin,ans+3*d,ans+b+d,ans+a+2*d)
        else:
            fin = min(fin,ans+2*d+c,ans+4*d,ans+2*d+b,ans+2*a+d,ans+a+2*d)
    else:
        for i in al:
            u = t+i
            ans_temp = ans + d*abs(i)
            if u % 5 == 0:
                if c > 4*u//5 * d:
                    if u//5 not in dic1:
                        solve(u//5,ans_temp+4*u//5 * d)
                        dic1[u//5] = ans_temp+4*u//5 * d
                    elif dic1[u//5] > ans_temp+4*u//5 * d:
                        solve(u//5,ans_temp+4*u//5 * d)
                        dic1[u//5] = ans_temp+4*u//5 * d
                else:
                    if u//5 not in dic1:
                        solve(u//5,ans_temp+c)
                        dic1[u//5] = ans_temp+c
                    elif dic1[u//5] > ans_temp+c:
                        solve(u//5,ans_temp+c)
                        dic1[u//5] = ans_temp+c
            if u % 3 == 0 and -2 < i < 2:
                if b > 2*u//3 * d:
                    if u//3 not in dic1:
                        solve(u//3,ans_temp+2*u//3 * d)
                        dic1[u//3] = ans_temp+2*u//3 * d
                    elif dic1[u//3] > ans_temp+2*u//3 * d:
                        solve(u//3,ans_temp+2*u//3 * d)
                        dic1[u//3] = ans_temp+2*u//3 * d
                else:
                    if u//3 not in dic1:
                        solve(u//3,ans_temp+b)
                        dic1[u//3] = ans_temp+b
                    elif dic1[u//3] > ans_temp+b:
                        solve(u//3,ans_temp+b)
                        dic1[u//3] = ans_temp+b

            if u % 2 == 0 and -2 < i < 2:
                if a > u//2 * d:
                    if u//2 not in dic1:
                        solve(u//2,ans_temp+u//2 * d)
                        dic1[u//2] = ans_temp+u//2 * d
                    elif dic1[u//2] > ans_temp+u//2 * d:
                        solve(u//2,ans_temp+u//2 * d)
                        dic1[u//2] = ans_temp+u//2 * d
                else:
                    if u//2 not in dic1:
                        solve(u//2,ans_temp+a)
                        dic1[u//2] = ans_temp+a
                    elif dic1[u//2] > ans_temp+a:
                        solve(u//2,ans_temp+a)
                        dic1[u//2] = ans_temp+a

t = int(input())
al = [0,-1,1,-2,2]

for i in range(t):
    n,a,b,c,d = map(int,input().split())
    fin = 10**30
    dic1 = {}
    solve(n,0)
    print(fin)

Submission status: Time Limit Exceeded

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

def solve(t,ans):
    global a,b,c,d,fin,al,dic1
    if t < 5:
        if t==1:
            fin = min(fin,ans+d)
        elif t == 2:
            fin = min(fin,ans+2*d,ans+a+d,)
        elif t == 3:
            fin = min(fin,ans+3*d,ans+b+d,ans+a+2*d)
        else:
            fin = min(fin,ans+2*d+c,ans+4*d,ans+2*d+b,ans+2*a+d,ans+a+2*d)
    else:
        for i in al:
            u = t+i
            ans_temp = ans + d*abs(i)
            if u % 5 == 0:
                if c > 4*u//5 * d:
                    if u//5 not in dic1:
                        solve(u//5,ans_temp+4*u//5 * d)
                        dic1[u//5] = ans_temp+4*u//5 * d
                    elif dic1[u//5] > ans_temp+4*u//5 * d:
                        solve(u//5,ans_temp+4*u//5 * d)
                        dic1[u//5] = ans_temp+4*u//5 * d
                else:
                    if u//5 not in dic1:
                        solve(u//5,ans_temp+c)
                        dic1[u//5] = ans_temp+c
                    elif dic1[u//5] > ans_temp+c:
                        solve(u//5,ans_temp+c)
                        dic1[u//5] = ans_temp+c
            if u % 3 == 0:
                if b > 2*u//3 * d:
                    if u//3 not in dic1:
                        solve(u//3,ans_temp+2*u//3 * d)
                        dic1[u//3] = ans_temp+2*u//3 * d
                    elif dic1[u//3] > ans_temp+2*u//3 * d:
                        solve(u//3,ans_temp+2*u//3 * d)
                        dic1[u//3] = ans_temp+2*u//3 * d
                else:
                    if u//3 not in dic1:
                        solve(u//3,ans_temp+b)
                        dic1[u//3] = ans_temp+b
                    elif dic1[u//3] > ans_temp+b:
                        solve(u//3,ans_temp+b)
                        dic1[u//3] = ans_temp+b

            if u % 2 == 0 and -2 < i < 2:
                if a > u//2 * d:
                    if u//2 not in dic1:
                        solve(u//2,ans_temp+u//2 * d)
                        dic1[u//2] = ans_temp+u//2 * d
                    elif dic1[u//2] > ans_temp+u//2 * d:
                        solve(u//2,ans_temp+u//2 * d)
                        dic1[u//2] = ans_temp+u//2 * d
                else:
                    if u//2 not in dic1:
                        solve(u//2,ans_temp+a)
                        dic1[u//2] = ans_temp+a
                    elif dic1[u//2] > ans_temp+a:
                        solve(u//2,ans_temp+a)
                        dic1[u//2] = ans_temp+a

t = int(input())
al = [0,-1,1,-2,2]

for i in range(t):
    n,a,b,c,d = map(int,input().split())
    fin = 10**30
    dic1 = {}
    solve(n,0)
    print(fin)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
t = int(input())

def bfs(cur, cost, a, b, c, d, target):
    memo = {0: float('inf')}
    stack = deque([(cur, cost)])
    while stack:
        cur, cost = stack.popleft()
        if cur in memo and memo[cur] <= cost:
            continue
        if cur > 2 * target:
            continue
        if cur < 0:
            continue
        memo[cur] = cost
        memo[0] = min(memo[0], cost + cur * d)
        stack.append((cur//5, cost + c + (cur % 5) * d))
        stack.append((cur//5 + 1, cost + c + (5 - cur % 5) * d))
        stack.append((cur//3, cost + b + (cur % 3) * d))
        stack.append((cur//3 + 1, cost + b + (3 - cur % 3) * d))
        stack.append((cur//2, cost + a + (cur % 2) * d))
        stack.append((cur//2 + 1, cost + a + (2 - cur % 2) * d))

    return memo[0]

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
t = int(input())

def bfs(cur, cost, a, b, c, d, target):
    memo = {0: float('inf')}
    stack = deque([(cur, cost)])
    while stack:
        cur, cost = stack.pop()
        if cur in memo and memo[cur] <= cost:
            continue
        if cur > 2 * target:
            continue
        if cur < 0:
            continue
        memo[cur] = cost
        memo[0] = min(memo[0], cost + cur * d)
        stack.append((cur//5, cost + c + (cur % 5) * d))
        stack.append((cur//5 + 1, cost + c + (5 - cur % 5) * d))
        stack.append((cur//3, cost + b + (cur % 3) * d))
        stack.append((cur//3 + 1, cost + b + (3 - cur % 3) * d))
        stack.append((cur//2, cost + a + (cur % 2) * d))
        stack.append((cur//2 + 1, cost + a + (2 - cur % 2) * d))

    return memo[0]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
#	ans = 10**20
#	for i in range(61):
#		for j in range(39):
#			if pow(2, i) * pow(3, j) > 10**19:
#				continue
#			for k in range(27):
#				if pow(2, i) * pow(3, j) * pow(5, k) > 10**19:
#					continue
#				for l in range(1, 6):
#					g = abs(n - l * pow(2, i) * pow(3, j) * pow(5, k))
#					res = a*i + b*j + c*k + (g+l) * d
#					ans = min(ans, res)
#	print(ans)
	dp = dict()
	dp[n] = 0

	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	def dfs(x):
		if x == 0:
			return
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add((x+1)//2, v):
				dfs((x+1)//2)

		if x%3 == 0:
			v = min(b, d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				dfs(x//3+1)

		if x%5 == 0:
			v = min(c, d*4*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//4)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//4 + 1)) + dp[x]
			if add(x//5+1, v):
				dfs(x//5+1)
		return
	dfs(n)
	print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


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 = sorted([(a, 2), (b, 3), (c, 5)],
                     key=lambda x: x[1]//x[0], reverse=True)
        ans = n*d
        stack = [(n, d)]  # remaining, cost
        while stack:
            rem, cost = stack.pop()
            if rem <= 1:
                ans = min(ans, cost)
                continue
            for y, x in ABC:
                if cost+y < ans:
                    stack.append((rem//x, (rem % x)*d+cost+y))
                    stack.append((-(-rem//x), (-rem % x)*d+cost+y))

        ret.append(str(ans))

    return '\n'.join(ret)


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

Submission status: Time Limit Exceeded

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

def solve(t,ans):
    global a,b,c,d,fin,al,dic1
    if t < 5:
        if t==1:
            fin = min(fin,ans+d)
        elif t == 2:
            fin = min(fin,ans+2*d,ans+a+d,)
        elif t == 3:
            fin = min(fin,ans+3*d,ans+b+d,ans+a+2*d)
        else:
            fin = min(fin,ans+2*d+c,ans+4*d,ans+2*d+b,ans+2*a+d,ans+a+2*d)
    else:
        for i in al:
            u = t+i
            ans_temp = ans + d*abs(i)
            if u % 5 == 0:
                if c > 4*u//5 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//5 not in dic1:
                        solve(u//5,ans_temp+c)
                        dic1[u//5] = ans_temp+c
                    elif dic1[u//5] > ans_temp+c:
                        solve(u//5,ans_temp+c)
                        dic1[u//5] = ans_temp+c
            if u % 3 == 0:
                if b > 2*u//3 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//3 not in dic1:
                        solve(u//3,ans_temp+b)
                        dic1[u//3] = ans_temp+b
                    elif dic1[u//3] > ans_temp+b:
                        solve(u//3,ans_temp+b)
                        dic1[u//3] = ans_temp+b

            if u % 2 == 0:
                if a > u//2 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//2 not in dic1:
                        solve(u//2,ans_temp+a)
                        dic1[u//2] = ans_temp+a
                    elif dic1[u//2] > ans_temp+a:
                        solve(u//2,ans_temp+a)
                        dic1[u//2] = ans_temp+a

t = int(input())
al = [0,-1,1,-2,2]

for i in range(t):
    n,a,b,c,d = map(int,input().split())
    fin = 10**30
    dic1 = {}
    solve(n,0)
    print(fin)