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:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    t = I()
    aa = [LI() for _ in range(t)]

    rr = []
    for n,a,b,c,dd in aa:
        e = {2: a, 3: b, 5: c}
        def search(s, t):
            d = collections.defaultdict(lambda: inf)
            d[s] = 0
            q = []
            heapq.heappush(q, (0, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if u == t:
                    break
                if v[u]:
                    continue
                v[u] = True

                if d[t] > k + dd * (u-t):
                    d[t] = k + dd * (u-t)
                for ek, ev in e.items():
                    m = u % ek
                    if m == 0:
                        if d[u//ek] > k + ev:
                            d[u//ek] = k + ev
                            heapq.heappush(q, (k+ev, u//ek))
                    else:
                        if d[u//ek + 1] > k + ev + (ek - m) * dd:
                            d[u//ek + 1] = k + ev + (ek - m) * dd
                            heapq.heappush(q, (k + ev + (ek - m) * dd, u//ek + 1))
                        if d[u//ek] > k + ev + m * dd:
                            d[u//ek] = k + ev + m * dd
                            heapq.heappush(q, (k + ev + m * dd, u//ek))

            return d[t]

        rr.append(search(n, 1) + dd)

    return JA(rr, "\n")

print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

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


for test_num in range(T):
    hq = []
    kake_patterns = [2,3,5]
    cost_patterns = [test_cases[test_num][1],test_cases[test_num][2],test_cases[test_num][3]]
    plmi_cost = test_cases[test_num][4]
    heapq.heappush(hq,-test_cases[test_num][0])
    memo = defaultdict(int)
    memo[test_cases[test_num][0]] = 0
    memo[0] = plmi_cost*test_cases[test_num][0]
    
    while len(hq)>0:
        checking = heapq.heappop(hq)
        checking = -checking
        cost = memo[checking]
        
        if checking in [0,1]:
            continue
        for i,kake in enumerate(kake_patterns):
            if checking%kake == 0:
                devided1 = checking//kake
                devided2 = checking//kake
            else:
                devided1 = checking//kake
                devided2 = checking//kake + 1
                
            #devided1 = math.floor(checking/kake)
            #devided2 = math.ceil(checking/kake)
            
            added_cost1 = cost + abs(devided1*kake-checking)*plmi_cost + cost_patterns[i]
            added_cost2 = cost + abs(devided2*kake-checking)*plmi_cost + cost_patterns[i]
            
            if devided1 in memo:
                if added_cost1 < memo[devided1]:
                    memo[devided1] = added_cost1
            else:
                memo[devided1] = added_cost1
                heapq.heappush(hq,-devided1)
            
            if devided2 in memo:
                if added_cost2 < memo[devided2]:
                    memo[devided2] = added_cost2
            else:
                memo[devided2] = added_cost2
                heapq.heappush(hq,-devided2)
            
            if added_cost1 + devided1*plmi_cost < memo[0]:
                memo[0] = added_cost1 + devided1*plmi_cost
            if added_cost2 + devided2*plmi_cost < memo[0]:
                memo[0] = added_cost2 + devided2*plmi_cost
            
    print(memo[0])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10**7)
INF = float("inf")
t = int(input())

def dfs(x):
    if x == 0: return 0
    if x == 1: return d
    if x in memo: return memo[x]
    r2, r3, r5 = x % 2, x % 3, x % 5
    res = d*x
    res = min(dfs(x//2) + c2+r2*d, res)
    if r2: res = min(dfs((x+2)//2) + c2+(2-r2)*d, res)
    res = min(dfs(x//3) + c3+r3*d, res)
    if r3: res = min(dfs((x+3)//3) + c3+(3-r3)*d, res)
    res = min(dfs(x//5) + c5+r5*d, res)
    if r5: res = min(dfs((x+5)//5) + c5+(5-r5)*d, res)
    memo[x] = res
    return res

for _ in range(t):
    memo = dict()
    n, c2, c3, c5, d = map(int, input().split())
    print(dfs(n))

Submission status: Accepted

Solution code:
T = int(input())

for t in range(T):
    N, A, B, C, D = map(int, input().split())
    memo = {}

    def dist(n):
        if n == 0:
            return 0
        if n == 1:
            return D
        if n in memo:
            return memo[n]
        
        ret = min(
            D * n,
            D * abs(n - n//5*5) + C + dist(n//5),
            D * abs(n - (n+4)//5*5) + C + dist((n+4)//5),
            D * abs(n - n//3*3) + B + dist(n//3),
            D * abs(n - (n+2)//3*3) + B + dist((n+2)//3),
            D * abs(n - n//2*2) + A + dist(n//2),
            D * abs(n - (n+1)//2*2) + A + dist((n+1)//2)
        )

        memo[n] = ret
        return ret
    print(dist(N))

Submission status: Accepted

Solution code:
def dfs(n):
    if n == 1:
        return d
    if n == 0:
        return 0
    if n in dic:
        return dic[n]
    ans = min(n * d, dfs(n // 2) + a + (n % 2) * d, dfs((n + 1) // 2) + a + ((-1 * n) % 2) * d, dfs(n // 3) + b + (n % 3) * d, dfs((n + 2) // 3) + b + ((-1 * n) % 3) * d, dfs(n // 5) + c + (n % 5) * d, dfs((n + 4) // 5) + c + ((-1 * n) % 5) * d)
    dic[n] = ans
    return ans
t = int(input())
for i in range(t):
    n, a, b, c, d = map(int, input().split())
    dic = dict()
    print(dfs(n))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

    Q = [(0, N)]
    # already processed
    S = set()
    an = D * N
    while Q:
        cost, num = heappop(Q)
        if num in S:
            continue
        an = min(an, cost + num * D)
        if num == 1:
            break
        S.add(num)

        q, r = divmod(num, 2)
        if r < 2:
            heappush(Q, (cost + A + r * D, q))
        if r > 0:
            heappush(Q, (cost + A + (2 - r) * D, q + 1))

        q, r = divmod(num, 3)
        if r < 2:
            heappush(Q, (cost + B + r * D, q))
        if r > 1:
            heappush(Q, (cost + B + (3 - r) * D, q + 1))

        q, r = divmod(num, 5)
        if r < 3:
            heappush(Q, (cost + C + r * D, q))
        if r > 2:
            heappush(Q, (cost + C + (5 - r) * D, q + 1))
    ans.append(an)

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

    Q = [(0, N)]
    # already processed
    S = set()
    an = D * N
    while Q:
        cost, num = heappop(Q)
        if num in S:
            continue
        an = min(an, cost + num * D)
        if num == 1:
            break
        S.add(num)

        q, r = divmod(num, 2)
        if r < 2:
            heappush(Q, (cost + A + r * D, q))
        if r > 0:
            heappush(Q, (cost + A + (2 - r) * D, q + 1))

        q, r = divmod(num, 3)
        if r < 2:
            heappush(Q, (cost + B + r * D, q))
        if r > 0:
            heappush(Q, (cost + B + (3 - r) * D, q + 1))

        q, r = divmod(num, 5)
        if r < 3:
            heappush(Q, (cost + C + r * D, q))
        if r > 0:
            heappush(Q, (cost + C + (5 - r) * D, q + 1))
    ans.append(an)

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

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
from collections import defaultdict
Inf = 10**28
inpl = lambda: list(map(int,input().split()))
T = int(input())
for _ in range(T):
    N, A, B, C, D = inpl()
    visited = defaultdict(lambda: Inf)
    ans = Inf
    pool = [(0,N)] # coin, number
    while pool:
        c, n = heappop(pool)
        if c >= ans:
            break
        elif c > visited[n]:
            continue
        q = c + D*n
        if q < ans:
            ans = q

        for mag, cost in [(2,A), (3,B), (5,C)]:
            m = (n+mag//2)//mag
            q = c + abs(n - mag*m)*D + cost
            if q < ans and q < visited[m]:
                visited[m] = q
                heappush(pool, (q, m))

    print(ans)

Submission status: Accepted

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

def min2(x, y): return x if x <= y else y

def rec(x):
    if x not in memo:
        ans = D*x
        for d, cost in zip([2, 3, 5], [A, B, C]):
            x2 = x//d
            if x2 != x:
                ans = min2(ans, x%d*D + cost + rec(x2))
            if x%d:
                x2 = (x+d-1)//d
                if x2 != x:
                    ans = min2(ans, (d-x%d)*D + cost + rec(x2))
        memo[x] = ans
    return memo[x]

anss = []
T = int(input())
for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    memo = {}
    ans = rec(N)
    anss.append(ans)

print('\n'.join(map(str, anss)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from functools import lru_cache

def solve(n,a,b,c,d):
    
    @lru_cache(None)
    def f(n):
        if n==0: return 0
        elif n==1: return d
        ret=d*n
        q,r=n//2, n%2
        if r==0:
            ret=min(f(q)+a, ret)
        else:
            ret=min(ret, f(q)+a+d*r, f(q+1)+a+d*r)
        q,r=n//3, n%3
        if r==0:
            ret=min(f(q)+b, ret)
        else:
            ret=min(ret, f(q)+b+d*r, f(q+1)+b+d*(3-r))
        q,r=n//5, n%5
        if r==0:
            ret=min(f(q)+c, ret)
        else:
            ret=min(ret, f(q)+c+d*r, f(q+1)+c+d*(5-r))
        return ret
    
    return f(n)

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

Submission status: Accepted

Solution code:
import sys
import heapq
T = int(input())
from collections import deque
for t in range(T):
  N,A,B,C,D = map(int,input().split())
  q = [(0, N)]
  heapq.heapify(q)
  seen = set()
  while q:
    cost,n = heapq.heappop(q)
    if n in seen:
      continue
    seen.add(n)
    if n == 0:
      print(cost)
      break

    heapq.heappush(q, (cost + n * D, 0))
    if n % 2 == 0:
      heapq.heappush(q, (cost + A, n // 2))
    else:
      heapq.heappush(q, (cost + D + A, (n + 1) // 2))
      heapq.heappush(q, (cost + D + A, (n - 1) // 2))

    if n % 3 == 0:
      heapq.heappush(q, (cost + B, n // 3))
    else:
      rest = n % 3
      heapq.heappush(q, (cost + rest * D + B, (n - rest) // 3))
      heapq.heappush(q, (cost + (3 - rest) * D + B, (n - rest + 3) // 3))

    if n % 5 == 0:
      heapq.heappush(q, (cost + C, n // 5))
    else:
      rest = n % 5
      heapq.heappush(q, (cost + rest * D + C, (n - rest) // 5))
      heapq.heappush(q, (cost + (5 - rest) * D + C, (n - rest + 5) // 5))

Submission status: Accepted

Solution code:
#include <CodeforcesSolutions.h>
#include <ONLINE_JUDGE <solution.cf(contestID = "1360",problemID = "F",method = "GET")>.h>
"""
    Author : thekushalghosh
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
    
def solve():
    n,a,b,c,d = invr()
    memo = {}
    def qw(n):
        if n == 0:
            return 0
 
        if n == 1:
            return d
 
        if n in memo:
            return memo[n]
 
        ret = n * d
 
        if (n % 2 == 0):
            ret = min(ret, a + qw(n // 2))
        else:
            ret = min(ret, (n%2)*d + a + qw(n // 2), (2-n%2)*d + a + qw((n+(2-n%2))//2))
 
        if (n % 3 == 0):
            ret = min(ret, b + qw(n // 3))
        else:
            ret = min(ret, (n%3)*d + b + qw(n // 3), (3-n%3)*d + b + qw((n+(3-n%3))//3))
 
        if (n % 5 == 0):
            ret = min(ret, c + qw(n // 5))
        else:
            ret = min(ret, (n%5)*d + c + qw(n // 5), (5-n%5)*d + c + qw((n+(5-n%5))//5))
        memo[n] = ret
        return ret
    print(qw(n))
        
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################

def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    t = inp()
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
    sys.stdout.close()
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
    return(q)
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
    
main()

Submission status: Accepted

Solution code:
T = int(input())

while(T > 0):
    N, A, B, C, D = map(int, input().split())
    memo = {}
    def d(n):
        if n == 0:
            return 0

        if n == 1:
            return D

        if n in memo:
            return memo[n]

        ret = n * D

        if (n % 2 == 0):
            ret = min(ret, A + d(n // 2))
        else:
            ret = min(ret, (n%2)*D + A + d(n // 2), (2-n%2)*D + A + d((n+(2-n%2))//2))

        if (n % 3 == 0):
            ret = min(ret, B + d(n // 3))
        else:
            ret = min(ret, (n%3)*D + B + d(n // 3), (3-n%3)*D + B + d((n+(3-n%3))//3))

        if (n % 5 == 0):
            ret = min(ret, C + d(n // 5))
        else:
            ret = min(ret, (n%5)*D + C + d(n // 5), (5-n%5)*D + C + d((n+(5-n%5))//5))

        memo[n] = ret
        return ret

    print(d(N))
    T -= 1

Submission status: Accepted

Solution code:
import sys

a = 0
b = 0
c = 0
d = 0
pw = dict()

def minCost(n):
	if n == 0:
		return 0
	if n == 1:
		return d
	if n in pw:
		return pw[n]
	else:
		ns = dict()
		ns[(n // 2) * 2] = 1
		ns[((n + 1) // 2) * 2] = 1
		ns[(n // 3) * 3] = 1
		ns[((n + 2) // 3) * 3] = 1
		ns[(n // 5) * 5] = 1
		ns[((n + 4) // 5) * 5] = 1
		_min = n * d
		for key in ns:
			if key % 2 == 0:
				_min = min(_min, a + int(minCost(key // 2)) + d * abs(n - key))
			if key % 3 == 0:
				_min = min(_min, b + int(minCost(key // 3)) + d * abs(n - key))
			if key % 5 == 0:
				_min = min(_min, c + int(minCost(key // 5)) + d * abs(n - key))
		pw[n] = _min
		return pw[n]

t = int(sys.stdin.readline())
for i in range(0, t):
	line = sys.stdin.readline().split()
	n = int(line[0])
	a = int(line[1])
	b = int(line[2])
	c = int(line[3])
	d = int(line[4])
	pw = dict()
	print(int(minCost(n)))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
 
import heapq
T = int(readline())
from collections import deque
for t in range(T):
  N,A,B,C,D = map(int,readline().split())
  q = [(0, N)]
  heapq.heapify(q)
  seen = set()
  while q:
    cost,n = heapq.heappop(q)
    if n in seen:
      continue
    seen.add(n)
    if n == 0:
      print(cost)
      break
      
    heapq.heappush(q, (cost + n * D, 0))
    if n % 2 == 0:
      heapq.heappush(q, (cost + A, n // 2))
    else:
      heapq.heappush(q, (cost + D + A, (n + 1) // 2))
      heapq.heappush(q, (cost + D + A, (n - 1) // 2))
      
    if n % 3 == 0:
      heapq.heappush(q, (cost + B, n // 3))
    else:
      rest = n % 3
      heapq.heappush(q, (cost + rest * D + B, (n - rest) // 3))
      heapq.heappush(q, (cost + (3 - rest) * D + B, (n - rest + 3) // 3))
      
    if n % 5 == 0:
      heapq.heappush(q, (cost + C, n // 5))
    else:
      rest = n % 5
      heapq.heappush(q, (cost + rest * D + C, (n - rest) // 5))
      heapq.heappush(q, (cost + (5 - rest) * D + C, (n - rest + 5) // 5))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

	if memo[N]:
		return memo[N]

	ret = N*D
	
	up = 2*(-(-N//2))
	down = 2*(N//2)
	ret = min(ret, D*(up-N)+A+solve(up//2))
	ret = min(ret, D*(N-down)+A+solve(down//2))

	up = 3*(-(-N//3))
	down = 3*(N//3)
	
	ret = min(ret, D*(up-N)+B+solve(up//3))
	ret = min(ret, D*(N-down)+B+solve(down//3))

	up = 5*(-(-N//5))
	down = 5*(N//5)
	ret = min(ret, D*(up-N)+C+solve(up//5))
	ret = min(ret, D*(N-down)+C+solve(down//5))

	memo[N] = ret
	return ret

T = INT()
ans = []
for _ in range(T):
	N, A, B, C, D = MAP()
	memo = defaultdict(int)
	ans.append(solve(N))
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
import copy as cp
from collections import deque, OrderedDict

LINF = 1001002003004005006
INF = 1001001001

def VI(N, init=0):
  return [init for _ in range(N)]
def VVI(N, M, init=0):
  return [[init for _ in range(M)] for _ in range(N)]

def VD(N, init=0.0):
  return [init for _ in range(N)]
def VVD(N, M, init=0.0):
  return [[init for _ in range(M)] for _ in range(N)]

def Decimal(x):
  print("{0:.10f}".format(x))

class Pair:
  def __init__(self, x=0, y=0):
    self.first = x
    self.second = y

  def __repr__(self):
    return '{0} {1}'.format(self.first, self.second)

  def __lt__(self, pi):
    return self.first < pi.second

def POW(x, n):
  ret = 1
  while n:
    if n&1:
      ret *= x
    x *= x
    n >>= 1
  return ret

A = 0
B = 0
C = 0
D = 0

mp = OrderedDict({})

def dfs(N):
  global A, B, C, D

  if N in mp:
    return mp[N]

  cost = LINF
  if LINF//D > N:
    cost = D * N

  l = N//2*2
  r = l+2
  if (l//2 < N):
    cost = min(cost, A+(N-l)*D+dfs(l//2))
  if (r//2 < N):
    cost = min(cost, A+(r-N)*D+dfs(r//2))

  l = N//3*3
  r = l+3
  if (l//3 < N):
    cost = min(cost, B+(N-l)*D+dfs(l//3))
  if (r//3 < N):
    cost = min(cost, B+(r-N)*D+dfs(r//3))

  l = N//5*5
  r = l+5
  if (l//5 < N):
    cost = min(cost, C+(N-l)*D+dfs(l//5))
  if (r//5 < N):
    cost = min(cost, C+(r-N)*D+dfs(r//5))

  mp[N] = cost
  return cost


T = int(input().rstrip())

for _ in range(T):
  N, A, B, C, D = map(int, input().rstrip().split())
  mp.clear()
  mp[0] = 0
  mp[1] = D
  ans = dfs(N)
  print(ans)

Submission status: Accepted

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

import heapq
T = int(readline())
from collections import deque
for t in range(T):
  N,A,B,C,D = map(int,readline().split())
  q = [(0, N)]
  heapq.heapify(q)
  seen = set()
  while q:
    cost,n = heapq.heappop(q)
    if n in seen:
      continue
    seen.add(n)
    if n == 0:
      print(cost)
      break
      
    heapq.heappush(q, (cost + n * D, 0))
    if n % 2 == 0:
      heapq.heappush(q, (cost + A, n // 2))
    else:
      heapq.heappush(q, (cost + D + A, (n + 1) // 2))
      heapq.heappush(q, (cost + D + A, (n - 1) // 2))
      
    if n % 3 == 0:
      heapq.heappush(q, (cost + B, n // 3))
    else:
      rest = n % 3
      heapq.heappush(q, (cost + rest * D + B, (n - rest) // 3))
      heapq.heappush(q, (cost + (3 - rest) * D + B, (n - rest + 3) // 3))
      
    if n % 5 == 0:
      heapq.heappush(q, (cost + C, n // 5))
    else:
      rest = n % 5
      heapq.heappush(q, (cost + rest * D + C, (n - rest) // 5))
      heapq.heappush(q, (cost + (5 - rest) * D + C, (n - rest + 5) // 5))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
input = sys.stdin.readline
for _ in range(int(input())):
  N, A, B, C, D = map(int, input().split())
  h = [(0, N)]
  d = dd(lambda: float("inf"))
  d[N] = 0
  vis = set()
  while len(h):
    c, x = hpop(h)
    if x in vis: continue
    vis.add(x)
    if x == 0:
      print(c)
      break
    #print(h)
    if d[0] <= c: continue
    hpush(h, (c + x * D, 0))
    d[0] = min(d[0], c + x * D)
    if d[x // 2] > c + A + (x % 2) * D:
      hpush(h, (c + A + (x % 2) * D, x // 2))
      d[x // 2] = c + A + (x % 2) * D
    if d[-(-x // 2)] > c + A + (x % 2) * D:
      hpush(h, (c + A + (-x % 2) * D, -(-x // 2)))
      d[-(-x // 2)] = c + A + (-x % 2) * D

    if d[x // 3] > c + B + (x % 3) * D:
      hpush(h, (c + B + (x % 3) * D, x // 3))
      d[x // 3] = c + B + (x % 3) * D
    if d[-(x // 3)] > c + B + (-x % 3) * D:
      hpush(h, (c + B + (-x % 3) * D, -(-x // 3)))
      d[-(-x // 3)] = c + B + (-x % 3) * D

    if d[x // 5] > c + C + (x % 5) * D:
      hpush(h, (c + C + (x % 5) * D, x // 5))
      d[x // 5] = c + C + (x % 5) * D
    if d[x // 5] > c + C + (-x % 5) * D:
      hpush(h, (c + C + (-x % 5) * D, -(-x // 5)))
      d[-(-x // 5)] = c + C + (-x % 5) * D

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
 
import heapq
  
T = int(readline())
for t in range(T):
  N,A,B,C,D = map(int,readline().split())
  q = [(0,N)]
  heapq.heapify(q)
  seen = set()
  while q:
    cost,n = heapq.heappop(q)
    if n in seen:
      continue
    if n == 0:
      print(cost)
      break
    seen.add(n)
    heapq.heappush(q, (cost + n * D, 0))
    if n % 2 == 0:
      heapq.heappush(q, (cost + A, n // 2))
    else:
      heapq.heappush(q, (cost + D + A, (n + 1) // 2))
      heapq.heappush(q, (cost + D + A, (n - 1) // 2))
      
    if n % 3 == 0:
      heapq.heappush(q, (cost + B, n // 3))
    else:
      rest = n % 3
      heapq.heappush(q, (cost + rest * D + B, (n - rest) // 3))
      heapq.heappush(q, (cost + (3 - rest) * D + B, (n + (3 - rest)) // 3))
      
    if n % 5 == 0:
      heapq.heappush(q, (cost + C, n // 5))
    else:
      rest = n % 5
      heapq.heappush(q, (cost + rest * D + C, (n - rest) // 5))
      heapq.heappush(q, (cost + (5 - rest) * D + C, (n + (5 - rest)) // 5))

Submission status: Accepted

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

import heapq
  
T = int(readline())
for t in range(T):
  N,A,B,C,D = map(int,readline().split())
  q = [(0,N)]
  heapq.heapify(q)
  seen = set()
  while q:
    cost,n = heapq.heappop(q)
    if n in seen:
      continue
    if n == 0:
      print(cost)
      break
    seen.add(n)
    heapq.heappush(q, (cost + n * D, 0))
    if n % 2 == 0:
      heapq.heappush(q, (cost + A, n // 2))
    else:
      heapq.heappush(q, (cost + D + A, (n + 1) // 2))
      heapq.heappush(q, (cost + D + A, (n - 1) // 2))
      
    if n % 3 == 0:
      heapq.heappush(q, (cost + B, n // 3))
    else:
      rest = n % 3
      heapq.heappush(q, (cost + rest * D + B, (n - rest) // 3))
      heapq.heappush(q, (cost + (3 - rest) * D + B, (n + (3 - rest)) // 3))
      
    if n % 5 == 0:
      heapq.heappush(q, (cost + C, n // 5))
    else:
      rest = n % 5
      heapq.heappush(q, (cost + rest * D + C, (n - rest) // 5))
      heapq.heappush(q, (cost + (5 - rest) * D + C, (n + (5 - rest)) // 5))

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
input = sys.stdin.readline
#S,L,R = map(int, input().split())

def solve(N,A,B,C,D):
    
    dp = {}
    
    def dfs(n):
        if n in dp:
            return dp[n]
        if n<=0:
            return 0
        if n==1:
            return D
        
        R = n*D
        
        #2 floor
        R = min(R,A+D*(n%2)+dfs(n//2))
        
        #2 ceil
        if n%2 != 0:
            R = min(R,A+D*(2-n%2)+dfs((n+2-1)//2))
        
        
        #3 floor
        R = min(R,B+D*(n%3)+dfs(n//3))
        
        #3 ceil
        if n%3 != 0:
            R = min(R,B+D*(3-n%3)+dfs((n+3-1)//3))
        
        
        #5 floor
        R = min(R,C+D*(n%5)+dfs(n//5))
        
        #5 ceil
        if n%5 != 0:
            R = min(R,C+D*(5-n%5)+dfs((n+5-1)//5))
        
        
        dp[n]=R
        return R
    
    return dfs(N)
    

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

Submission status: Accepted

Solution code:
def solve(N, A, B, C, D, memo):
    if N in memo:
        return memo[N]
    ans = D * N
    if N <= 1:
        memo[N] = ans
        return ans
    divs = [(2, A), (3, B), (5, C)]
    for divider, divcost in divs:
        delta = N % divider
        if delta:
            ans = min(ans, solve(N // divider, A, B, C, D, memo) +
                      divcost + D * delta)
            ans = min(ans, solve(N // divider + 1, A, B, C, D, memo) +
                      divcost + D * (divider - delta))
        else:
            ans = min(ans, solve(N // divider, A, B, C, D, memo) + divcost)
    memo[N] = ans
    return ans


def main():
    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)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
t=int(input())
for _ in range(t):
    n,a,b,c,d=map(int,input().split())
    dp=dict()
    dp[n]=0
    que=[[0,n]] # [cost, present_number]

    def dp_revise(x,v):
        if x not in dp.keys():
            dp[x]=v
            return True
        elif dp[x]>v:
            dp[x]=v
            return True
        else: 
            return False

    while que:
        p=heapq.heappop(que)
        if p[1]==0: 
            break
        x=p[1]
        r2=x%2
        v=min(a+r2*d, d*(x//2+r2))+dp[x] # compare doA or doD to reach x//2
        if dp_revise(x//2,v):
            heapq.heappush(que,[v,x//2])
        if r2!=0:
            v=min(a+d, d+d*(x//2+1))+dp[x] # compare doA or doD to reach x//2
            if dp_revise(x//2+1,v):
                heapq.heappush(que,[v,x//2+1])
        r3=x%3
        v=min(b+r3*d, d*(x//3)*2+r3*d)+dp[x] # compare doB or doD to reach x//3
        if dp_revise(x//3,v):
            heapq.heappush(que,[v,x//3])
        if r3!=0:
            v=min(b+(3-r3)*d, d*(x//3+1)*2+(3-r3)*d)+dp[x] # compare doB or doD to reach x//3
            if dp_revise(x//3+1,v):
                heapq.heappush(que,[v,x//3+1])
        r5=x%5
        v=min(c+r5*d, d*(x//5)*4+r5*d)+dp[x] # compare doC or doD to reach x//5
        if dp_revise(x//5,v):
            heapq.heappush(que,[v,x//5])
        if r5!=0:
            v=min(c+(5-r5)*d, d*(x//5+1)*4+(5-r5)*d)+dp[x] # compare doC or doD to reach x//5
            if dp_revise(x//5+1,v):
                heapq.heappush(que,[v,x//5+1])
            
    print(dp[0])

Submission status: Accepted

Solution code:
'''
5
29384293847243 454353412 332423423 934923490 1
'''
import sys
import heapq
from collections import defaultdict
read = sys.stdin.buffer.read

N, *r = map(int, read().split())
r=iter(r)
Querys=zip(r,r,r,r,r)

cost=defaultdict(lambda :10**27)
que=0
ans=0
def push(n,c):
    global ans
    if n not in cost:
        heapq.heappush(que,(c,n))
    cost[n]=min(cost[n],c)
    ans=min(ans,c+n*d)
    
for n,a,b,c,d in Querys:
    cost.clear()
    cost[n]=0
    ans=n*d
    que=[(0,n)]#number

    #1になるのに最小のものを見つける
    while que:
        C,n=heapq.heappop(que)
        C=cost[n]
        if n==1 or cost[n]<C:
            continue
        # 2で割る
        if n%2==0:
            push(n//2,C+a)
        else:
            push(n//2,C+a+d)
            push(n//2+1,C+a+d)
        # 3
        if n<3:
            continue
        if n%3==0:
            push(n//3,C+b)
        if n%3==1:
            push(n//3,C+b+d)
        if n%3==2:
            push(n//3+1,C+b+d)
        # 5
        if n<5:
            continue
        if n%5==0:
            push(n//5,C+c)
        if n%5==1:
            push(n//5,C+c+d)
        if n%5==2:
            push(n//5,C+c+2*d)
        if n%5==3:
            push(n//5+1,C+c+2*d)
        if n%5==4:
            push(n//5+1,C+c+d)
    print(ans)