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

Solution (Python):
def main():
    import heapq
    t = int(input())
    for i in range(t):
        n, a, b, c, d = map(int, input().split())
        h = [(0, n)]
        heapq.heapify(h)
        s = set()
        while h:
            cost, now = heapq.heappop(h)
            if now in s:
                continue
            else:
                s.add(now)
            if now == 0:
                print(cost)
                break
            heapq.heappush(h, (cost+now*d, 0))
            
            if now % 2 == 0:
                heapq.heappush(h, (cost+a, now//2))
            else:
                heapq.heappush(h, (cost+a+d, (now+1)//2))
                heapq.heappush(h, (cost+a+d, now//2))
            
            if now % 3 == 0:
                heapq.heappush(h, (cost+b, now//3))
            else:
                temp = now % 3
                heapq.heappush(h, (cost+b+(3-temp)*d, (now+3-temp)//3))
                heapq.heappush(h, (cost+b+temp*d, now//3))
            
            if now % 5 == 0:
                heapq.heappush(h, (cost+c, now//5))
            else:
                temp = now % 5
                heapq.heappush(h, (cost+c+(5-temp)*d, (now+5-temp)//5))
                heapq.heappush(h, (cost+c+temp*d, now//5))


main()

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

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

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

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

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

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

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

    dp = {0:0, 1:d}

    def find_cost(x):
        ls = [a, b, c]
        ss = [2, 3, 5]
        cost = d * x
        for l, s in zip(ls, ss):
            if x in dp:
                return dp[x]
            div, mod = divmod(x,s)
            tmp = mod * d + l
            cost = min(cost, tmp + find_cost(div))
            if mod == 0:
                continue
            tmp = (s - mod)*d + l
            cost = min(cost, tmp + find_cost(div+1))
        dp[x] = cost
        return cost
    print(find_cost(n))

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

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

    def dfs(m, cost):
        if m not in memo or memo[m] > cost:
            memo[m] = cost

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

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

                dfs(0, cost + m * d)

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

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


def solve(n, a, b, c, d):

    return memo[0]


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

    def dfs(m, cost):
        if m not in memo or memo[m] > cost:
            memo[m] = cost

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

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

                dfs(0, cost + m * d)

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

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


def solve(n, a, b, c, d):
    memo = {}

    def dfs(m, cost):
        if m not in memo or memo[m] > cost:
            memo[m] = cost

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

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

                dfs(0, cost + m * d)

    dfs(n, 0)
    return memo[0]


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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





T = I()

@lru_cache(maxsize=None)
def make_kouho(n,A,B,C,D):
  ret1 = [(0,D*n)]
  if n%2 == 0:
    ret2 = [(n//2,A)]
  else:
    ret2 = [((n-1)//2,A+D),((n+1)//2,A+D)]
  if n%3 == 0:
    ret3 = [(n//3,B)]
  else:
    r = n%3
    ret3 = [((n-r)//3,B+D*r),((n+3-r)//3,B+D*(3-r))]
  if n%5 == 0:
    ret5 = [(n//5,C)]
  else:
    r = n%5
    ret5 = [((n-r)//5,C+D*r),((n+5-r)//5,C+D*(5-r))]
  return ret1+ret2+ret3+ret5

@lru_cache(maxsize=None)
def cheepest(n,A,B,C,D):
  if n == 0:
    return 0
  elif n == 1:
    return D
  else:
    return min(cheepest(kouho,A,B,C,D)+cost  for kouho,cost in make_kouho(n,A,B,C,D))
  

for _ in range(T):
  N,A,B,C,D = IL()
  print(cheepest(N,A,B,C,D))

Solution (Python):
from functools import lru_cache


def solve(n, a, b, c, d):

    @lru_cache(maxsize=None)
    def func(n):
        if n == 0:
            return 0
        if n == 1:
            return d
        else:
            
            coin = d * n

            
            div, mod = divmod(n, 2)

            if mod == 0:
                coin = min(coin, func(div) + a)
            else:
                coin = min(coin, func(div) + a + d, func(div + 1) + a + d)

            
            div, mod = divmod(n, 3)

            if mod == 0:
                coin = min(coin, func(div) + b)
            elif mod == 1:
                coin = min(coin, func(div) + b + d, func(div + 1) + b + 2 * d)
            else:
                coin = min(coin, func(div) + b + 2 * d, func(div + 1) + b + d)

            
            div, mod = divmod(n, 5)

            if mod == 0:
                coin = min(coin, func(div) + c)
            elif mod == 1:
                coin = min(coin, func(div) + c + d, func(div + 1) + c + 4 * d)
            elif mod == 2:
                coin = min(coin, func(div) + c + 2 * d, func(div + 1) + c + 3 * d)
            elif mod == 3:
                coin = min(coin, func(div) + c + 3 * d, func(div + 1) + c + 2 * d)
            else:
                coin = min(coin, func(div) + c + 4 * d, func(div + 1) + c + d)

        return coin
    return func(n)


t = int(input())
ans = []
for i in range(t):
    n, a, b, c, d = map(int, input().split())
    ans.append(solve(n, a, b, c, d))

print(*ans, sep="\n")

Solution (Python):
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,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))
    dic[N]=tmp
    return tmp

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

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


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

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

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

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

            dfs(0, cost + m * d)

    dfs(n, 0)
    return memo[0]


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

Solution (Python):
import sys

sys.setrecursionlimit(10**6)


















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

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

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


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

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

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

    return memo[0]

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def dfs(n):
    if n not in memo:
        ans = min(n*d, min(dfs(n//2),dfs((n+1)//2)) + a + d*(n % 2))
        if n % 3 <= 1:
            ans = min(ans, dfs(n//3) + b + d*(n % 3))
        else:
            ans = min(ans, dfs((n+2)//3) + b + d*(3 - n % 3))
        if n % 5 <= 2:
            ans = min(ans, dfs(n//5) + c + d*(n % 5))
        else:
            ans = min(ans, dfs((n+4)//5) + c + d*(5 - n % 5))
        memo[n] = ans
    return memo[n]


t = int(input())

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

Solution (Python):
def dfs(n):
    if n not in memo:
        ans = min(n*d, min(dfs(n//2),dfs((n+1)//2)) + a + d*(n % 2))
        if n % 3 <= 1:
            ans = min(ans, dfs(n//3) + b + d*(n % 3))
        else:
            ans = min(ans, dfs((n+2)//3) + b + d*(3 - n % 3))
        if n % 5 <= 2:
            ans = min(ans, dfs(n//5) + c + d*(n % 5))
        else:
            ans = min(ans, dfs((n+4)//5) + c + d*(5 - n % 5))
        memo[n] = ans
    return memo[n]


t = int(input())

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

Solution (Python):


import heapq


def solve():
  N, A, B, C, D = map(int, input().split())
  seen_values = set()
  queue = []
  heapq.heappush(queue, (0, N))

  while True:
    cost, value = heapq.heappop(queue)

    if value in seen_values:
      continue

    seen_values.add(value)

    if value == 1:
      print(cost + D)
      return

    for k, c in ((2, A), (3, B), (5, C)):
      v, m = divmod(value, k)

      if v == 0:
        continue
      elif m == 0:
        heapq.heappush(queue, (cost + c, v))
      else:
        heapq.heappush(queue, (cost + c + D * m, v))
        heapq.heappush(queue, (cost + c + D * (k - m), v + 1))

      heapq.heappush(queue, (cost + D * (value - v), v))


def main():
  for _ in range(int(input())):
    solve()


if __name__ == '__main__':
  main()

Solution (Python):
T = int(input())
NABCD = [[int(_) for _ in input().split()] for _ in range(T)]
for n, a, b, c, d in NABCD:

    memo = {}
    memo[0] = 0
    memo[1] = d

    def solve(n):
        if n in memo:
            return memo[n]
        ans = n * d
        q, r = divmod(n, 2)
        if r == 0:
            ans = min(ans, a + solve(q))
        else:
            ans = min(ans, a + d + solve(q))
            ans = min(ans, a + d + solve(q + 1))
        q, r = divmod(n, 3)
        if r == 0:
            ans = min(ans, b + solve(q))
        else:
            ans = min(ans, b + r * d + solve(q))
            ans = min(ans, b + (3 - r) * d + solve(q + 1))
        q, r = divmod(n, 5)
        if r == 0:
            ans = min(ans, c + solve(q))
        else:
            ans = min(ans, c + r * d + solve(q))
            ans = min(ans, c + (5 - r) * d + solve(q + 1))
        memo[n] = ans
        return ans

    print(solve(n))

Solution (Python):
def dfs(n):
    if n not in memo:
        ans = min(dfs(n//2) + a + d*(n%2), dfs((n+1)//2) + a + d*(n%2), n*d)
        ans = min(ans, dfs(n//3) + b + d*(n % 3), dfs((n+2)//3) + b + d*(3 - n%3))
        ans = min(ans, dfs(n//5) + c + d*(n % 5), dfs((n+4)//5) + c + d*(5 - n%5))
        memo[n] = ans
    return memo[n]


t = int(input())

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

Solution (Python):
def solve(n):
    if n in memo:
        return memo[n]

    ans = INF
    for i in (-1, 0, 1):
        res = n + i
        if res % 2 == 0:
            tmp = res - (res // 2)
            ans = min(solve(res // 2) + abs(i) * d + min(a, tmp * d), ans)

    for i in (-2, -1, 0, 1, 2):
        res = n + i
        if res % 3 == 0:
            tmp = res - (res // 3)
            ans = min(solve(res // 3) + abs(i) * d + min(b, tmp * d), ans)
          
    for i in (-4, -3, -2, -1, 0, 1, 2, 3, 4):
        res = n + i
        if res % 5 == 0:
            tmp = res - (res // 5)
            ans = min(solve(res // 5) + abs(i) * d + min(c, tmp * d), ans)

    memo[n] = ans
    return ans

INF = 10 ** 30
t = int(input())

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

Solution (Python):
import sys
from collections import deque

def func(t, MAX, dic, num, coin):
  ans = dic.get(num, -1)
  a,b,c,d = t
  
  if ans != -1:
    return ans
  
  ans = sys.maxsize

  if num == 0:
    dic[0] = 0
    MAX = min(coin,MAX)
    return 0

  if num == 1:
    dic[1] = d
    MAX = min(coin + d, MAX)
    return d

  if coin >= MAX:
    return sys.maxsize

  
  if num % 2 == 0:
    a = min((((num) * d) //2), a)
    ans = min(func(t, MAX, dic, num//2, coin+a)+a, ans)
  else:
    tmp_a = a
    a = min((((num+1) * d) //2), a)
    ans = min(func(t, MAX, dic, (num+1)//2, coin+a+d)+a+d, ans)
    
    a = min((((num-1) * d) //2), tmp_a)
    ans = min(func(t, MAX, dic, (num-1)//2, coin+a+d)+a+d, ans)

  if num % 3 == 0:
    b = min(((num)*2*d)//3, b)
    ans = min(func(t, MAX, dic, num//3, coin+b)+b, ans)
  elif num % 3 == 1:
    b = min(((num-1)*2*d)//3, b)
    ans = min(func(t, MAX, dic, (num-1)//3, coin+b+d)+b+d, ans)
  else:
    b = min(((num+1)*2*d)//3, b)
    ans = min(func(t, MAX, dic, (num+1)//3, coin+b+d)+b+d, ans)

  if num % 5 == 0:
    c = min(((num)*4*d)//5, c)
    ans = min(func(t, MAX, dic, num//5, coin+c)+c, ans)
  elif num % 5 <= 2:
    tmp = num % 5
    c = min(((num-tmp)*4*d)//5, c)
    ans = min(func(t, MAX, dic, (num-tmp)//5, coin+c+d*tmp)+c+d*tmp, ans)
  else:
    tmp = 5 - (num % 5)
    c = min(((num+tmp)*4*d)//5, c)
    ans = min(func(t, MAX, dic, (num+tmp)//5, coin+c+d*tmp)+c+d*tmp, ans)
    
  dic[num] = ans
  MAX = min(coin+ans, MAX)
  return ans

def main():
  t = int(input())

  e = []
  f = []
  g = []
  h = []
  j = []

  for i in range(t):
    n,a,b,c,d = map(int,input().split())
    e.append(n)
    f.append(a)
    g.append(b)
    h.append(c)
    j.append(d)

  for i in range(t):
    n = e[i]
    a = f[i]
    b = g[i]
    c = h[i]
    d = j[i]
    
    t = (a,b,c,d)
    

    print(func(t, sys.maxsize, {}, n, 0))
    
main()

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

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

    def cost(N):
        if N in memo:
            return memo[N]
        ans = N * d
        ks = [2, 3, 5]
        abc = [a, b, c]
        for i in range(3):
            k = ks[i]
            coin = abc[i]
            div, mod = divmod(N, k)
            pay = mod * d + coin
            ans = min(ans, pay + cost(div))
            if mod == 0:
                continue
            pay = (k - mod) * d + coin
            ans = min(ans, pay + cost(div + 1))
        memo[N] = ans
        return ans

    print(cost(n))

Solution (Python):


import heapq


def solve():
  N, A, B, C, D = map(int, input().split())
  seen_values = set()
  queue = []
  heapq.heappush(queue, (0, N))

  while True:
    cost, value = heapq.heappop(queue)

    if value in seen_values:
      continue

    seen_values.add(value)

    if value == 1:
      print(cost + D)
      return

    for k, c in ((2, A), (3, B), (5, C)):
      v, m = divmod(value, k)

      if v == 0:
        continue
      elif m == 0:
        heapq.heappush(queue, (cost + c, v))
      else:
        heapq.heappush(queue, (cost + c + D * m, v))
        heapq.heappush(queue, (cost + c + D * (k - m), v + 1))

      heapq.heappush(queue, (cost + D * (value - v), v))


def main():
  for _ in range(int(input())):
    solve()


if __name__ == '__main__':
  main()

Solution (Python):

import sys

sys.setrecursionlimit(2 * 10 ** 6)


def dfs(x):
    global n, d, ops, dp
    if x in dp:
        return dp[x]
    res = d * x
    for num, cost in ops:
        res = min(res, dfs(x // num) + cost + d * (x % num))
        if x % num != 0:
            res = min(res, dfs(x // num + 1) + cost + d * (num - x % num))
    dp[x] = res
    return res


t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    ops = [[2, a], [3, b], [5, c]]
    dp = {0: 0, 1: d}
    print(dfs(n))

Solution (Python):
import sys
readline = sys.stdin.readline
 
INF = 10**30
def calc(k):
    if k in D:
        return D[k]
    if not k:
        return 0
    res = k*d
    if k != k//2 + 1:
        res = min(res, calc(k//2 + 1) + a + d*(2-k%2))
    if k != k//3 + 1:
        res = min(res, calc(k//3 + 1) + b + d*(3-k%3))
    if k != k//5 + 1:
        res = min(res, calc(k//5 + 1) + c + d*(5-k%5))
    
    if k >= 2:
        res = min(res, calc(k//2) + a + d*(k%2))
    if k >= 3:
        res = min(res, calc(k//3) + b + d*(k%3))
    if k >= 5:
        res = min(res, calc(k//5) + c + d*(k%5))
    D[k] = res
    return res
T = int(readline())
Ans = [None]*T
for qu in range(T):
    n, a, b, c, d = map(int, readline().split())
    D = dict()
    Ans[qu] = calc(n)
print('\n'.join(map(str, Ans)))

Solution (Python):
T, *I = map(int, open(0).read().split())

memo = {}
def solve(N):
    if N == 0:
        return 0
    if N == 1:
        return D

    if N in memo:
        return memo[N]

    l2 = (N // 2) * 2
    r2 = -(-N // 2) * 2

    l3 = (N // 3) * 3
    r3 = -(-N // 3) * 3

    l5 = (N // 5) * 5
    r5 = -(-N // 5) * 5

    memo[N] = min(
        N * D,

        abs(l2 - N) * D + A + solve(l2 // 2),
        abs(r2 - N) * D + A + solve(r2 // 2),

        abs(l3 - N) * D + B + solve(l3 // 3),
        abs(r3 - N) * D + B + solve(r3 // 3),

        abs(l5 - N) * D + C + solve(l5 // 5),
        abs(r5 - N) * D + C + solve(r5 // 5),
    )

    return memo[N]

for N, A, B, C, D in zip(*[iter(I)] * 5):
    memo.clear()
    print(solve(N))

Solution (Python):
t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    mem = {}
    def DFS(k):
        tmp = 10**20
        if k==0:
            return 0
        elif k==1:
            return d
        elif k in mem:
            return mem[k]
        if k%2==0:
            tmp = min(DFS(k//2)+min(a, k//2*d), tmp)
        else:
            tmp = min(DFS(k//2)+min(a+d, (k//2+1)*d), tmp)
            tmp = min(DFS(k//2+1)+min(a+d, k//2*d), tmp)
        if k%3==0:
            tmp = min(DFS(k//3)+min(b, k//3*2*d), tmp)
        elif k%3==1:
            tmp = min(DFS(k//3)+min(b+d, (k//3*2+1)*d), tmp)
        else:
            tmp = min(DFS(k//3+1)+min(b+d, (k//3*2+1)*d), tmp)
        if k%5==0:
            tmp = min(DFS(k//5)+min(c, k//5*4*d), tmp)
        elif k%5==1:
            tmp = min(DFS(k//5)+min(c+d, (k//5*4+1)*d), tmp)
        elif k%5==2:
            tmp = min(DFS(k//5)+min(c+2*d, (k//5*4+2)*d), tmp)
        elif k%5==3:
            tmp = min(DFS(k//5+1)+min(c+2*d, (k//5*4+2)*d), tmp)
        else:
            tmp = min(DFS(k//5+1)+min(c+d, (k//5*4+3)*d), tmp)
        mem[k] = tmp
        return tmp
    print(DFS(n))

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
T = int(input())
for _ in range(T):
    N,A,B,C,D=map(int,input().split())
    l=[2,3,5]
    p=[A,B,C]
    mem={}
    def solve(n):
        if n==0:
            return 0
        if n==1:
            return D
        if n in mem:
            return mem[n]
        tmp=n*D
        for i in [2,3,5]:
            z=p[l.index(i)]
            d=n%i
            u=i-d
            if n%i==0:
                tmp=min(tmp,solve(n//i)+z)
            else:
                tmp=min(tmp,solve(n//i)+z+d*D,solve(n//i+1)+z+u*D)
        mem[n]=tmp
        return tmp
    print(solve(N))

Solution (Python):
"""
参考(真似させてもらいました)
https://atcoder.jp/contests/agc044/submissions/13546510
"""



import sys
sys.setrecursionlimit(int(1e6))

def solve(N_,A,B,C,D):
    num = {}
    def saiki(N):
        
        res = N*D
        if N == 0:
            return 0
        elif N == 1:
            return D
        if N in num:
            return num[N]
        
        if N%2 == 0:
            res = min(res,saiki(N//2)+A)
        else:
            res = min(res,saiki((N+1)//2)+A+D,saiki((N-1)//2)+A+D)
        
        if N%3 == 0:
            res = min(res,saiki(N//3)+B)
        else:
            res = min(res,saiki(N//3)+D*(N%3)+B,saiki(N//3+1)+D*(3-N%3)+B)
        
        if N%5 == 0:
            res = min(res,saiki(N//5)+C)
        else:
            res = min(res,saiki(N//5)+D*(N%5)+C,saiki(N//5+1)+D*(5-N%5)+C)
        
        
        num[N] = res

        return res
    
    print(saiki(N))

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

t = int(input())

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

INF = float('inf')
from functools import lru_cache

for n,a,b,c,d in nabcd:

    @lru_cache(None)
    def dfs(now):
        if now == 0:
            return 0
        elif now == 1:
            return d
        elif now == 2:
            return min(d+a, d*2)
        elif now <0:
            return INF

        tmp = now*d

        
        sho = now//2+1
        fusoku = sho*2 - now
        over2 = dfs(sho)+d*fusoku+a

        
        sho = now//2
        amari = now-sho*2
        nver2 = dfs(sho)+d*amari+a

        
        sho = now//3+1
        fusoku = sho*3 - now
        over3 = dfs(sho)+d*fusoku+b

        
        sho = now//3
        amari = now-sho*3
        nver3 = dfs(sho)+d*amari+b

        
        sho = now//5+1
        fusoku = sho*5 - now
        over5 = dfs(sho)+d*fusoku+c

        
        sho = now//5
        amari = now-sho*5
        nver5 = dfs(sho)+d*amari+c

        return min(tmp,over2,nver2,over3,nver3,over5,nver5)

    ans = dfs(n)
    print(ans)

Solution (Python):
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)+B+(3-r3)*D,f((n+4)//5)+C+(5-r5)*D)
            memo[n] = res
            return res
    print(f(N))