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
input=sys.stdin.readline

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if x1==0:
        return
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Submission status: Time Limit Exceeded

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

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    x1,x2=n//ttf,n%ttf
    x3=x2*d
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x3:
                    check[x1]=check[n]+x3
            else:
                check[x1]=check[n]+x3
        else:
            if x1 in check:
                if check[x1]>check[n]+x3+cha:
                    check[x1]=check[n]+x3+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x3+cha
                dfs(x1)

    x1,x2=n//ttf+1,ttf-n%ttf
    x3=x2*d
    if ttf-x2>x2:
        if x1 in check:
            if check[x1]>check[n]+x3+cha:
                check[x1]=check[n]+x3+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x3+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Submission status: Time Limit Exceeded

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

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x2*d:
                    check[x1]=check[n]+x2*d
            else:
                check[x1]=check[n]+x2*d
        else:
            if x1 in check:
                if check[x1]>check[n]+x2*d+cha:
                    check[x1]=check[n]+x2*d+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)

    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Submission status: Time Limit Exceeded

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

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    check[0]=min(check[n]+n*d,check[0])

    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x2*d:
                    check[x1]=check[n]+x2*d
            else:
                check[x1]=check[n]+x2*d
        else:
            if x1 in check:
                if check[x1]>check[n]+x2*d+cha:
                    check[x1]=check[n]+x2*d+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)

    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d

    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x2*d:
                    check[x1]=check[n]+x2*d
            else:
                check[x1]=check[n]+x2*d
        else:
            if x1 in check:
                if check[x1]>check[n]+x2*d+cha:
                    check[x1]=check[n]+x2*d+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)

    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d

    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x2*d:
                    check[x1]=check[n]+x2*d
            else:
                check[x1]=check[n]+x2*d
        else:
            if x1 in check:
                if check[x1]>check[n]+x2*d+cha:
                    check[x1]=check[n]+x2*d+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)

    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d

    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x2*d:
                    check[x1]=check[n]+x2*d
            else:
                check[x1]=check[n]+x2*d
        else:
            if x1 in check:
                if check[x1]>check[n]+x2*d+cha:
                    check[x1]=check[n]+x2*d+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)

    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if (ttf-n%ttf)>=(n%ttf):
        if n//ttf==0:
            if n//ttf in check:
                if check[n//ttf]>check[n]+(n%ttf)*d:
                    check[n//ttf]=check[n]+(n%ttf)*d
            else:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            if n//ttf in check:
                if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                    check[n//ttf]=check[n]+(n%ttf)*d+cha
                    dfs(n//ttf)
            else:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
    if (ttf-n%ttf)<=(n%ttf):
        if 1+n//ttf in check:
            if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
                check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
                dfs(1+n//ttf)
        else:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Submission status: Time Limit Exceeded

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

@lru_cache(None)
def f(n,a,b,c,d):
  if n==0:return 0
  if n==1:return d
  if n==2:return min(d*2,a+d)
  if n==3:return min(d*3,d+a+d,b+d)
  if n==4:return min(d*4,a+a+d,d+b+d,d+c+d)
  if n==5:return min(d*5,d+a+a+d,d+d+b+d,d+a+b+d,c+d)
  if n==6:return min(d*6,a+b+d,a+d+a+d,b+d+b+d,d+c+d)
  # print(n,a,b,c,d)
  p=n*d
  for i in range(-10, 11):
    nn=n+i
    if nn<0:continue
    if nn%2==0and nn//2<n:p=min(p,f(nn//2,a,b,c,d)+abs(i)*d+a)
    if nn%3==0and nn//3<n:p=min(p,f(nn//3,a,b,c,d)+abs(i)*d+b)
    if nn%5==0and nn//5<n:p=min(p,f(nn//5,a,b,c,d)+abs(i)*d+c)
  return p

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
INF = 10**18
t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    memo = defaultdict(lambda: INF)

    def dfs(n, cost):

        if memo[n] <= cost:
            return 0

        memo[n] = cost
        if n == 0:
            return 0

        dfs(0, cost+n*d)

        r = n % 2
        dfs((n-r)//2, cost+a+r*d)
        if r != 0:
            dfs((n+(2-r))//2, cost+a+(2-r)*d)

        r = n % 3
        dfs((n-r)//3, cost+b+r*d)
        if r != 0:
            dfs((n+(3-r))//3, cost+b+(3-r)*d)

        r = n % 5
        dfs((n-r)//5, cost+c+r*d)
        if r != 0:
            dfs((n+(5-r))//5, cost+c+(5-r)*d)
            
    dfs(n, 0)
    print(memo[0])

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

T = int(input())

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

    def dist(n):
        if n == 0:
            return 0
        if n == 1:
            return D

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

        return ret

    print(dist(N))

Submission status: Time Limit Exceeded

Solution code:

#from collections import defaultdict
#from pprint import pprint
#from collections import deque
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
#import numpy as np
#import math
# = map(int,input().split())

# = list(map(int,input().split()))

# = [list(map(int,input().split())) for _ in range(XXXX)]

def func(i):
    if i == 0:
        return 0
    elif i == 1:
        return d
    elif i in memo:
        return memo[i]
    else:
        min_val = int(min(
            d*i,
            d*abs(i-i//2*2) + a + func(i//2),
            d*abs(i-(i+1)//2*2) + a + func((i+1)/2),
            d*abs(i-i//3*3) + b + func(i//3),
            d*abs(i-(i+2)//3*3) + b + func((i+2)//3),
            d*abs(i-i//5*5) + c + func(i//5),
            d*abs(i-(i+4)//5*5) + c + func((i+4)//5)
        ))

    memo[i] = min_val
    return min_val



t = int(input())

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


for i in range(t):
    n = nabcd[i][0]
    a = nabcd[i][1]
    b = nabcd[i][2]
    c = nabcd[i][3]
    d = nabcd[i][4]

    memo = {}


    print(func(n))
    #print(memo)

Submission status: Time Limit Exceeded

Solution code:
import heapq
t = int(input())

def ka(cost,num,w):
    #print(w,cost,num)
    coun = 0
    for i in range(len(w)):
        if (w[i][1] == num):
            if (cost < w[i][0]):
                w.pop(i)
                heapq.heappush(w,(cost,num))
                #used.append((cost,num))
                coun += 1
                break
            else:
                coun += 1
                break
    if (coun == 0):
        heapq.heappush(w,(cost,num))
        #used.append((cost,num))
        
for i in range(t):
    n,a,b,c,d = map(int, input().split())
    w = [(0,n)]
    
    ans = float("inf")
    used = []
    while True:
        #print(w)
        p,q = heapq.heappop(w)
        #print(p,q)
        if (q == 0):
            print(min(ans,p))
            break
        if (q%5==0):
            ka(p+c,q//5,w)
        else:
            for i in range(-4,5):
                if (q+i<0):
                    continue
                if ((q+i)%5==0):
                    ka(p+d*abs(i),q+i,w)
        if (q%3==0):
            ka(p+b,q//3,w)
        else:
            for i in range(-2,3):
                if (q+i<0):
                    continue
                if ((q+i)%3==0):
                    ka(p+d*abs(i),q+i,w)
        if (q%2==0):
            ka(p+a,q//2,w)
        else:
            for i in range(-1,2):
                if (q+i<0):
                    continue
                if ((q+i)%2==0):
                    ka(p+d*abs(i),q+i,w)
        ans = min(ans,p+q*d)

Submission status: Time Limit Exceeded

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

def vc(value,cost,pt):
    if value==1:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost+d)     
        else:
            vcs[0]=cost+d     
        return value,cost+d
    elif value<=0:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost)     
        else:
            vcs[0]=cost
        return cost
#    elif value==1:
#        cost=cost+d
#        return value,cost        
    
    if pt==1:
        v=value//2
        cost=cost+a+(value-v*2)*d
    elif pt==2:
        v=value//3
        cost=cost+b+(value-v*3)*d
    elif pt==3:
        v=value//5
        cost=cost+c+(value-v*5)*d
    elif pt==4:
        v=value//2+1
        cost=cost+a+(v*2-value)*d
    elif pt==5:
        v=value//3+1
        cost=cost+b+(v*3-value)*d
    elif pt==6:
        v=value//5+1
        cost=cost+c+(v*5-value)*d
    elif pt==7:
        v=0
        cost=cost+(value-v)*d
    return v,cost
    
def dfc(value,cost):
#    print(value,cost)
    if value==1:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost+d)     
        else:
            vcs[0]=cost+d     
        return cost+d
    elif value<=0:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost)     
        else:
            vcs[0]=cost
        return cost

    for i in range(7):
        value1,cost1=vc(value,cost,i+1)
#        print(i+1,":",value1,cost1)
        if value1 in vcs.keys():
            if vcs[value1]<=cost1:
                continue
            else:
                vcs[value1]=min(vcs[value1],cost1)     
                dfc(value1,cost1)
        else:
            vcs[value1]=cost1     
            dfc(value1,cost1)
        
'''          
    value1,cost1=vc(value,cost,1)
    print("1:",value1,cost1)
    if value1 in vcs.keys():
        vcs[value1]=min(vcs[value1],cost1)     
    else:
        vcs[value1]=cost1     
        dfc(value1,cost1)

    value2,cost2=vc(value,cost,2)
    print("2:",value2,cost2)
    if value2 in vcs.keys():
        vcs[value2]=min(vcs[value2],cost2)        
    else:
        vcs[value2]=cost2     
        dfc(value2,cost2)

    value3,cost3=vc(value,cost,3)
    print("3:",value3,cost3)
    if value3 in vcs.keys():
        vcs[value3]=min(vcs[value3],cost3)        
    else:
        vcs[value3]=cost3     
        dfc(value3,cost3)

    value4,cost4=vc(value,cost,4)
    print("4:",value4,cost4)
    if value4 in vcs.keys():
        vcs[value4]=min(vcs[value4],cost4)        
    else:
        vcs[value4]=cost4     
        dfc(value4,cost4)

    value5,cost5=vc(value,cost,5)
    print("5:",value5,cost5)
    if value5 in vcs.keys():
        vcs[value5]=min(vcs[value5],cost5)        
    else:
        vcs[value5]=cost5     
        dfc(value5,cost5)

    value6,cost6=vc(value,cost,6)
    print("6:",value6,cost6)
    if value6 in vcs.keys():
        vcs[value6]=min(vcs[value6],cost6)        
    else:
        vcs[value6]=cost6     
        dfc(value6,cost6)
    
    value7,cost7=vc(value,cost,7)
    print("7:",value7,cost7)
    if value7 in vcs.keys():
        vcs[value7]=min(vcs[value7],cost7)        
    else:
        vcs[value7]=cost7     
        dfc(value7,cost7)
'''

t=int(input())
#t=1
for i in range(t):
    n,a,b,c,d=map(int,input().split())
#    n,a,b,c,d=11,1,2,4,8
#    n,a,b,c,d=11,1,2,2,8
#    n,a,b,c,d=32, 10, 8, 5, 4
#    n,a,b,c,d=29384293847243, 454353412, 332423423, 934923490, 1
#    n,a,b,c,d=900000000000000000, 332423423, 454353412, 934923490, 987654321
    
    vcs=dict()

    cost=dfc(n,0)

#    print(cost)
#    print(min(vcs.items()))
    print(vcs[0])

Submission status: Time Limit Exceeded

Solution code:
import heapq
t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    # x to lowest coin
    cheapest = set()
    # (coin, x)
    search = [(d, 1, 0, 0, 0, 0)]
    first = True

    while 1:
        coin, x, add, f2, f3, f5 = heapq.heappop(search)
#         print(f'coin: {coin}, x: {x}, add: {add}, f2: {f2}, f3: {f3}, f5: {f5}')
        if (x > 1 or first) and x not in cheapest:
            first = False
            if x == n:
                print(coin)
                break
            cheapest.add(x)

            if add >=0:
                heapq.heappush(search, (coin + d, x + 1, add + 1, 0, 0, 0))
            if x - 1 > 1 and add <= 0:
                heapq.heappush(search, (coin + d, x - 1, add - 1, 0, 0, 0))
                
            if 2 * x <= 2 * n:
                heapq.heappush(search, (coin + a, 2 * x, 0, f2 + 1, f3, f5))
            if 3 * x <= 2 * n and f2 == 0:
                heapq.heappush(search, (coin + b, 3 * x, 0, f2, f3 + 1, f5))
            if 5 * x <= 2 * n and f2 == 0 and f3 == 0:
                heapq.heappush(search, (coin + c, 5 * x, 0, f2, f3, f5 + 1))

Submission status: Time Limit Exceeded

Solution code:
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc

def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check[0]) if 0 in check else check[n]+n*d
    if n//ttf==0:
        check[n//ttf]=min(check[n]+(n%ttf)*d,check[n//ttf]) if n//ttf in check else check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Submission status: Time Limit Exceeded

Solution code:
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**12
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Submission status: Time Limit Exceeded

Solution code:
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**13
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Submission status: Time Limit Exceeded

Solution code:
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**15
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Submission status: Time Limit Exceeded

Solution code:
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**(20)
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Submission status: Time Limit Exceeded

Solution code:
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**(30)
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Submission status: Time Limit Exceeded

Solution code:
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**(40)
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Submission status: Time Limit Exceeded

Solution code:
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**(50)
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0,inf))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,inf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

Submission status: Time Limit Exceeded

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

def dist(n,A,B,C,D):
    if n == 0:
        return 0
    if n == 1:
        return D

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

for j in range(T):
    print(dist(N[j],A[j],B[j],C[j],D[j]))

Submission status: Time Limit Exceeded

Solution code:
import heapq
t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    # x to lowest coin
    cheapest = dict()
    # (coin, x)
    search = [(d, 1)]
    first = True

    while 1:
        coin, x = heapq.heappop(search)

        if (x > 1 or first) and x not in cheapest:
            first = False
            if x == n:
                print(coin)
                break
            cheapest[x] = coin

            heapq.heappush(search, (coin + a, 2 * x))
            heapq.heappush(search, (coin + b, 3 * x))
            heapq.heappush(search, (coin + c, 5 * x))
            heapq.heappush(search, (coin + d, x + 1))
            if x - 1 > 1:
                heapq.heappush(search, (coin + d, x - 1))