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: Accepted

Solution code:
def main():

    T = int(input())

    def dfs(i, A, B, C, D):
        if i not in memo:
            v = i * D
            if i % 2 == 0:
                v = min(v, A + dfs(i//2, A, B, C, D))
            else:
                v = min(v, D + A + dfs((i-1)//2, A, B, C, D))
                v = min(v, D + A + dfs((i+1)//2, A, B, C, D))
            if i % 3 == 0:
                v = min(v, B + dfs(i//3, A, B, C, D))
            else:
                v = min(v, D*(i%3) + B + dfs((i-i%3)//3, A, B, C, D))
                v = min(v, D*(3-i%3) + B + dfs((i+3-i%3)//3, A, B, C, D))
            if i % 5 == 0:
                v = min(v, C + dfs(i//5, A, B, C, D))
            else:
                v = min(v, D*(i%5) + C + dfs((i-i%5)//5, A, B, C, D))
                v = min(v, D*(5-i%5) + C + dfs((i+5-i%5)//5, A, B, C, D))
            memo[i] = v
        return memo[i]

    for _ in range(T):
        N, A, B, C, D = map(int, input().split())
        memo = dict()
        memo[0] = 0
        memo[1] = D

        print(dfs(N, A, B, C, D))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from functools import lru_cache

import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


# @mt
def slv(N, A, B, C, D):
    @lru_cache(maxsize=None)
    def f(n):
        ans = n*D
        for i in range(-min(2, n), min(3, n)):
            m = n + i
            i = abs(i)
            if m == 0:
                continue

            if m % 5 == 0:
                ans = min(ans, f(m//5) + C + D*i)
            if m % 3 == 0:
                ans = min(ans, f(m//3) + B + D*i)
            if m % 2 == 0:
                ans = min(ans, f(m//2) + A + D*i)
        return ans

    return f(N)


def main():
    T = read_int()
    for _ in range(T):
        N, A, B, C ,D = read_int_n()
        print(slv(N, A, B, C, D))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
t = int(input())
import heapq
def tr(pnt,m):
  try:
    if use[m] > pnt:
      heapq.heappush(now,[pnt,m])
      use[m] = pnt
  except:
    heapq.heappush(now,[pnt,m])
    use[m] = pnt
for _ in range(t):
  n,a,b,c,d = map(int,input().split())
  now = [[0,n]]
  use = {}
  ans = n*d
  while True:
    sc,num = heapq.heappop(now)
    ans = min(ans,sc+num*d)
    if num == 1:
      print(ans)
      break

    if num % 2 == 0:
      tr(sc+a,num//2)
    else:
      tr(sc+a+d,(num-1)//2)
      tr(sc+a+d,(num+1)//2)
    
    if num % 3 == 0:
      tr(sc+b,num//3)
    elif num % 3 == 1:
      tr(sc+b+d,(num-1)//3)
    else:
      tr(sc+b+d,(num+1)//3)
    
    if num % 5 == 0:
      tr(sc+c,num//5)
    elif num % 5 == 1:
      tr(sc+c+d,(num-1)//5)
    elif num % 5 == 2:
      tr(sc+c+2*d,(num-2)//5)
    elif num % 5 == 3:
      tr(sc+c+2*d,(num+2)//5)
    else:
      tr(sc+c+d,(num+1)//5)

Submission status: Accepted

Solution code:
T=int(input())
from functools import lru_cache

for _ in range(T):
    N,A,B,C,D=map(int,input().split())
    @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

    print(solve(N))

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10**9)

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

    def dfs(m):
        if m in memo:
            return memo[m]
        else:
            res1 = m * d

            res2 = (m % 2) * d + a + dfs(m // 2)
            res3 = (m % 3) * d + b + dfs(m // 3)
            res4 = (m % 5) * d + c + dfs(m // 5)

            res5 = ((2 - (m % 2)) % 2) * d + a + dfs(
                (m + (2 - (m % 2)) % 2) // 2)
            res6 = ((3 - (m % 3)) % 3) * d + b + dfs(
                (m + (3 - (m % 3)) % 3) // 3)
            res7 = ((5 - (m % 5)) % 5) * d + c + dfs(
                (m + (5 - (m % 5)) % 5) // 5)

            memo[m] = min(res1, res2, res3, res4, res5, res6, res7)
            return memo[m]

    ans = dfs(n)
    print(ans)

Submission status: Accepted

Solution code:
t = int(input())
import heapq
def tr(pnt,m):
  try:
    if use[m] > pnt:
      heapq.heappush(now,[pnt,m])
      use[m] = pnt
  except:
    heapq.heappush(now,[pnt,m])
    use[m] = pnt
inf = 10**18
for _ in range(t):
  n,a,b,c,d = map(int,input().split())
  now = [[0,n]]
  use = {}
  mini = 10**18
  ans = n * d
  while True:
    sc,num = heapq.heappop(now)
    ans = min(ans,sc+d*num)
    if num == 1:
      print(ans)
      break
    if num % 2 == 0:
      tr(sc+a,num//2)
    else:
      tr(sc+a+d,(num-1)//2)
      tr(sc+a+d,(num+1)//2)
    
    if num % 3 == 0:
      tr(sc+b,num//3)
    elif num % 3 == 1:
      tr(sc+b+d,(num-1)//3)
    else:
      tr(sc+b+d,(num+1)//3)
    
    if num % 5 == 0:
      tr(sc+c,num//5)
    elif num % 5 == 1:
      tr(sc+c+d,(num-1)//5)
    elif num % 5 == 2:
      tr(sc+c+2*d,(num-2)//5)
    elif num % 5 == 3:
      tr(sc+c+2*d,(num+2)//5)
    else:
      tr(sc+c+d,(num+1)//5)

Submission status: Accepted

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)


memo = {}

def solve():
    N,A,B,C,D = map(int,input().split())
    global memo
    memo = {0:0,1:D}
    return process(N,N,A,B,C,D)


def process(M,N,A,B,C,D):
    # if M < 0:
    #     return D * N + 1
    global memo
    if M in memo:
        return memo[M]
    res = process((M-M%2)//2,N,A,B,C,D) + A + (M%2) * D
    res = min(res,process((M+M%2)//2,N,A,B,C,D) + A + (M%2) * D)
    res = min(res,process((M-M%3)//3,N,A,B,C,D) + B + (M%3) * D)
    res = min(res,process((M+3-M%3)//3,N,A,B,C,D) + B + (3-M%3) * D)
    res = min(res,process((M-M%5)//5,N,A,B,C,D) + C + (M%5) * D)
    res = min(res,process((M+5-M%5)//5,N,A,B,C,D) + C + (5-M%5) * D)
    res = min(res,M*D)
    memo[M] = res
    return res


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

    for i in range(T):
        res = solve()
        print(res)



main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
	dp = dict()
	dp[n] = 0
	q = [(0, n)]
	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

	while True:
		l = heappop(q)
		if l[1] == 0:
			break
		x = l[1]
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				heappush(q, (v, x//2))
			v = min(a+d, d + d*(x//2+1)) + dp[x]
			if add(x//2+1, v):
				heappush(q, (v, x//2+1))

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

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

	print(dp[0])

Submission status: Accepted

Solution code:
from collections import deque

t = int(input())
cases = [tuple(int(v) for v in input().split()) for _ in range(t)]


def get_simple_price(n, p, d, m):
    price = 0
    while n != 0:
        mod = n % m
        if mod != 0:
            price += mod * d
            n -= mod
        if n != 0:
            price += p
            n //= m
    return price


def discover(n, a, b, c, d):
    # make limit
    limit = min(
        get_simple_price(n, a, d, 2),
        get_simple_price(n, b, d, 3),
        get_simple_price(n, c, d, 5),
        n * d,
    )
    memo = {}

    queue = deque([(n, 0)])
    while len(queue) > 0:
        t, p = queue.pop()
        if t == 0:
            if p < limit:
                limit = p
            continue
        if t == 1:
            queue.append((0, p + d))
            continue
        if t in memo:
            if p < memo[t]:
                memo[t] = p
            else:
                continue
        else:
            memo[t] = p

        queue.append((0, p + t * d))
        mod = t % 2
        queue.append((t // 2, p + a + d * mod))
        if mod != 0:
            queue.append((t // 2 + 1, p + a + d * (2 - mod)))
        mod = t % 3
        queue.append((t // 3, p + b + d * mod))
        if mod != 0:
            queue.append((t // 3 + 1, p + b + d * (3 - mod)))
        mod = t % 5
        queue.append((t // 5, p + c + d * mod))
        if mod != 0:
            queue.append((t // 5 + 1, p + c + d * (5 - mod)))

    return limit


for n, a, b, c, d in cases:
    print(discover(n, a, b, c, d))

Submission status: Accepted

Solution code:
t=int(input())

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

    memo[x]=ans
    return ans

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

Submission status: Accepted

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

def dfs(n):
  if n in dic:
    return dic[n]  
  
  m2=n%2
  if m2==0:
    score_a1=A+dfs(n//2)
    score_a2=A+dfs(n//2)
  else:
    score_a1=m2*D+A+dfs((n-m2)//2)
    score_a2=m2*D+A+dfs((n+(2-m2))//2)

  m3=n%3
  if m3==0:
    score_b1=B+dfs(n//3)
    score_b2=B+dfs(n//3)
  else:
    score_b1=m3*D+B+dfs((n-m3)//3)
    score_b2=(3-m3)*D+B+dfs((n+(3-m3))//3)

  m5=n%5
  if m5==0:
    score_c1=C+dfs(n//5)
    score_c2=C+dfs(n//5)
  else:
    score_c1=m5*D+C+dfs((n-m5)//5)
    score_c2=(5-m5)*D+C+dfs((n+(5-m5))//5)

  score_d=n*D
  ret=min(score_a1,score_a2,score_b1,score_b2,score_c1,score_c2,score_d)
  dic[n]=ret
  return ret

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

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

def calc(nn, a,b,c,d):
    global dp

    if nn in dp :
        return dp[nn]
    if nn == 0:
        return 0
    
    ncost = []
    # /2
    if nn%2 == 0:
        tcost = calc(nn//2, a,b,c,d)
        ncost.append(tcost + min((nn//2)*d , a))
    else:
        tcost = calc((nn-1)//2, a,b,c,d)
        ncost.append(tcost + min(((nn-1)//2)*d + d , a+d))

        tcost = calc((nn+1)//2, a,b,c,d)
        ncost.append(tcost + min(((nn+1)//2)*d + d , a+d))

    # /3
    if nn%3 == 0:
        tcost = calc(nn//3, a,b,c,d)
        ncost.append(tcost + min((nn//3)*2*d , b))
    else:
        m = nn%3
        tcost = calc((nn-m)//3,  a,b,c,d)
        ncost.append(tcost + min(((nn-m)//3)*2*d + d*m , b+d*m) )
        tcost = calc((nn+(3-m))//3, a,b,c,d)
        ncost.append(tcost + min((nn+(3-m))//3*2*d + d*(3-m) , b+d*(3-m)))

    # /5
    if nn%5 == 0:
        tcost = calc(nn//5, a,b,c,d)
        ncost.append(tcost + min((nn//5)*4*d , c))
    else:
        m = nn%5
        tcost = calc((nn-m)//5 , a,b,c,d)
        ncost.append(tcost +  min(((nn-m)//5)*4*d + d*m , c+d*m))
        tcost = calc((nn+(5-m))//5, a,b,c,d)
        ncost.append(tcost +  min((nn+(5-m))//5*4*d + d*(5-m) , c+d*(5-m)))

    mincost = min(ncost) 
    dp[nn] = mincost
    return mincost

t = ii()
ans = []
for i in range(t):
    n,a,b,c,d = mi()
    dp = {}
    dp[1] = d
    ansi = calc(n,a,b,c,d)
    ans.append(ansi)

for i in range(t):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import defaultdict
dic_h = defaultdict(int)
dic_h[0] = 9999999999
dic_h[1] = 8

t = int(input())

cnt = 0
def tk(v,a,b,c,d):
    global cnt,dic_h
    if dic_h[v] != 0 :
        return dic_h[v]
    
    pas1 = v // 2
    if v == 2 :
        pas2 = 0  #無限ループ阻止のため
    else:
        pas2 = pas1 + 1 # vが2の時無限ループになる
    pam1 =  v % 2 
    pam2 = 2 - pam1
    pbs1 = v // 3
    pbs2 = pbs1 + 1
    pbm1 = v % 3 
    pbm2 = 3 -pbm1  
    pcs1 = v // 5
    pcs2 = pcs1 +  1
    pcm1 = v % 5 
    pcm2 = 5 - pcm1

    koho_a1 = tk(pas1,a,b,c,d) + pam1*d + a
    koho_b1 = tk(pbs1,a,b,c,d) + pbm1*d + b
    koho_c1 = tk(pcs1,a,b,c,d) + pcm1*d + c
    koho_a2 = tk(pas2,a,b,c,d) + pam2*d + a
    koho_b2 = tk(pbs2,a,b,c,d) + pbm2*d + b
    koho_c2 = tk(pcs2,a,b,c,d) + pcm2*d + c
    
    ret = min(v*d,koho_a1,koho_a2,koho_b1,koho_b2,koho_c1,koho_c2 ) 
    dic_h[v] = ret
    #print(v,ret)
    return ret

for i in range(t):
    n,a,b,c,d = map(int,input().split())
    #print(n,a,b,c,d)
    dic_h = defaultdict(int)
    dic_h[0] = 9999999999    
    dic_h[1] = d
    print(tk(n,a,b,c,d))

Submission status: Accepted

Solution code:
T = int(input())

testcase = [list(map(int,input().split())) for i in range(T)]

from functools import lru_cache

@lru_cache(maxsize=None)
def f(n,a,b,c,d):
    if n == 0:
        return 0
    if n == 1:
        return d
    else:
        return min((n-5*(n//5)) * d + c + f(n//5,a,b,c,d),(n-3*(n//3)) * d + b + f(n//3,a,b,c,d),(n-2*(n//2)) * d + a + f(n//2,a,b,c,d),
                   (5*((n+4)//5)-n) * d + c + f((n+4)//5,a,b,c,d),(3*((n+2)//3)-n) * d + b + f((n+2)//3,a,b,c,d),(2*((n+1)//2)-n) * d + a + f((n+1)//2,a,b,c,d),n*d)

for n,a,b,c,d in testcase:
    print(f(n,a,b,c,d))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

    
        
t = int(input())
for i in range(t):
    ans = {}
    def sub(n,A,B,C,D):
        if n==1:
            ans[1] = D
            return D
        if n==0:
            return 0
        if n in ans:
            return ans[n]
        v = n * D
        if n%2==0:
            v = min(v, sub(n//2, A, B, C, D)+A)
        else:
            v = min(v, sub(n//2, A, B, C, D)+A+D)
            if n>2:
                v = min(v, sub(n//2+1, A, B, C, D)+A+D)
        if n%3==0:
            v = min(v, sub(n//3, A, B, C, D)+B)
        else:
            if n>=3:
                v = min(v, sub(n//3, A, B, C, D)+B+(n%3)*D)
                v = min(v, sub(n//3+1, A, B, C, D)+B+(3-(n%3))*D)
        if n%5==0:
            v = min(v, sub(n//5, A, B, C, D)+C)
        else:
            if n>=5:
                v = min(v, sub(n//5, A, B, C, D)+C+(n%5)*D)
                v = min(v, sub(n//5+1, A, B, C, D)+C+(5-(n%5))*D)
        ans[n] = v
        return v

    n, A,B,C,D = map(int, input().split())
    print(sub(n,A,B,C,D))
#     print(ans)

Submission status: Accepted

Solution code:
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))
            # 2について
            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))
            # 3について
            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))
            # 5について
            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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
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)]

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

#####Shorten#####
def DD(arg): return defaultdict(arg)


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

######Combination######
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

######Factorization######
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

#####MakeDivisors######
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

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

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

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

#####ChangeBase#####
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))))

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

#############
# Main Code #
#############

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

Submission status: Accepted

Solution code:
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:
            # まずは全てdで増やした場合をセット
            coin = d * n

            # 2倍するケースを試す
            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)

            # 3倍するケースを試す
            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)

            # 5倍するケースを試す
            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")

Submission status: Accepted

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