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: Runtime Error

Solution code:

def estimateZeroToFive(A, B, C, D):
    List = [0] * 7
    List[1] = D
    List[2] = min(A+D, 2 * D)
    List[3] = min(3*D, List[2] + D, List[1] + B)
    List[6] = min(6*D, List[2] + B, List[3] + A, C+2*D)
    List[4] = min(4*D, List[2] + A, List[3] + D, 2*D+C, List[2]+B+2*D)
    List[5] = min(5*D, List[1] + C, List[4] + D, List[6] + D, List[2]+B+D )

    return List

def queue(Queue_CostValue):
    Values = Queue_CostValue.pop(0)
    return Values

def OneTurn(A, B, C, D, Costs_ZeroToFive, Acchieved, Queue_CostValue_Turns):
    while(len(Queue_CostValue_Turns)>0):

        CostValue = queue(Queue_CostValue_Turns)

        Cost = CostValue[0]
        Value = CostValue[1]
        CostMin = Acchieved[0]
        Flag = True
        if(Cost > CostMin):
            Flag = False
        elif(Value <= 6):
            Cost += Costs_ZeroToFive[Value]
            if(Cost < CostMin):
                Acchieved[0] = Cost
                Flag = False
        if(Flag==True):
            if(Value %5 ==0):
                Queue_CostValue_Turns.append([Cost+C, Value//5 ])
            if(Value%3 == 0):
                Queue_CostValue_Turns.append([Cost+B, Value//3 ])
            if(Value%2==0):
                Queue_CostValue_Turns.append([Cost+A, Value//2 ])

            Queue_CostValue_Turns.append([Cost+D, Value+1])
            Queue_CostValue_Turns.append([Cost+D, Value-1])
            OneTurn(A, B, C, D, Costs_ZeroToFive, Acchieved, Queue_CostValue_Turns)


def OneTurn2(A, B, C, D, Costs_ZeroToFive, Acchieved, Queue_CostValue_Turns):
    while(len(Queue_CostValue_Turns)>0):

        CostValue = queue(Queue_CostValue_Turns)

        Cost = CostValue[0]
        Value = CostValue[1]
        Turns = CostValue[2]
        CostMin = Acchieved[0]
        Flag = True
        if(Cost > CostMin):
            Flag = False
        elif(Value <= 6):
            Cost += Costs_ZeroToFive[Value]
            if(Cost < CostMin):

                Acchieved[0] = Cost

                if(len(Acchieved)==1):
                    Acchieved.append(Turns)
                else:
                    Acchieved[1]=Turns
                Flag = False
        if(Flag==True):
            if(Value %5 ==0):
                Queue_CostValue_Turns.append([Cost+C, Value//5, Turns+"C" ])
            if(Value%3 == 0):
                Queue_CostValue_Turns.append([Cost+B, Value//3, Turns+"B" ])
            if(Value%2==0):
                Queue_CostValue_Turns.append([Cost+A, Value//2, Turns+"A" ])

            Queue_CostValue_Turns.append([Cost+D, Value+1, Turns+"D+"])
            Queue_CostValue_Turns.append([Cost+D, Value-1, Turns+"D-"])
            OneTurn2(A, B, C, D, Costs_ZeroToFive, Acchieved, Queue_CostValue_Turns)


if(__name__ == "__main__"):
    # T = int( input().strip() )
    T = 1
    NABCDList =[]
    for Num in range(T):
        StrList = input().strip().split()
        for m in range( len(StrList) ):
            N = int(StrList[0])
            A = int(StrList[1])
            B = int(StrList[2])
            C = int(StrList[3])
            D = int(StrList[4])

        Costs_ZeroToFive= estimateZeroToFive(A, B, C, D)
        Acchieved = [N*D]
        # print("0-6: ", Costs_ZeroToFive)
        # OneTurn2(A, B, C, D, Costs_ZeroToFive, Acchieved, [ [0, N, ""] ])
        OneTurn(A, B, C, D, Costs_ZeroToFive, Acchieved, [ [0, N] ])
        print(Acchieved[0])
        #estimatemin(N, A, B, C, D, N, Min, 0)
        #print(Min)

        #estimatemin(N, A, B, C, D, Value, Min, Coin_Used = 0):

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
import functools
@functools.lru_cache(maxsize=None)  
def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D,solve((N+1)//2)+A+D)
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    else:
        b=N%3 
        tmp=min(tmp,solve((N+(3-b))//3)+B+(3-b)*D,solve((N-b)//3)+B+b*D)
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    else:
        c=N%5
        tmp=min(tmp,solve((N-c)//5)+C+D*c,solve((N+(5-c))//5)+C+D*(5-c))
    return tmp

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

Submission status: Runtime Error

Solution code:
N=int(input())
S=list(map(int,input().split()))
count=0
P=[0]*(N*N+1)
for j in range(N*N):
  P[j+1]=S.index(j+1)
for i in range(N*N):
  player=S[i]
  hayasa=P[player]
  
  que=[[] for _ in range(N)]
  d=[-1]*(N*N+1)
  que[0].append(player)
  d[player]=i
  
  j=0
  finish=0
  while True:
    for kouho in que[j]:
      if kouho%N==0:
        finish=1
        break
      if kouho%N==1:
        finish=1
        break
      if kouho+N>N*N:
        finish=1
        break
      if kouho<N:
        finish=1
        break
        
      if d[kouho+N]<i:
        if P[kouho+N]>hayasa:
          que[j+1].append(kouho+N)
          d[kouho+N]=i
        else:
          que[j].append(kouho+N)
          d[kouho+N]=i
          
      if d[kouho-N]<i:
        if P[kouho-N]>hayasa:
          que[j+1].append(kouho-N)
          d[kouho-N]=i
        else:
          que[j].append(kouho-N)
          d[kouho-N]=i
          
      if d[kouho+1]<i:
        if P[kouho+1]>hayasa:
          que[j+1].append(kouho+1)
          d[kouho+1]=i
        else:
          que[j].append(kouho+1)
          d[kouho+1]=i
          
      if d[kouho-1]<i:
        if P[kouho-1]>hayasa:
          que[j+1].append(kouho-1)
          d[kouho-1]=i
        else:
          que[j].append(kouho-1)
          d[kouho-1]=i
    if finish==1:
      count+=j
      break
    j+=1    
print(count)

Submission status: Runtime Error

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

	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False
	@njit
	def dfs(x):
		if x == 0:
			return
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add((x+1)//2, v):
				dfs((x+1)//2)

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

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

Submission status: Runtime Error

Solution code:
def helper(N:int, A:int, B:int, C:int, D:int, cost:int):
    if N <= 0: return
    for j in range(-1, 2):
        for i in range(3):
            if N + j == 0: 
                global ans
                ans = min(ans, cost+D)
                return
            if (N+j) % table[i] == 0:
                helper((N+j)/table[i], A, B, C, D, cost+cost_v[i]+(D if j != 0 else 0))

table = [2, 3, 5]
cost_v = [1, 2, 4]
T = input()
while T > 0:
   N, A, B, C, D = input(), input(), input(), input(), input()
   cost_v[0], cost_v[1], cost_v[2] = A, B, C
   ans = float("inf")
   helper(11,1,2,4,8,0)
   print(ans)
   T -= 1

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
T=int(input())

def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    if N in dic:
        return dic[N]
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D)
    b=N%3 
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    else:
        tmp=min(tmp,solve((N+(3-b))//3)+B+D,solve((N-b)//3)+B+2*D)
    c=N%5
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    else:
        tmp=min(tmp,solve((N-c)//5)+C+D*c,,solve((N+(5-c))//5)+C+D*(5-c))
    dic[N]=tmp
    return tmp

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

Submission status: Runtime Error

Solution code:
t = int(input())
for k in range(t):
  n,a,b,c,d=list(map(int,input().split()))
  olist={"A":a,"B":b,"C":c,"D":d}
  ans=0
  d=1
  while ans==0:
    for dd in range(d):
      for o in olist:
        
      print(dd)
    d+=1  
    ans+=1
  print(olist)

Submission status: Runtime Error

Solution code:
T = int(input())
for i in range(T):
    N,A,B,C,D = map(int,input().split())
    memo = {0:0,1:D}
    def f(n):
        if n in memo:
            return memo[n]
        else:
            res = D*n
            r2 = n%2
            r3 = n%3
            r5 = n%5
            res = min(res,f(n//2)+A+r2*D,f(n//3)+B+r3*D,f(n//5)+C+r5*D)
            res = min(res,f((n+1)//2)+A+(2-r2)*D,f((n+2)//3+1)+B+(3-r3)*D,f((n+4)//5+1)+C+(5-r5)*D)
            memo[n] = res
            return res
    print(f(N))

Submission status: Runtime Error

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

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

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

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

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]

#配るDPで考える。
    dp = [10**10 for _ in range(5*(n-1)+1)]
    dp[0] = 0
    dp[1] = d
    j = 1
    while j < n:
        #print(j)
        #pt_a = pt_b = pt_c = pt_d = 10 ** 10
        pt_a = pt_b = pt_c = pt_d = float("inf")

        if dp[j] == 10**10:
            j += 1
            continue

        dp[j*2] = min(dp[j*2],dp[j] + a)

        dp[j*3] = min(dp[j*3],dp[j] + b)

        dp[j*5] = min(dp[j*5],dp[j] + c)

        dp[j+1] = min(dp[j+1],dp[j] + d)

        #if not j-1 in dp:
        #    dp[j-1] = dp[j] + d
        #    j -= 1
        #    continue
        #else:
        #    if dp[j-1] > dp[j] + d:
        #        dp[j-1] = dp[j] + d
        #        j -= 1
        #        continue
        j += 1
            
    
    print(dp[n])
    #print(dp[n])

    result = float("inf")

    for k in range(0,5*(n-1)+1-n):
        if n+k in dp:
            result = min(result,dp[n+k]+k*d)


    print(result)





#
#    #i進めるときに使うコインの最小値をdp[i]
#    dp = dict()
#    dp[0] = 0
#    dp[1] = d
#    j = 2
#    while True:
#        #print(j)
#        #pt_a = pt_b = pt_c = pt_d = float("inf")
#        pt_a = pt_b = pt_c = pt_d = 10 ** 10
#
#        if j >= a and j % 2 == 0:
#            pt_a = dp[j/2] + a
#        
#        if j >= b and j % 3 == 0:
#            pt_b = dp[j/3] + b
#
#        if j >= c and j % 5 == 0:
#            pt_c = dp[j/5] + c
#        
#        pt_d = dp[j-1] + d
#        if not j in dp:
#            dp[j] = min(pt_a,pt_b,pt_c,pt_d)
#        else:
#            dp[j] = min(dp[j],pt_a,pt_b,pt_c,pt_d)
#
#
#        if dp[j-1] > dp[j]+d:
#            dp[j-1] = dp[j]+d
#            j = j-1
#        else:
#            if j == n:
#                break
#            else:
#                j += 1
#
#    print(dp[n])
#
#    #切り上げ
#    end_point = (n-1)*5
#    j += 1
#    while True:
#        #pt_a = pt_b = pt_c = pt_d = float("inf")
#        pt_a = pt_b = pt_c = pt_d = 10 ** 10
#        if j >= a and j % 2 == 0:
#            pt_a = dp[j/2] + a
#        
#        if j >= b and j % 3 == 0:
#            pt_b = dp[j/3] + b
#
#        if j >= c and j % 5 == 0:
#            pt_c = dp[j/5] + c
#        
#        pt_d = dp[j-1] + d
#        if not j in dp:
#            dp[j] = min(pt_a,pt_b,pt_c,pt_d)
#        else:
#            dp[j] = min(dp[j],pt_a,pt_b,pt_c,pt_d)
#
#        if dp[j-1] > dp[j]+d:
#            dp[j-1] = dp[j]+d
#            j = j-1
#        else:
#            if j > dp[n]+end_point:
#                break
#            else:
#                j += 1
#    
#    print(dp[n])












# コインi枚で進める最大量がdp[i]と考えたとき
#    dp = defaultdict(int)
#    dp[d] = 1
#    j = d
#    while True:
#        j += 1
#        pt_a = pt_b = pt_c = pt_d = float("inf")
#        #aのパターン
#        if j >= a:
#            pt_a = dp[j-a]*2
#        
#        #bのパターン
#        if j >= b:
#            pt_b = dp[j-b]*3
#
#        #cのパターン
#        if j >= c:
#            pt_c = dp[j-c]*5
#
#        #dのパターン
#        pt_d = min(dp[j-d]+1,dp[j-d]-1)
#
#        pt_a = dp[i-1] + 1
#        if i>2 and i % 2 == 0:
#            pt_b = dp[i%2]

        



    #if n % 5 == 0:
    #    pass
    #elif n % 3 == 0:
    #    pass
    #elif n % 2 == 0:
    #    pass

Submission status: Runtime Error

Solution code:
import math

t = input()
cases = []
for i in range(int(t)):
  temp = input().split()
  cases.append([int(temp[0]),int(temp[1]),int(temp[2]),int(temp[3]),int(temp[4])])

log = []
case = []
#saiki de zen tansaku
def saiki(temochi,max):
  if log[max] > temochi:
    log[max] = temochi
  else:
    return
  if max ==0:
    return
  
  if max % 5 == 0 :
    saiki(temochi + case[3] , max // 5)
  if max % 3 == 0 :
    saiki(temochi + case[2] , max // 3)
  if max % 2 == 0 :
    saiki(temochi + case[1] , max // 2)
  
  saiki(temochi + case[4] , max - 1)
  upsaiki(temochi + case[4] , max + 1)

def upsaiki(temochi,max):
  
  if max % 5 == 0:
    saiki(temochi + case[3] , max //5)
  if max % 3 == 0 and max <= i[0] * 3 / 2:
    saiki(temochi + case[2] , max // 3)
  if max <= i[0] * 5 / 3:
    upsaiki(temochi + case[4] , max + 1)
    
  
for i in cases:
  #so insu bunkai
  n = i[0]
  factor = []
  limit = int(math.sqrt(n))+1
  for num in range(2,limit):
    while n%num == 0:
      n //= num
      factor.append(num)
    if n == 1:
      break
  else:
    factor.append(n)
  
  log = list(reversed(range(i[0] + 1)))
  case = i
  saiki(0,i[0])
  print(log[0])

Submission status: Runtime Error

Solution code:
import heapq
def calc(n,a,b,c,d):
    candidates = []
    cost = {2:a,3:b,5:c}
    que = [(0,n)]
    heapq.heapify(que)
    mult = [2,3,5]
    ans = 10**18
    while len(que)>0:
        c,v = heapq.heappop(que)
        if ans<c:
            break
        for m in mult:
            if v<m:
                print(*que)
                t = c+d*v
                candidates.append(t)
                ans = min(ans,t)

            c1 = d*(v-(v//m*m)) + cost[m] + c
            v1 = v//m
            c2 = -d*(v+(-v)//m*m) + cost[m] + c
            v2 = -(-v//m)
            if c1<c2:
                heapq.heappush(que,(c1,v1))
            else:
                heapq.heappush(que,(c2,v2))
        # for value,cost in stack:
        #     for m in mult: 
        #         if value<m: 
        #             candidates.append(cost+d*value)
        #             continue
        #         c1 = d*(value-(value//m*m)) + c[m] + cost
        #         v1 = value//m
        #         c2 = -d*(value+(-value)//m*m) + c[m] + cost
        #         v2 = -(-value//m)

    print(min(candidates))

def main():
    calc(*tuple(map(int,input().split())))
    # t = int(input())

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

import numpy as np
def func(N , A, B, C, D):
    lis1 =prime_factorize(N)
    lis1 = [str(n) for n in lis1]
    l1 = [A if i =="2" else i for i in lis1]
    l1= [B if i =="3" else i for i in l1]
    l1 = [C if i =="5" else i for i in l1]
    l1 = [int(n) for n in l1]
    l1 = max (sum(l)+D, D*sum(l))

    lis2 = prime_factorize(N-1)
    lis2 = [str(n) for n in lis2]
    l2 = [A if i =="2" else i for i in lis2]
    l2 = [B if i =="3" else i for i in l2]
    l2 = [C if i =="5" else i for i in l2]
    l2 = [int(n) for n in l2]
    l2 = min (sum(l2)+D*2, D*sum(l2))

    lis3 = prime_factorize(N+1)
    lis3 = [str(n) for n in lis3]
    l3 = [A if i =="2" else i for i in lis3]
    l3 = [B if i =="3" else i for i in l3]
    l3 = [C if i =="5" else i for i in l3]
    l3 = [int(n) for n in l3]
    l3 = min (sum(l3)+D*2, D*sum(l3))
    return (min(l1,l2,l3))

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

Submission status: Runtime Error

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

import numpy as np
def func(N , A, B, C, D):
    lis1 =prime_factorize(N)
    lis1 = [str(n) for n in lis1]
    l1 = [A if i =="2" else i for i in lis1]
    l1= [B if i =="3" else i for i in l1]
    l1 = [C if i =="5" else i for i in l1]
    l1 = [int(n) for n in l1]
    l1 = max (sum(l)+D, D*sum(l))

    lis2 = prime_factorize(N-1)
    lis2 = [str(n) for n in lis2]
    l2 = [A if i =="2" else i for i in lis2]
    l2 = [B if i =="3" else i for i in l2]
    l2 = [C if i =="5" else i for i in l2]
    l2 = [int(n) for n in l2]
    l2 = min (sum(l2)+D*2, D*sum(l2))

    lis3 = prime_factorize(N+1)
    lis3 = [str(n) for n in lis3]
    l3 = [A if i =="2" else i for i in lis3]
    l3 = [B if i =="3" else i for i in l3]
    l3 = [C if i =="5" else i for i in l3]
    l3 = [int(n) for n in l3]
    l3 = min (sum(l3)+D*2, D*sum(l3))
    print(min(l1,l2,l3))

T = int(input())
for i in range(1, T+1):
    N, A, B, C, D = map(int, input().split())
    func(N, A, B, C, D)

Submission status: Runtime Error

Solution code:
T = int(input())
inf = float("inf")
import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限

can3=inf
can2=inf
can5=inf
def dp(n,A,B,C,D):
    global can3,can2,can5 
    if n>=30:
        return n//30*dp(30,A,B,C,D) + dp(n%30,A,B,C,D)
    if n==0:
        return 0
    if n==1:
        return D
    if n%5==0:
        can5 = dp(n//5,A,B,C,D) + C
    if n%3==0:
        can3 = dp(n//3,A,B,C,D) + B
    if n%2==0:
        can2 = dp(n//2,A,B,C,D) + A     
    return min(can5,can3,can2,dp(n-1,A,B,C,D)+D,dp(n+1,A,B,C,D)+D)
    
for i in range(T):
    N,a,b,c,d = map(int,input().split())
    print(dp(N,a,b,c,d))

Submission status: Runtime Error

Solution code:
import copy

def a(j,calc,ABC,D,n):
    result_ = 0
    n_ = n
    
    while n_ != 1:
        ABC_tmp = copy.deepcopy(ABC[j])
        
        for k in range(len(ABC)):
            if n_ % ABC_tmp[k] != 0:
                del ABC_tmp[k]
               
        min_coin = min(ABC_tmp)
        min_index = ABC[j].index(min_coin)
        calc_ = calc[min_index]
        
        if calc_ == "A":
            n_ = n_ / 2
            result_ += ABC[i][0]
        elif calc_ == "B":
            n_ = n_ / 3
            result_ += ABC[i][1]
        elif calc_ == "C":
            n_ = n_ / 5
            result_ += ABC[i][2]
            
    return result_

def aaa(j,calc,ABC,D,n,a):
    result_ = 0
    n_ = n + a
    result_ += D[j]
    
    
    while n_ != 1:
        ABC_tmp = copy.deepcopy(ABC[j])
        
        for k in range(len(ABC)):
            if n_ % ABC_tmp[k] != 0:
                del ABC_tmp[k]
               
        min_coin = min(ABC_tmp)
        min_index = ABC[j].index(min_coin)
        calc_ = calc[min_index]
        
        if calc_ == "A":
            n_ = int(n_ / 2)
            result_ += ABC[i][0]
        elif calc_ == "B":
            n_ = int(n_ / 3)
            result_ += ABC[i][1]
        elif calc_ == "C":
            n_ = int(n_ / 5)
            result_ += ABC[i][2]
            
    return result_


# 操作を
calc = ["A","B","C"]

T =int(input())
N = [0]*T
ABC = []
D = [0]*T
result = [0]*T


for i in range(T):
    ABC.append([0]*3)
    N[i],ABC[i][0],ABC[i][1],ABC[i][2],D[i] = map(int,input().split())
    print(N)
    print(ABC)
    print(D)
    
for j,n in enumerate(N):#テストを回す
    
    result[j] + D[j]# 必ず最初は足す
    result_0 = 0
    result_1 = 0
    
    
    if n % 2 == 0 or n % 3 == 0 or n % 5 == 0:
        result[j] = a()
    else:
        # 最後に足すパターン
        result_0 = aaa(j,calc,ABC,D,n,-1)

        # 最後に引くパターン
        result_1 = aaa(j,calc,ABC,D,n,1)
 
        result[j] += min(result_0,result_1)

Submission status: Runtime Error

Solution code:
'''
T = 5
N = 11
A = 1#*2
B = 2#*3
C = 4#*5
D = 8#+1
'''

T = int(input())
#T = 1
for _ in range(T):
	N, A, B, C, D = map(int, input().split())
	#[A, B, C, D]
	memo = [0, D]#{1: D}
	for i in range(2, N+2):
		cost_A = 999999 if i%2 else memo[i//2] + A
		cost_B = 999999 if i%3 else memo[i//3] + B
		cost_C = 999999 if i%5 else memo[i//5] + C
		cost_D = memo[i-1] + D
		#memo[i] = cost
        cost = min(cost_A, cost_B, cost_C, cost_D)
		memo.append(cost)
		memo[i-1] = min([memo[i-1], cost + D])
		#print(str(i)+' >>> '+str(cost))
	print(memo[N])
print()

Submission status: Runtime Error

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)

T = int(input())

caseList = []

for i in range(T):
    caseList.append(list(map(int, input().split())))
    
for N, A, B, C, D in caseList:
    dic = {N: 0}
	minAns = 999999999999
	searchSet = set([N])

	count = 0
	k=N
	while True:
 	   tmpSet = set()

      v = dic[k]

      if k == 1:
          continue

      # A
      if k % 2 == 0:
          dic[k // 2] = dic.get(k // 2, minAns)
          if dic[k // 2] > v + A:
              dic[k // 2] = v + A
              tmpSet.add(k // 2)

      # B
      if k % 3 == 0:
          dic[k // 3] = dic.get(k // 3, minAns)
          if dic[k // 3] > v + B:
              dic[k // 3] = v + B
              tmpSet.add(k // 3)

      # C
      if k % 5 == 0:
          dic[k // 5] = dic.get(k // 5, minAns)
          if dic[k // 5] > v + C:
              dic[k // 5] = v + C
              tmpSet.add(k // 5)

      # D
      dic[k + 1] = dic.get(k + 1, minAns)
      if dic[k + 1] > v + D:
          dic[k + 1] = v + D
          tmpSet.add(k + 1)

      dic[k - 1] = dic.get(k - 1, minAns)
      if dic[k - 1] > v + D:
          dic[k - 1] = v + D
          tmpSet.add(k - 1)

      del dic[k]
      k=min(dic, key=dic.get)


      count += 1
      if 1 in dic.keys():
          if minAns > dic[1] + D:
              minAns = dic[1] + D
          #             print(minAns)
          else:
              break
	print(minAns)

Submission status: Runtime Error

Solution code:
'''
T = 5
N = 11
A = 1#*2
B = 2#*3
C = 4#*5
D = 8#+1
'''

T = int(input())
#T = 1
for _ in range(T):
	N, A, B, C, D = map(int, input().split())
	#[A, B, C, D]
	memo = [0, D]#{1: D}
	for i in range(2, N+2):
		cost_A = 999999 if i%2 else memo[i//2] + A
		cost_B = 999999 if i%3 else memo[i//3] + B
		cost_C = 999999 if i%5 else memo[i//5] + C
		cost_D = memo[i-1] + D
		#memo[i] = cost
		memo.append(min(cost_A, cost_B, cost_C, cost_D))
		memo[i-1] = min([memo[i-1], cost + D])
		#print(str(i)+' >>> '+str(cost))
	print(memo[N])
print()

Submission status: Runtime Error

Solution code:
def yu_c(n):
    if n >= 5:
        N5 = n // 5
        coin = C * N5
        N5_amari = n % 5
    if N5_amari >= 3:
        N3 = N5_amari // 3
        coin += B * N3
        N3_amari = N5_amari % 3
    if N3_amari >= 2:
        N2 = N3_amari // 2
        coin += A * N2
        N2_amari = N3_amari % 2
    
    coin += D * N2_amari
    return coin
    


for i in range(int(input())):
    N,A,B,C,D = map(int,input().split())
    
    #2,3,5で割れる一番Nに近い数を探す
    a = N % 2
    b = N % 3
    c = N % 5
    hiku = min(min(a,b),c)
    tasu = min(min(a,3-b),5-c)
    
    if A + B > C:
        yuusen = "AB"
    else:
        yuusen = "C"
    
    if yuusen == "C":
        yu_c(hiku)
        yu_c(tasu)
    else:
        yu_ab(hiku)
        yu_ab(tasu)

Submission status: Runtime Error

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

import numpy as np
def func(N , A, B, C, D):
    lis1 =prime_factorize(N)
    lis1 = [str(n) for n in lis1]
    l1 = [A if i =="2" else i for i in lis1]
    l1= [B if i =="3" else i for i in l1]
    l1 = [C if i =="5" else i for i in l1]
    l1 = max (sum(l)+D, D*sum(l))

    lis2 = prime_factorize(N-1)
    lis2 = [str(n) for n in lis2]
    l2 = [A if i =="2" else i for i in lis2]
    l2 = [B if i =="3" else i for i in l2]
    l2 = [C if i =="5" else i for i in l2]
    l2 = min (sum(l2)+D*2, D*sum(l2))

    lis3 = prime_factorize(N+1)
    lis3 = [str(n) for n in lis3]
    l3 = [A if i =="2" else i for i in lis3]
    l3 = [B if i =="3" else i for i in l3]
    l3 = [C if i =="5" else i for i in l3]
    l3 = min (sum(l3)+D*2, D*sum(l3))
    print(min(l1,l2,l3))

T = int(input())
for i in range(1, T+1):
    N, A, B, C, D = map(int, input().split())
    func(N, A, B, C, D)

Submission status: Runtime Error

Solution code:
T = int(input())
inf = float("inf")
import sys
sys.setrecursionlimit(10**4) #再帰関数の呼び出し制限

can3=inf
can2=inf
can5=inf
def dp(n,A,B,C,D):
    global can3,can2,can5 
    if n>30:
        return n//30*dp(30,A,B,C,D) + dp(n%30,A,B,C,D)
    if n==0:
        return 0
    if n==1:
        return D
    if n%5==0:
        can5 = dp(n//5,A,B,C,D) + C
    if n%3==0:
        can3 = dp(n//3,A,B,C,D) + B
    if n%2==0:
        can2 = dp(n//2,A,B,C,D) + A     
    return min(can5,can3,can2,dp(n-1,A,B,C,D)+D,dp(n+1,A,B,C,D)+D)
    
for i in range(T):
    N,a,b,c,d = map(int,input().split())
    print(dp(N,a,b,c,d))

Submission status: Runtime Error

Solution code:
hoge

Submission status: Runtime Error

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

def rec(n, a, b, c, d, x, coins, best):
    if coins > best:
        # cut branch
        return best + 1
    elif x >= n:
        return coins + d * (x - n)
    else:
        # d(x) 残り全部をdとした場合
        vdx = rec(n, a, b, c, d, n, coins + (n - x)*d, best)
        best = min(vdx, best)

        # a
        va = rec(n, a, b, c, d, x * 2, coins + a, best)
        best = min(va, best)
        # b
        vb = rec(n, a, b, c, d, x * 3, coins + b, best)
        best = min(vb, best)
        # c
        vc = rec(n, a, b, c, d, x * 5, coins + c, best)
        best = min(vc, best)

        # d(1)
        vd1 = rec(n, a, b, c, d, x + 1, coins + d, best)
        best = min(vd1, best)
        # d(2)
        #if x > 1:
        #    vd2 = rec(n, a, b, c, d, x - 1, coins + d, best)
        #    best = min(vd2, best)

        return best

def estimate(n, q, cost, cost_d):
    acc = 0
    while n:
        acc += cost + (n % q) * cost_d
        n //= q
    return acc

for i, tc in enumerate(tcs):
    n, a, b, c, d = tc

    v1 = estimate(n, 2, a, d)
    v2 = estimate(n, 3, b, d)
    v3 = estimate(n, 5, c, d)
    v4 = d*n
    best = min(v1, v2, v3, v4)

    ans = rec(n, a, b, c, d, 1, d, best)
    #print("case",i,ans)
    print(ans)