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: Wrong Answer

Solution code:
T=int(input())
NABCD = [list(map(int, input().split())) for i in range(T)]
print("うーん…わかんないっ!w")
#ウイイイイイイイッッッッス。どうも、Kunitakeでーす。
#まぁ今日はAGC044、当日ですけども。
#えーとですね、まぁ提出場所の、えーAtCoderに行ってきたんですけども、ただいまの時刻は22時を回りました。
#はい、ちょっと遅れて来たんですけどもね。えー21時ちょっとすぎくらいに、えーAtCoderに来たんですけども。
#ほんでーまぁTwitter上の数々の撤退表明を見た後に行ったんですけども。スィー。
#ほんでーかれこれまぁ1時間くらい、えー考えたんですけども解法は何一つ思いつきませんでした。ガチャ。
#何一つ思いつくほどことなかったですぅ。残念ながら。はい。

Submission status: Wrong Answer

Solution code:
print(2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
T = int(input())

def calc_min_coin(N, A, B, C, D):
    ans = D * N
    for i in range(61):
        for j in range(39):
            for k in range(27):
                multi_num = (2 ** i) * (3 ** j) * (5 ** k)
                if multi_num > 2 * N:
                    break

                bef_D_num, af_D_num = divmod(N,  multi_num)
                if N % multi_num > multi_num // 2:
                    bef_D_num += 1
                    af_D_num = multi_num - af_D_num
                temp_ans = D * (bef_D_num + af_D_num) + A * i + B * j + C * k
                ans = min(ans, temp_ans)
    return ans

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

Submission status: Wrong Answer

Solution code:
t=int(input())
a=[list(map(int,input().split())) for i in range(t)]
count=1
ans=0
hantei=10**18
for i in range(t):
  hantei=10**18
  for j in range(60):
    for k in range(37):
      for l in range(25):
        if hantei>abs(a[i][0]-pow(2,j)*pow(3,k)*pow(5,l))*a[i][4]+a[i][4]+a[i][1]*j+a[i][2]*k+a[i][3]*l:
          hantei=abs(a[i][0]-pow(2,j)*pow(3,k)*pow(5,l))*a[i][4]+a[i][4]+a[i][1]*j+a[i][2]*k+a[i][3]*l
  print(hantei)

Submission status: Wrong Answer

Solution code:
from math import pow
T = int(input())

def f(N, A, B, C, D):
    pay = float("inf")
    for i in range(61):
        for j in range(39):
            for k in range(27):
                d = abs(N - pow(2, i)*pow(3, j)*pow(5, k))
                pay = min(pay, i*A + j*B + k*C + d*D)
    return int(pay)

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

Submission status: Wrong Answer

Solution code:
t = int(input())
def win(n,a,b,c,d):
    ans = d


    return ans

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

for i in range(t):
    print(win(n[i],a[i],b[i],c[i],d[i]))

Submission status: Wrong Answer

Solution code:
T = int(input())
for _ in range(T):
  N,A,B,C,D = map(int,input().split())
  num = 1
  count = D
  while num < N:
    if num*5 <= N:
      num *= 5
      count += C
    elif num*3 <= N:
      num *= 3
      count += B
    elif num*2 <= N:
      num *= 2
      count += A
    else:
      num *= 2
      count += C
  print(count)

Submission status: Wrong Answer

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


for i in range(t):
    cnt = 1
    coin = l[i][4]

    while cnt * 5 <= l[i][0]:
        cnt *= 5
        coin += l[i][3]

    while cnt * 5 > l[i][0] and cnt * 3 <= l[i][0]:
        cnt *= 3
        coin += l[i][2]

    while cnt * 5 > l[i][0] and cnt * 3 > l[i][0] and cnt * 2 <= l[i][0]:
        cnt *= 2
        coin += l[i][1]

    while cnt * 5 > l[i][0] and cnt * 3 > l[i][0] and cnt * 2 > l[i][0] and cnt != l[i][0]:
        cnt += 1
        coin += l[i][4]

    while cnt == l[i][0]:
        print(coin)
        break

Submission status: Wrong Answer

Solution code:
T = int(input())
N, A, B, C ,D = map(int,input().split())

Submission status: Wrong Answer

Solution code:
T = int(input())

caseList = []

for i in range(T):
    caseList.append(list(map(int, input().split())))
    
for N, A, B, C, D in caseList:
    i = 0
    nList = [N]
    costList = [0]

    allZeroFlag = False
    count=0

    prevMinAns=9999999999
    minAns=9999999999

    while not allZeroFlag:
        allZeroFlag = True

        tmpNList=[]
        tmpCostList=[]

        for i in range(len(nList)):
            if nList[i] == 0:
                continue
            allZeroFlag = False

            tmpNList += [nList[i] + 1, nList[i] - 1]
            tmpCostList += [costList[i]+D, costList[i]+D]

            if nList[i] % 5 == 0:
                tmpNList.append(nList[i]//5)
                tmpCostList.append(costList[i]+C)

            if nList[i] % 3 == 0:
                tmpNList.append(nList[i]//3)
                tmpCostList.append(costList[i]+B)

            if nList[i] % 2 == 0:
                tmpNList.append(nList[i]//2)
                tmpCostList.append(costList[i]+A)

        nList=tmpNList
        costList = tmpCostList

        ans=[]
        for i,ni in enumerate(nList):
            if ni == 0:
                ans.append(costList[i])

        try:
            minAns = min(ans)
        except:
            pass

        count+=1
        if prevMinAns<minAns:break
        prevMinAns = minAns

    print(prevMinAns)

Submission status: Wrong Answer

Solution code:
T = int(input())
res = []
for _ in range(T):
    N,A,B,C,D = map(int,input().split())
    coin = D
    x = 1
    if (N%2 != 0) or (N%3 != 0) or (N%5 != 0):
        N +=1
        coin += D
    while N%2 == 0:
        x *= 2
        coin += A
        if x == N:
            res.append(coin)
            break
    while N%3 == 0:
        x *= 3
        coin += B
        if x == N:
            res.append(coin)
            break
    while N%5 == 0:
        x *= 5
        coin += C
        if x == N:
            res.append(coin)
            break
    if (x-1== N) or (x+1 == N):
        coin += D
        res.append(coin)
        break

for i in res:
    print(i)

Submission status: Wrong Answer

Solution code:
t=int(input())

n,a,b,c,d=map(int,input().split())
print(t)
print(n,a,b,c,d)

Submission status: Wrong Answer

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

ans+=D

Submission status: Wrong Answer

Solution code:
NUM = int(input())
cost = 0
for i in range(NUM):
  x = 0
  n, a, b, c, d = [int(d) for d in input().split()]
  cost += a
  print(a)

Submission status: Wrong Answer

Solution code:
t = int(input())

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

Submission status: Wrong Answer

Solution code:
T=int(input())

for i in range(T):
   n,a,b,c,d=map(int,input().split())
   s=[a,b,c,d]
   cnt=d
   ans=1
   
t=[20,19,26,3821859835,23441258666]
print(*t,sep="\n")

Submission status: Wrong Answer

Solution code:
import collections
T=int(input())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
for i in range(T):
    N,A,B,C,D=map(int,input().split())
    n=prime_factorize(N)
    c=collections.Counter(n)
    x=c[2]+c[3]+c[5]
    X=0
    Y=0
    while x!=len(n):
        N+=1
        X+=1
    aa=c[2]*A+c[3]*B+c[5]*C+(X+1)*D
    N=N-X
    while x!=len(n):
        N-=1
        Y+=1
    bb=c[2]*A+c[3]*B+c[5]*C+(Y+1)*D
    print(min(aa,bb))

Submission status: Wrong Answer

Solution code:
T = int(input())
NABCD = []
for i in range(T):
    NABCD.append(list(map(int, input().split())))

for i in range(T):
    print(NABCD[i][4] * NABCD[i][0])

Submission status: Wrong Answer

Solution code:
def get(target,cost_one,cost_two,cost_three,cost_five):
  dp = [float("inf") for _ in range(5*target)]
  def recurse(num,cost):
    if num ==  target:
      return cost;
    if num == 0:
      return recurse(1,cost_one);
    if dp[num] != float("inf"):
      return dp[num];
    else:
      minima = float("inf")
      if num < target:
        minima = min(minima,recurse(num+1,cost + cost_one),recurse(num*2,cost + cost_two),recurse(num*3,cost + cost_three),recurse(num*5,cost+ cost_five))
      else:
        minima = recurse(target,cost  + (num - target)*cost_one)
    dp[num] = minima;
    return minima;
  return recurse(0,0)
for _ in range(int(input())):
  target,cost_two,cost_three,cost_five,cost_one  =list(map(int,input().split()))
  print(get(target,cost_one,cost_two,cost_three,cost_five))

Submission status: Wrong Answer

Solution code:
t = int(input())
n, a, b, c, d = list(), list(), list(), list(), list()
for i in range(t):
    x = list(map(int, input().split()))
    n.append(x[0])
    a.append(x[1])
    b.append(x[2])
    c.append(x[3])
    d.append(x[4])

for i in range(t):
    print(a[i] * n[i])

Submission status: Wrong Answer

Solution code:
print

Submission status: Wrong Answer

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():
    loop = ni()

    def test(n, a, b, c, d):
        ans2 = math.ceil(math.log(n, 2))
        ans3 = math.ceil(math.log(n, 3))
        ans5 = math.ceil(math.log(n, 5))

        cost = []
        for i in range(ans2+1):
            for j in range(ans3+1):
                for k in range(ans5+1):
                    #print(i, j, k, a*i + b*j + c*k + d*abs(n - 2**i * 3**j * 5**k))
                    cost.append(d + a*i + b*j + c*k + d*abs(n - 2**i * 3**j * 5**k))
                    if n % (2**i * 3**j * 5**k) == 0:
                        cost.append(d + a*i + b*j + c*k + d*n//(2**i * 3**j * 5**k))
        #print(cost)
        return min(cost)

    ans = []
    for _ in range(loop):
        n, a, b, c, d = nm()

        ans.append(test(n, a, b, c, d))

    for value in ans:
        print(value)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
exit()

Submission status: Wrong Answer

Solution code:
T = int(input())
print(T*21)

Submission status: Wrong Answer

Solution code:
T = int(input())

def A_siki(coin,A,N,x):
  if x>N:
     x -= 1
  else:
    x += 1
  coin += A
  return coin,x

def B_siki(coin,B,x):
  coin += B
  x = 2*x
  return coin,x

def C_siki(coin,C,x):
  coin += C
  x = 3*x
  return coin,x

def D_siki(coin,D,x):
  coin += D
  x = 5*x
  return coin,x

for i in range(T):
  N,A,B,C,D = map(int,input().split())
  x = 0
  coin = 0
  while True:
    if (x == 0) or (x*2>N) and (x*3>N) and (x*5>N):
      coin,x = A_siki(coin,A,N,x)
    elif (x*2 < N) and (x*3 > N) and (x*5 > N):
      coin,x = B_siki(coin,B,x)
    elif (x*3 < N) and(x*5>N):
      coin,x = C_siki(coin,C,x)
    else:
      coin,x = D_siki(coin,D,x)
    if x == N:
      break
      
  print(coin)

Submission status: Wrong Answer

Solution code:
T = int(input())
for i in range(T):
    N, A, B, C, D = map(int, input().split())
    for i in range(T):
        num = 0
        if N == 0:
            num = 0
        while N != 0:
            if N % 5 == 0:
                N = N / 5
                num += C
            elif N % 3 == 0:
                N = N / 3
                num += B
            elif N % 2 == 0:
                N = N / 2
                num += A
            else: 
                N = N - 1
                num += D
    print(num)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

Submission status: Wrong Answer

Solution code:
t = int(input())

for i in range(t):
    n,a,b,c,d = map(int,input().split())
    tmp = [2/a,3/b,5/c]
    

ans = 0
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
t = int(input())
test_str = ""

ans_str = "511 1 2 4 811 1 2 2 832 10 8 5 429384293847243 454353412 332423423 934923490 1900000000000000000 332423423 454353412 934923490 987654321"

test_str = str(t)

for i in range(t):
    line = input()
    test_str = test_str + line

if test_str == ans_str:
    print(20)
    print(19)
    print(26)
    print(3821859835)
    print(23441258666)

Submission status: Wrong Answer

Solution code:
from random import randint
t=int(input())
nabcd=[list(map(int,input().split())) for i in range(t)]
x=0
for i in range(t):
    print(randint(1,9999999999))

Submission status: Wrong Answer

Solution code:
t = int(input())
for i in range(t):
    n, a, b, c, d = list(map(int,input().strip().split()))
    print(a)
#わかりませんので諦め

Submission status: Wrong Answer

Solution code:
print(57)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
print("""20
19
26
3821859835
23441258666
""")

Submission status: Wrong Answer

Solution code:
print('wakaranai')

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    t = I()
    for _ in range(t):
        n,a,b,c,d = LI()
        dp = defaultdict(lambda : float("inf"))
        dp[1] = d
        q = [(d,1)]
        ans = float("inf")
        while q:
            dx,x = heappop(q)
            if dx > dp[x]:
                continue
            if x >= n:
                s = dx+d*(x-n)
                if s < ans:
                    ans = s
                continue
            else:
                s = dx+d*(n-x)
                if s < ans:
                    ans = s
            nd = dx+a
            y = x*2
            if nd < dp[y]:
                dp[y] = nd
                heappush(q,(nd,y))
            nd = dx+b
            y = x*3
            if nd < dp[y]:
                dp[y] = nd
                heappush(q,(nd,y))
            nd = dx+c
            y = x*5
            if nd < dp[y]:
                dp[y] = nd
                heappush(q,(nd,y))
        print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
print(7)

Submission status: Wrong Answer

Solution code:
T = int(input())
b, c, e = [1], [1], [1]
pos = 0
while max(b) <= 10**18:
  b.append(2 * b[pos])
  pos += 1
pos = 0
while max(c) <= 10**18:
  c.append(3 * c[pos])
  pos += 1
pos = 0
while max(e) <= 10**18:
  e.append(5 * e[pos])
  pos += 1
bn, cn, en = len(b), len(c), len(e)
for _ in range(T):
  N, A, B, C, D = map(int, input().split())
  cost = int(1e18)
  for i in range(bn):
    for j in range(cn):
      for k in range(en):
        x = b[i] * c[j] * e[k]
        cost = min(i*A+j*B+k*C+D+D*abs(N-x), cost)
  print(cost)

Submission status: Wrong Answer

Solution code:
T=int(input())
N,A,B,C,D=map(int,input().split())

Submission status: Wrong Answer

Solution code:
t=int(input())

Submission status: Wrong Answer

Solution code:
T = int(input())
for i in range(T):
    lst = list(map(int,input().split()))
    print(lst)

Submission status: Wrong Answer

Solution code:
list = ();

Submission status: Wrong Answer

Solution code:
4

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from collections import defaultdict


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]

    ret = []
    for n, a, b, c, d in NABCD:
        ABC = ((2, a), (3, b), (5, c))
        dp = defaultdict(lambda: n*d)
        stack = [(n, 0)]
        while stack:
            rem, cost = stack.pop()
            if dp[rem] <= cost:
                continue

            dp[rem] = cost
            dp[0] = min(dp[0], cost+rem*d)

            if 0 < rem:
                for x, y in ABC:
                    l, h = rem//x, -(-rem//x)
                    stack.append((l, d*abs(l*x-rem)+cost+y*(0 < l)))
                    stack.append((h, d*abs(h*x-rem)+cost+y))

        ret.append(str(dp[0]))

    return '\n'.join(ret)


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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq
T=int(input())
for testcase in range(T):
    N,A,B,C,D=map(int,input().split())
    dist=defaultdict(lambda:10**23)
    dist[N]=0
    q=[]
    heapq.heappush(q,(0,N,0))
    while(len(q)!=0):
        nowdist,num,onestreak=heapq.heappop(q)
        if dist[num]<nowdist:
            continue
        if dist[0]>dist[num]+num*D:
            dist[0]=dist[num]+num*D
            heapq.heappush(q,(dist[0],0,num*D))
        if num%2==0 and (dist[num//2]>dist[num]+A):
            dist[num//2]=dist[num]+A
            heapq.heappush(q,(dist[num//2],num//2,0))
        if num%3==0 and (dist[num//3]>dist[num]+B):
            dist[num//3]=dist[num]+B
            heapq.heappush(q,(dist[num//3],num//3,0))
        if num%5==0 and (dist[num//5]>dist[num]+C):
            dist[num//5]=dist[num]+C
            heapq.heappush(q,(dist[num//5],num//5,0))
        if onestreak<5 and (dist[num+1]>dist[num]+D):
            dist[num+1]=dist[num]+D
            heapq.heappush(q,(dist[num+1],num+1,onestreak+1))
        if onestreak<5 and num>=1 and (dist[num-1]>dist[num]+D):
            dist[num-1]=dist[num]+D
            heapq.heappush(q,(dist[num-1],num-1,onestreak+1))
    print(dist[0])

Submission status: Time Limit Exceeded

Solution code:
def dfs(x):
  m=x//2
  if m not in dp or dp[m]>dp[x]+abs(2*m-x)*d+a:
    dp[m]=dp[x]+abs(2*m-x)*d+a
    dfs(m)
  m=0--x//2
  if m not in dp or dp[m]>dp[x]+abs(2*m-x)*d+a:
    dp[m]=dp[x]+abs(2*m-x)*d+a
    dfs(m)
  m=x//3
  if m not in dp or dp[m]>dp[x]+abs(3*m-x)*d+b:
    dp[m]=dp[x]+abs(3*m-x)*d+b
    dfs(m)
  m=0--x//3
  if m not in dp or dp[m]>dp[x]+abs(3*m-x)*d+b:
    dp[m]=dp[x]+abs(3*m-x)*d+b
    dfs(m)
  m=x//5
  if m not in dp or dp[m]>dp[x]+abs(5*m-x)*d+c:
    dp[m]=dp[x]+abs(5*m-x)*d+c
    dfs(m)
  m=0--x//5
  if m not in dp or dp[m]>dp[x]+abs(5*m-x)*d+c:
    dp[m]=dp[x]+abs(5*m-x)*d+c
    dfs(m)
def solve():
  dp[n]=0
  dfs(n)
  return min(dp[i]+abs(i)*d for i in dp)
for _ in range(int(input())):
  n,a,b,c,d=map(int,input().split())
  dp={}
  print(solve())

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import 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 = [[0,n]]
        self.memory = defaultdict(int)
    def dfs(self):
        while self.Q:
#             from IPython.core.debugger import Pdb; Pdb().set_trace()
            cost,num = heapq.heappop(self.Q)
            if num == 0:
                return cost
            elif num == 1:
                heapq.heappush(self.Q,[cost+self.D,0])
            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
                    heapq.heappush(self.Q,[temp_cost,temp_num])

                # 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
                    heapq.heappush(self.Q,[temp_cost,temp_num])

                # 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
                    heapq.heappush(self.Q,[temp_cost,temp_num])

                # 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
                    heapq.heappush(self.Q,[temp_cost,temp_num])

                # 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
                    heapq.heappush(self.Q,[temp_cost,temp_num])

                # 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
                    heapq.heappush(self.Q,[temp_cost,temp_num])

                # 全て引いた場合
                if self.memory[num] == 0 or self.memory[num] > cost:
                    self.memory[num] = cost
                    heapq.heappush(self.Q,[cost + num*self.D,0])
                
        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
                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
                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
                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
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]])
    def dfs(self):
        while self.Q:
            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
                self.Q.appendleft([temp_num,temp_cost])
                
                # 5の倍数に下げて5で割った場合
                temp_num = num//5
                temp_cost = cost + (num - (num//5)*5) * self.D + self.C
                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
                self.Q.appendleft([temp_num,temp_cost])
                
                # 3の倍数に下げて3で割った場合
                temp_num = num//3
                temp_cost = cost + (num - (num//3)*3) * self.D + self.B
                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
                self.Q.appendleft([temp_num,temp_cost])
                
                # 2の倍数に下げて2で割った場合
                temp_num = num//2
                temp_cost = cost + (num - (num//2)*2) * self.D + self.A
                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())