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:
from collections import deque,defaultdict
class DFS:
    def __init__(self,n,a,b,c,d):
        self.N = n
        self.A = a
        self.B = b
        self.C = c
        self.D = d
        self.ans = self.N * self.D
        self.Q = deque([[n,0]])
        self.memory = defaultdict(int) # 実績を記録、すでにその値より低いコストでやっていたら除外する
    def dfs(self):
        while self.Q:
#             from IPython.core.debugger import Pdb; Pdb().set_trace()
            num,cost = self.Q.popleft()
            if num == 0:
                self.ans = min(self.ans, cost)
            elif num == 1:
                self.ans = min(self.ans, cost + self.D * num)
            else:
                # 5の倍数に上げて5で割った場合
                temp_num = num//5 + 1
                temp_cost = cost + ((num//5 + 1) * 5 - num) * self.D + self.C
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                
                # 5の倍数に下げて5で割った場合
                temp_num = num//5
                temp_cost = cost + (num - (num//5)*5) * self.D + self.C
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                
                # 3の倍数に上げて3で割った場合
                temp_num = num//3 + 1
                temp_cost = cost + ((num//3 + 1) * 3 - num) * self.D + self.B
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                
                # 3の倍数に下げて3で割った場合
                temp_num = num//3
                temp_cost = cost + (num - (num//3)*3) * self.D + self.B
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                    
                # 2の倍数に上げて2で割った場合
                temp_num = num//2 + 1
                temp_cost = cost + ((num//2 + 1) * 2 - num) * self.D + self.A
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                
                # 2の倍数に下げて2で割った場合
                temp_num = num//2
                temp_cost = cost + (num - (num//2)*2) * self.D + self.A
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                
                # 全て引いた場合
                self.ans = min(self.ans, num*self.D + cost)
                
        return self.ans
T = int(input())
for _ in range(T):
    N,A,B,C,D = map(int,input().split())
    case = DFS(N,A,B,C,D)
    print(case.dfs())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque,defaultdict
class DFS:
    def __init__(self,n,a,b,c,d):
        self.N = n
        self.A = a
        self.B = b
        self.C = c
        self.D = d
        self.ans = self.N * self.D
        self.Q = deque([[n,0]])
        self.memory = defaultdict(int) # 実績を記録、すでにその値より低いコストでやっていたら除外する
    def dfs(self):
        while self.Q:
#             from IPython.core.debugger import Pdb; Pdb().set_trace()
            num,cost = self.Q.popleft()
            if num == 0:
                self.ans = min(self.ans, cost)
            elif num == 1:
                self.ans = min(self.ans, cost + self.D * num)
            else:
                # 5の倍数に上げて5で割った場合
                temp_num = num//5 + 1
                temp_cost = cost + ((num//5 + 1) * 5 - num) * self.D + self.C
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                
                # 5の倍数に下げて5で割った場合
                temp_num = num//5
                temp_cost = cost + (num - (num//5)*5) * self.D + self.C
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                
                # 3の倍数に上げて3で割った場合
                temp_num = num//3 + 1
                temp_cost = cost + ((num//3 + 1) * 3 - num) * self.D + self.B
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                
                # 3の倍数に下げて3で割った場合
                temp_num = num//3
                temp_cost = cost + (num - (num//3)*3) * self.D + self.B
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                    
                # 2の倍数に上げて2で割った場合
                temp_num = num//2 + 1
                temp_cost = cost + ((num//2 + 1) * 2 - num) * self.D + self.A
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                
                # 2の倍数に下げて2で割った場合
                temp_num = num//2
                temp_cost = cost + (num - (num//2)*2) * self.D + self.A
                if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                    self.memory[temp_num] = temp_cost
                    self.Q.appendleft([temp_num,temp_cost])
                
                # 全て引いた場合
                self.ans = min(self.ans, num*self.D + cost)
                
        return self.ans
T = int(input())
for _ in range(T):
    N,A,B,C,D = map(int,input().split())
    case = DFS(N,A,B,C,D)
    print(case.dfs())

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(10**6)


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


    def calc_cost(N, A, B, C, D):


        #@lru_cache(maxsize=None)
        def calc(N):
            if N == 0:
                return 0
            if N == 1:
                return D

            cost = N * D
            
            for T, Tcost in ((2, A), (3, B), (5, C)):
                div, mod = divmod(N, T)

                cost = min(cost, calc(div) + Tcost + mod * D)
                if mod:
                    cost = min(cost, calc(div + 1) + Tcost + (T - mod) * D)

            return cost


        return calc(N)


    for TESTCASE in TESTCASEs:
        total_cost = calc_cost(*TESTCASE)
        print(total_cost)


if __name__ == '__main__':
    main()

sys.exit()

Submission status: Time Limit Exceeded

Solution code:
t=int(input())
for i in range(t):
    coin = 0
    n,a,b,c,d = map(int,input().split())
    a1 = float(a/2)
    b1 = float(b/3)
    c1 = float(c/5)
    coin += d
    q = 1
    f=0
    while f==0:
        if a1 > b1 and a1 > c1:    
            while (n+1)/2 >= 1:
                if n%2==1:
                    coin += d
                    n-=1
                    if n==0:
                        print(coin)
                        f=1
                        break
                n=n/2
                coin += a
        elif b1 > a1 and b1 > c1:
            while (n+2)/3 >= 1:
                if n%3==1:
                    coin += d
                    n-=1
                    if n==0:
                        print(coin)
                        f=1
                        break
                elif n%3==2:
                    coin += d
                    n+=1
                n=n/3
                coin += b

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
    T = int(input())
    ans = [None]*T
    ipt = [list(map(int, input().split())) for _ in range(T)]
    for i in range(T):
        n, a, b, c, d = ipt[i]
        dic = {}
        dic[n] = 0
        hq = [-n]
        heapq.heapify(hq)
        while len(hq) > 0:
            p = heapq.heappop(hq)
            p *= -1
            for x in range(p-5, p+6):
                if x <= 1:
                    continue
                if x%2 == 0:
                    if not x//2 in dic:
                        dic[x//2] = float("inf")
                        heapq.heappush(hq, -1*(x//2))
                    if dic[p]+d*abs(x-p)+a < dic[x//2]:
                        dic[x//2] = dic[p]+d*abs(x-p)+a
                    if dic[p]+d*abs(p-x//2) < dic[x//2]:
                        dic[x//2] = dic[p]+d*abs(p-x//2)
                if x%3 == 0:
                    if not x//3 in dic:
                        dic[x//3] = float("inf")
                        heapq.heappush(hq, -1*(x//3))
                    if dic[p]+d*abs(x-p)+b < dic[x//3]:
                        dic[x//3] = dic[p]+d*abs(x-p)+b
                    if dic[p]+d*abs(p-x//3) < dic[x//3]:
                        dic[x//3] = dic[p]+d*abs(p-x//3)
                if x%5 == 0:
                    if not x//5 in dic:
                        dic[x//5] = float("inf")
                        heapq.heappush(hq, -1*(x//5))
                    if dic[p]+d*abs(x-p)+c < dic[x//5]:
                        dic[x//5] = dic[p]+d*abs(x-p)+c
                    if dic[p]+d*abs(p-x//5) < dic[x//5]:
                        dic[x//5] = dic[p]+d*abs(p-x//5)
        ans[i] = min(n*d, dic[1]+d)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
    T = int(input())
    ans = [None]*T
    for i in range(T):
        n, a, b, c, d = map(int, input().split())
        dic = {}
        dic[n] = 0
        hq = [-n]
        heapq.heapify(hq)
        while len(hq) > 0:
            p = heapq.heappop(hq)
            p *= -1
            for x in range(p-5, p+6):
                if x <= 1:
                    continue
                if x%2 == 0:
                    if not x//2 in dic:
                        dic[x//2] = float("inf")
                        heapq.heappush(hq, -1*(x//2))
                    if dic[p]+d*abs(x-p)+a < dic[x//2]:
                        dic[x//2] = dic[p]+d*abs(x-p)+a
                    if dic[p]+d*abs(p-x//2) < dic[x//2]:
                        dic[x//2] = dic[p]+d*abs(p-x//2)
                if x%3 == 0:
                    if not x//3 in dic:
                        dic[x//3] = float("inf")
                        heapq.heappush(hq, -1*(x//3))
                    if dic[p]+d*abs(x-p)+b < dic[x//3]:
                        dic[x//3] = dic[p]+d*abs(x-p)+b
                    if dic[p]+d*abs(p-x//3) < dic[x//3]:
                        dic[x//3] = dic[p]+d*abs(p-x//3)
                if x%5 == 0:
                    if not x//5 in dic:
                        dic[x//5] = float("inf")
                        heapq.heappush(hq, -1*(x//5))
                    if dic[p]+d*abs(x-p)+c < dic[x//5]:
                        dic[x//5] = dic[p]+d*abs(x-p)+c
                    if dic[p]+d*abs(p-x//5) < dic[x//5]:
                        dic[x//5] = dic[p]+d*abs(p-x//5)
        ans[i] = min(n*d, dic[1]+d)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
    T = int(input())
    ans = [None]*T
    for i in range(T):
        n, a, b, c, d = map(int, input().split())
        dic = {}
        dic[n] = 0
        hq = [-n]
        heapq.heapify(hq)
        while len(hq) > 0:
            p = heapq.heappop(hq)
            p *= -1
            for x in range(p-5, p+6):
                if x <= 1:
                    continue
                if x%2 == 0:
                    if x//2 in dic:
                        dic[x//2] = min(dic[x//2], dic[p]+d*abs(x-p)+a, dic[p]+d*abs(p-x//2))
                    else:
                        dic[x//2] = min(dic[p]+d*abs(x-p)+a, dic[p]+d*abs(p-x//2))
                        heapq.heappush(hq, -1*(x//2))
                if x%3 == 0:
                    if x//3 in dic:
                        dic[x//3] = min(dic[x//3], dic[p]+d*abs(x-p)+b, dic[p]+d*abs(p-x//3))
                    else:
                        dic[x//3] = min(dic[p]+d*abs(x-p)+b, dic[p]+d*abs(p-x//3))
                        heapq.heappush(hq, -1*(x//3))
                if x%5 == 0:
                    if x//5 in dic:
                        dic[x//5] = min(dic[x//5], dic[p]+d*abs(x-p)+c, dic[p]+d*abs(p-x//5))
                    else:
                        dic[x//5] = min(dic[p]+d*abs(x-p)+c, dic[p]+d*abs(p-x//5))
                        heapq.heappush(hq, -1*(x//5))
        ans[i] = min(n*d, dic[1]+d)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor,log
from decimal import *
from heapq import *
import sys
input=sys.stdin.readline
T=int(input())
cases=[list(map(int,input().split())) for _ in range(T)]
getcontext().prec=20
num=0
cnt=0
def main():
    for i in cases:
        l2=[0]*3
        N,l2[0],l2[1],l2[2],D=i
        d = {}
        num=0
        cnt=0
        for j in range(60):         #2の累乗
            for k in range(38):     #3の累乗
                for l in range(26): #5の累乗
                    div=pow(2,j)*pow(3,k)*pow(5,l)
                    x=Decimal(N)/Decimal(div)
                    c=x.to_integral_exact(rounding=ROUND_CEILING)
                    f=x.to_integral_exact(rounding=ROUND_FLOOR)
                    if d.get(c)==None:
                        d[c]=float("inf")
                    if d.get(f)==None:
                        d[f]=float("inf")
        d[N]=0
        #print(d)
        q=[]
        q.append((0,N))
        heapify(q)
        #print(d)
        while len(q)>0:
            dist,u=heappop(q)
            if d[u]<dist: continue
            for j in range(3):
                num=1+pow(2,j)
                cnt=l2[j]
                x = Decimal(u) / Decimal(num)
                v1 = x.to_integral_exact(rounding=ROUND_CEILING)
                v2 = x.to_integral_exact(rounding=ROUND_FLOOR)
                # v1=ceil(u/2)
                # v2=floor(u/2)
                alt1 = d[u] + min(cnt+((num-(u%num))%num)*D,(u-v1)*D)
                alt2 = d[u] + min(cnt+(u%num)*D,(u-v2)*D)
                if d[v1] > alt1:
                    d[v1] = alt1
                    heappush(q, (alt1, v1))
                if d[v2] > alt2:
                    d[v2] = alt2
                    heappush(q, (alt2, v2))
            #print(d)
            #input()
        print(d[0])
        #print(len(d))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor
from decimal import *
import heapq
T=int(input())
cases=[list(map(int,input().split())) for _ in range(T)]
getcontext().prec=20
for i in cases:
    N,A,B,C,D=i
    d = {}
    for i in range(60):         #2の累乗
        for j in range(38):     #3の累乗
            for k in range(26): #5の累乗
                div=pow(2,i)*pow(3,j)*pow(5,k)
                x=Decimal(N)/Decimal(div)
                c=x.to_integral_exact(rounding=ROUND_CEILING)
                f=x.to_integral_exact(rounding=ROUND_FLOOR)
                if d.get(c)==None:
                    d[c]=float("inf")
                if d.get(f)==None:
                    d[f]=float("inf")
    d[N]=0
    #print(d)
    q=[]
    q.append([0,N])
    heapq.heapify(q)
    while len(q)>0:
        dist,u=heapq.heappop(q)
        if d[u]<dist: continue
        for j in range(3):
            if j==0:    #2で割る時を考える
                x=Decimal(u)/Decimal(2)
                v1=x.to_integral_exact(rounding=ROUND_CEILING)
                v2=x.to_integral_exact(rounding=ROUND_FLOOR)
                #v1=ceil(u/2)
                #v2=floor(u/2)
                alt1=d[u]+min(A+(u%2)*D,(u-v1)*D)
                alt2=d[u]+min(A+(u%2)*D,(u-v2)*D)
                if d[v1]>alt1:
                    d[v1]=alt1
                    heapq.heappush(q,[alt1,v1])
                if d[v2]>alt2:
                    d[v2]=alt2
                    heapq.heappush(q,[alt2,v2])
            if j==1:    #3で割る時を考える
                x=Decimal(u)/Decimal(3)
                v1=x.to_integral_exact(rounding=ROUND_CEILING)
                v2=x.to_integral_exact(rounding=ROUND_FLOOR)
                #v1=ceil(u/3)
                #v2=floor(u/3)
                alt1=d[u]+min(B+((3-(u%3))%3)*D,(u-v1)*D)
                alt2=d[u]+min(B+(u%3)*D,(u-v2)*D)
                if d[v1]>alt1:
                    d[v1]=alt1
                    heapq.heappush(q,[alt1,v1])
                if d[v2]>alt2:
                    d[v2]=alt2
                    heapq.heappush(q,[alt2,v2])
            if j==2:    #5で割る時を考える
                x=Decimal(u)/Decimal(5)
                v1=x.to_integral_exact(rounding=ROUND_CEILING)
                v2=x.to_integral_exact(rounding=ROUND_FLOOR)
                #v1=ceil(u/5)
                #v2=floor(u/5)
                alt1=d[u]+min(C+((5-(u%5))%5)*D,(u-v1)*D)
                alt2=d[u]+min(C+(u%5)*D,(u-v2)*D)
                if d[v1]>alt1:
                    d[v1]=alt1
                    heapq.heappush(q,[alt1,v1])
                if d[v2]>alt2:
                    d[v2]=alt2
                    heapq.heappush(q,[alt2,v2])
        #print(d)
        #input()
    print(d[0])
    #print(len(d))

Submission status: Time Limit Exceeded

Solution code:
import math
def dfs(N,A,B,C,D):
    if N in dic: return dic[N]
    if N == 0: return 0
    if N == 1: return D
    mini = D * N
    if N % 2 == 0: mini = min(mini,dfs(N//2,A,B,C,D) + A)
    else: 
        mini=min(dfs(math.ceil(N/2),A,B,C,D) + A + (2-N%2) * D,mini)
        mini=min(dfs(math.floor(N/2),A,B,C,D) + A + (N%2) * D,mini)

    if N % 3 == 0: mini = min(mini,dfs(N//3,A,B,C,D) + B)
    else:
        mini=min(dfs(math.ceil(N/3),A,B,C,D) + B + (3-N%3) * D,mini)
        mini=min(dfs(math.floor(N/3),A,B,C,D) + B + (N%3) * D,mini)

    if N % 5 == 0: mini = min(mini,dfs(N//5,A,B,C,D) + C)
    else:
        mini=min(dfs(math.ceil(N/5),A,B,C,D) + C + (5-N%5) * D,mini)
        mini=min(dfs(math.floor(N/5),A,B,C,D) + C + (N%5) * D,mini)
    
    if mini not in dic:
        dic[N] = mini
    return mini
i = int(input())
for _ in range(i):
    X,A,B,C,D = map(int,input().split())
    global dic
    dic = {}
    print(dfs(X,A,B,C,D))

Submission status: Time Limit Exceeded

Solution code:
import math
def dfs(N,A,B,C,D):
    if N in dic: return dic[N]
    if N == 0: return 0
    if N == 1: return D
    (ret1,ret2,ret3,ret4,ret5,ret6,ret7,ret8,ret9)=[10**25 for _ in range(9)]
    if N % 2 == 0: ret1 = dfs(N//2,A,B,C,D) + A
    else: 
        ret4 = dfs(math.ceil(N/2),A,B,C,D) + A + (2-N%2) * D
        ret5 = dfs(math.floor(N/2),A,B,C,D) + A + (N%2) * D

    if N % 3 == 0: ret2 = dfs(N//3,A,B,C,D) + B
    else:
        ret7 = dfs(math.ceil(N/3),A,B,C,D) + B + (3-N%3) * D
        ret6 = dfs(math.floor(N/3),A,B,C,D) + B + (N%3) * D

    if N % 5 == 0: ret3 = dfs(N//5,A,B,C,D) + C
    else:
        ret8 = dfs(math.ceil(N/5),A,B,C,D) + C + (5-N%5) * D
        ret9 = dfs(math.floor(N/5),A,B,C,D) + C + (N%5) * D
    
    ret = min(ret1,ret2,ret3,ret4,ret5,ret6,ret7,ret8,ret9,D*N)

    if ret not in dic:
        dic[N] = ret
    return ret
i = int(input())
for _ in range(i):
    X,A,B,C,D = map(int,input().split())
    global dic
    dic = {}
    print(dfs(X,A,B,C,D))

Submission status: Time Limit Exceeded

Solution code:
import math
def dfs(N,A,B,C,D):
    if N in dic: return dic[N]
    if N == 0: return 0
    if N == 1: return D
    (ret1,ret2,ret3,ret4,ret5,ret6,ret7,ret8,ret9)=[10**30 for _ in range(9)]
    if N % 2 == 0: ret1 = dfs(N//2,A,B,C,D) + A
    else: 
        ret4 = dfs(math.ceil(N/2),A,B,C,D) + A + (2-N%2) * D
        ret5 = dfs(math.floor(N/2),A,B,C,D) + A + (N%2) * D

    if N % 3 == 0: ret2 = dfs(N//3,A,B,C,D) + B
    else:
        ret7 = dfs(math.ceil(N/3),A,B,C,D) + B + (3-N%3) * D
        ret6 = dfs(math.floor(N/3),A,B,C,D) + B + (N%3) * D

    if N % 5 == 0: ret3 = dfs(N//5,A,B,C,D) + C
    else:
        ret8 = dfs(math.ceil(N/5),A,B,C,D) + C + (5-N%5) * D
        ret9 = dfs(math.floor(N/5),A,B,C,D) + C + (N%5) * D
    
    ret = min(ret1,ret2,ret3,ret4,ret5,ret6,ret7,ret8,ret9,D*N)

    if ret not in dic:
        dic[N] = ret
    return ret
i = int(input())
for _ in range(i):
    X,A,B,C,D = map(int,input().split())
    global dic
    dic = {}
    print(dfs(X,A,B,C,D))

Submission status: Time Limit Exceeded

Solution code:
t=int(input())
def f(x):
	if x<=1:
		return D*x
	ret=D*x

	if x%2==0:
		ret=min(ret,f(x//2)+A)
	else:
		ret=min(ret,f(x//2)+A+D,f(x//2+1)+A+D)
	
	if x%3==0:
		ret=min(ret,f(x//3)+B)
	elif x%3==1:
		ret=min(ret,f(x//3)+B+D)
	else:
		ret=min(ret,f(x//3+1)+B+D)

	if x%5<=2:
		ret=min(ret,f(x//5)+C+D*(x%5))
	else:
		ret=min(ret,f(x//5+1)+C+D*(5-x%5))
	return ret
for _ in range(t):
	n,A,B,C,D=map(int,input().split())
	print(f(n))

Submission status: Time Limit Exceeded

Solution code:
def dfs(n):
    global b,check,d
    #ttfは235、chaはabc
    #2,3,5の場合それぞれ
    for ttf,cha in zip([2,3,5],b):
        #-1ずつしていく場合
        if check[0]>check[n]+n*d:
            check[0]=check[n]+n*d

        #最寄りまで-してく場合
        x1,x2=n//ttf,n%ttf
        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 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)

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:
def dfs(n):
    global b,check,d
    #ttfは235、chaはabc
    for ttf,cha in zip([2,3,5],b):
        #-1ずつしていく場合
        check[0]=min(check[n]+n*d,check[0])

        #最寄りまで-してく場合
        x1,x2=n//ttf,n%ttf
        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 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)

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:
check=dict()
#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 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 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
    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:
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 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 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:
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])

    #最寄りまで-してく場合
    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)

    #最寄りまで+1してく場合
    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,0:N*d}
    dfs(N)
    print(check[0])

Submission status: Time Limit Exceeded

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

check=dict()
N,z,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 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 z
    for i,j in z:
        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}
    z=list(zip([2,3,5],b))
    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 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
    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 check.get(x1) is not None:
            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 check.get(x1) is not None:
            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
    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])