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 sys

sys.setrecursionlimit(10**6)

# def dfs(t,ans):
#     global a,b,c,d fin
#     if t % 5 == 0:
#         if c > 4*t//5 * d:
#             fin = min(fin,ans+4*t//5*d)
#         else:
#             dfs(t//5,ans+c)
#     if t % 3 == 0:
#         if b > 2*t//3 * d:
#             fin = min(fin,ans+2*t//3*d)
#         else:
#             dfs(t//3,ans+b)
#     if t % 2 == 0:
#         if a > t//2 * d:
#             fin = min(fin,ans+t//2*d)
#         else:
#             dfs(t//2,ans+a)
def solve(t,ans):
    global a,b,c,d,fin,al,dic1
    # print(t)
    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:
        fa,fb,fc = 1,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:
            fa = 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 fa == 1:
                fa = 0
                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)
        # while fa or fb or fc:
        #     u = t+cnt
        #     ans_temp = ans + d*abs(i)
        #     if u % 5 == 0:
        #         if c > 4*u//5 * d:
        #             fin = min(fin,ans_temp+u*d)
        #         else:
        #             solve(u//5,ans_temp+c)
        #     if u % 3 == 0:
        #         if b > 2*u//3 * d:
        #             fin = min(fin,ans_temp+u*d)
        #         else:
        #             solve(u//3,ans_temp+b)
        #     if u % 2 == 0:
        #         if a > u//2 * d:
        #             fin = min(fin,ans_temp+u*d)
        #         else:
        #             solve(u//2,ans_temp+a)
            # if u == 1:
            #     fin = min(fin,ans_temp+d)
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)

Submission status: Accepted

Solution code:
#! /usr/bin/env python3

import sys
sys.setrecursionlimit(10 ** 6)

tt = int(input())
for _ in range(tt):
    n, a, b, c, d = map(int, input().split())
    memo = {}
    def solve(k):
        if k == 0:
            return 0
        elif k == 1:
            return d
        elif k in memo:
            return memo[k]
        else:
            res = k * d
            r = k % 2
            for x in [k - r, k - r + 2]:
                if x >= 1 and x // 2 < k:
                    res = min(res, d * abs(k - x) + a + solve(x // 2))
            r = k % 3
            for x in [k - r, k - r + 3]:
                if x >= 1 and x // 3 < k:
                    res = min(res, d * abs(k - x) + b + solve(x // 3))
            r = k % 5
            for x in [k - r, k - r + 5]:
                if x >= 1 and x // 5 < k:
                    res = min(res, d * abs(k - x) + c + solve(x // 5))
            memo[k] = res
            return memo[k]
    print(solve(n))

Submission status: Accepted

Solution code:
import heapq
import bisect
T = int(input())
lis = [[int(i) for i in input().split()] for _ in range(T)]

w = [2,3,5]


for l in lis:
    n = l[0]
    q = [-n,-1]
    heapq.heapify(q)
    d = {2:l[1],3:l[2],5:l[3],1:l[4]}
    clis = [0,(n-1)*d[1],n*d[1]]
    mlis = [-n,-1,0]
    while True:
        m = heapq.heappop(q)
        if -1 <= m:
            clis[-1] = min([clis[-1],clis[-2]+d[1]])
            break
        ind = bisect.bisect_left(mlis,m)
        clis[-1] = min([clis[-1],clis[ind]-m*d[1]])
        c = clis[bisect.bisect_left(mlis,m)]
        for i in w:
            x = m//i
            y = m%i
            ind = bisect.bisect_left(mlis,x)
            if mlis[ind] == x:
                clis[ind] = min([clis[ind],c +d[i]+ d[1]*y])
            else:
                mlis.insert(ind,x)
                clis.insert(ind,c +d[i]+ d[1]*y)
                heapq.heappush(q,x)
            if y != 0:
                ind = bisect.bisect_left(mlis,x+1)
                if mlis[ind] == x+1:
                    clis[ind] = min([clis[ind],c+d[i]+d[1]*(i-y)])
                else:
                    mlis.insert(ind,x+1)
                    clis.insert(ind,c+d[i]+d[1]*(i-y))
                    heapq.heappush(q,x+1)

    print(clis[-1])

Submission status: Accepted

Solution code:
for i in range(int(input())):
    N,A,B,C,D=map(int,input().split())
    memo={}
    memo[0]=0
    memo[1]=D
    def dfs(num):
        global A,B,C,D
        if num in memo:
            return memo[num]
        res=D*num
        for i in range(-1,2):
            nv=num+i
            if nv%2==0:
                res=min(res,D*abs(i)+A*(nv//2!=0)+dfs(nv//2))
        for i in range(-2,3):
            nv=num+i
            if nv%3==0:
                res=min(res,D*abs(i)+B*(nv//3!=0)+dfs(nv//3))
        for i in range(-4,5):
            nv=num+i
            if nv%5==0:
                res=min(res,D*abs(i)+C*(nv//5!=0)+dfs(nv//5))
        memo[num]=0
        memo[num]=res
        return memo[num]

    print(dfs(N))

Submission status: Accepted

Solution code:
DP = {}

def solve(n, a, b, c, d):
    if n <= 0: 
        return 0
    if n == 1:
        return d
    if n in DP:
        return DP[n]
    ans = float('inf')
    for i in range(-3, 4):
        num = n + i
        trash = abs(i)*d
        if num < 0:
            continue
        if num%5 == 0 and num // 5 < n:
            ans = min(ans, solve(num//5, a, b, c, d) + min(c, d*(num-(num//5))) + trash)
        if num%3 == 0 and num // 3 < n:
            ans = min(ans, solve(num//3, a, b, c, d) + min(b, d*(num-(num//3))) + trash)
        if num%2 == 0 and num // 2 < n:
            ans = min(ans, solve(num//2, a, b, c, d) + min(a, d*(num-(num//2))) + trash)
        # print(str(n) + ' ' + str(ans) + ' ' + str(num) + ' ' + str(i))
    DP[n] = int(ans)

    return int(ans)

def solve2():
    DP.clear()
    ans = float('inf')
    n, a, b, c, d = map(int, input().split())
    # for i in range(0, 65):
    #     for j in range(0, 30):
    #             for k in range(0, 10):
    #                 val = pow(2, i)*pow(3, j)*pow(5, k)
    #                 ans = min(ans, a*i + b*j + c*k + abs(n - val)*(d))
    # print(ans)
                    
    print(solve(n, a, b, c,d))
    
t = int(input())
for _ in range(t):
    solve2()

Submission status: Accepted

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

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


inf = float('Inf')
f = [2, 3, 5]
cost = [0]*4


d = dict()


def dfs(x, d):
    if x in d:
        return(d[x])
    ret = cost[-1]*x
    for i in range(3):
        if x < f[i]:
            continue
        if x % f[i] == 0:
            ret = min(ret, dfs(x // f[i], d) + cost[i])
        else:
            k = x // f[i]
            ret = min(ret, cost[i] + dfs(k, d) + (x %
                                                  f[i]) * cost[-1], cost[i] + dfs(k+1, d) + ((k+1)*f[i]-x)*cost[-1])
    d[x] = ret
    return(ret)


def main():
    T = int(input())
    for _ in range(T):
        N, *c = map(int, input().split())
        for i in range(4):
            cost[i] = c[i]
        print(dfs(N, dict()))


main()

Submission status: Accepted

Solution code:
t=int(input())
for loopi in range(t):
  n,a,b,c,d=list(map(int,input().split()))
  minest=10**40
  dd={n:0}
  while 1:
    newd={}
    for i in dd:
      if i%2:
        l=int((i-1)//2)
        if l in newd:
          newd[l]=min(dd[i]+min(a+d,(i-l)*d),newd[l])
        else:
          newd[l]=dd[i]+min(a+d,(i-l)*d)
        l=int((i+1)//2)
        if l in newd:
          newd[l]=min(dd[i]+min(a+d,(i-l)*d),newd[l])
        else:
          newd[l]=dd[i]+min(a+d,(i-l)*d)
      else:
        l=int(i//2)
        if l in newd:
          newd[l]=min(dd[i]+min(a,l*d),newd[l])
        else:
          newd[l]=dd[i]+min(a,l*d)
      l=int((i-(i+1)%3+1)//3)
      if l in newd:
        newd[l]=min(dd[i]+min(d*((i+1)%3-1)**2+b,(i-l)*d),newd[l])
      else:
        newd[l]=dd[i]+min(d*((i+1)%3-1)**2+b,(i-l)*d)
      l=int((i-(i+2)%5+2)//5)
      if l in newd:
        newd[l]=min(dd[i]+min(d*int((((i+2)%5-2)**2)**0.5)+c,(i-l)*d),newd[l])
      else:
        newd[l]=dd[i]+min(d*int((((i+2)%5-2)**2)**0.5)+c,(i-l)*d)
    if 1 in newd:
      mmm=newd.pop(1)
      if minest>mmm:
        minest=mmm
    if 0 in newd:
      newd.pop(0)
    if len(newd)==0:
      break
    dd=newd
  print(minest+d)

Submission status: Accepted

Solution code:
a,b,c,d=0,0,0,0
dic={}
def solve(n):
    if n not in dic.keys():
        if n%2:
            cand1=min(solve((n+1)//2),solve((n-1)//2))+a+d
        else:
            cand1=solve(n//2)+a
        if n%3==0:
            cand2=solve(n//3)+b
        elif n%3==1:
            cand2=solve((n-1)//3)+b+d
        elif n%3==2:
            cand2=solve((n+1)//3)+b+d
        if n%5==0:
            cand3=solve(n//5)+c
        elif n%5==1:
            cand3=solve((n-1)//5)+c+d
        elif n%5==2:
            cand3=solve((n-2)//5)+c+d*2
        elif n%5==3:
            cand3=solve((n+2)//5)+c+d*2
        elif n%5==4:
            cand3=solve((n+1)//5)+c+d
        dic[n]=min(cand1,cand2,cand3,n*d)
    return dic[n]


t=int(input())
for cas in range(t):
    n,a,b,c,d=map(int,input().split())
    dic={}
    dic[1] = d
    dic[2] = min(d*2,d+a)
    dic[3] = min(min(d*2,d+a)+d,d+b)
    dic[4] = min(min(d*2,d+a)+a,min(min(d*2,d+a)+d,d+b)+d)
    dic[5] = min(d+c,min(min(d*2,d+a)+a,min(min(d*2,d+a)+d,d+b)+d)+d)
    print(solve(n))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
def cur(n):
    if n not in dic:
        if n%2==0:
            m=n//2
            n1=cur(m)+ min(a,d*(n-m))
        else:
            n1=min(cur(n//2)+min(a+d,d*(n-n//2)),cur(n//2+1)+a+d)

        if n%3==0:
            m=n//3
            n2=cur(m)+ min(b,d*(n-m))
        else:
            n2=min(cur(n//3)+min(b+d*(n%3),d*(n-n//3)) ,cur(n//3+1)+b+d*(3-n%3))

        if n%5==0:
            m=n//5
            n3=cur(m)+ min(c,d*(n-m))
        else:
            n3=min(cur(n//5)+ min(c+d*(n%5),d*(n-n//5) ) ,cur(n//5+1)+c+d*(5-n%5))
        dic[n]=min(n1,n2,n3)
    return dic[n]

t=int(input())
for _ in range(t):
    p,a,b,c,d=map(int,input().split())
    tmpdic=defaultdict(lambda: 10**15)
    tmpdic[0]=0;tmpdic[1]=d;tmpdic[2]=min(2*d,a+d)
    s=(1,2)
    for _ in range(7):
        ss=set()
        for x in s:
            tmpdic[2*x]=min(tmpdic[2*x],tmpdic[x]+a);ss.add(2*x)
            tmpdic[3*x]=min(tmpdic[3*x],tmpdic[x]+b);ss.add(3*x)
            tmpdic[5*x]=min(tmpdic[5*x],tmpdic[x]+c);ss.add(5*x)
            tmpdic[x+1]=min(tmpdic[x+1],tmpdic[x]+d);ss.add(x+1)
            tmpdic[x-1]=min(tmpdic[x-1],tmpdic[x]+d)
            if x-1>2: ss.add(x-1)
        s=ss
    dic={0:0,1:d,2:min(2*d,a+d)}
    for i in range(3,11):
        dic[i]=min(tmpdic[i],i*d)
    print(cur(p))

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def dijkstra(src):
    from heapq import heappush, heappop

    que = [(0, src)]
    dist = {}
    dist[src] = 0
    while que:
        cost, u = heappop(que)
        if u >= 5:
            x = u % 5
            v = (u-x) // 5
            if v not in dist or cost+c+d*x < dist[v]:
                dist[v] = cost+c+d*x
                heappush(que, (cost+c+d*x, v))
            if u % 5 != 0:
                x = 5 - u % 5
                v = (u+x) // 5
                if v not in dist or cost+c+d*x < dist[v]:
                    dist[v] = cost+c+d*x
                    heappush(que, (cost+c+d*x, v))
        if u >= 3:
            x = u % 3
            v = (u-x) // 3
            if v not in dist or cost+b+d*x < dist[v]:
                dist[v] = cost+b+d*x
                heappush(que, (cost+b+d*x, v))
            if u % 3 != 0:
                x = 3 - u % 3
                v = (u+x) // 3
                if v not in dist or cost+b+d*x < dist[v]:
                    dist[v] = cost+b+d*x
                    heappush(que, (cost+b+d*x, v))
        if u >= 2:
            x = u % 2
            v = (u-x) // 2
            if v not in dist or cost+a+d*x < dist[v]:
                dist[v] = cost+a+d*x
                heappush(que, (cost+a+d*x, v))
            if u % 2 != 0:
                x = 2 - u % 2
                v = (u+x) // 2
                if v not in dist or cost+a+d*x < dist[v]:
                    dist[v] = cost+a+d*x
                    heappush(que, (cost+a+d*x, v))
    return dist

for _ in range(INT()):
    N, a, b, c, d = MAP()

    res = dijkstra(N)
    ans = INF
    for u, cost in res.items():
        ans = min(ans, cost + abs(u) * d)
    print(ans)

Submission status: Accepted

Solution code:
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    T =iRaw()
    for t in range(T):
        N,A,B,C,D = isRaw()
        hq = []
        limitAns = min([
            int(math.log(N,2)+1)*A,
            int(math.log(N,3)+1)*B,
            int(math.log(N,5)+1)*C
        ])
        heappush(hq,(0,N))

        memo = {}
        memo[N]=0

        ans = N*D
        divcs = [[2,A],[3,B],[5,C]]
        while True:
            cC,cN = heappop(hq)
            memo[cN] = cC
            ans = min(ans,cC+D*cN)
            if cN  == 0:
                ans = min(cC,ans)
                break
            if cN == 1:
                ans = min(cC+D, ans)
                break
            for divc in divcs:
                div,dc = divc
                nM = cN % div
                nN = cN // div
                #if nM <= div//2:
                if True:
                    nC = cC+dc+(D*(cN % div))
                    if nN not in memo or memo[nN] > nC:
                        memo[nN] = nC
                        heappush(hq, (nC, nN))
                if nM!=0:
                    nN = nN+1
                    nC = cC+dc+(D*(div-nM))
                    if nN not in memo or memo[nN] > nC:
                        memo[nN] = nC
                        heappush(hq, (nC, nN))

        print(ans)

main()

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def dfs(n):
    global h
    if n in h:
        return h[n]
    #ddprint(f"dfs {n}")
    if n==1:
        return d
    v1 = n*d
    v3 = v5 = BIG
    if n%2==1:
        v2a = dfs((n-1)//2)+a+d
        v2b = dfs((n+1)//2)+a+d
        v2 = min(v2a,v2b)
    else:
        v2 = dfs(n//2)+a

    if n>=3:
        r = n%3
        if r<=1:
            v3 = dfs((n-r)//3)+b+r*d
        else:
            v3 = dfs((n+1)//3)+b+d

    if n>=5:
        r = n%5
        if r<=2:
            #ddprint(f"dfs {n} v5 b {b} r {r} d {d}")
            v5 = dfs((n-r)//5)+c+r*d
        else:
            v5 = dfs((n+5-r)//5)+c+(5-r)*d

    ret = min([v1,v2,v3,v5])
    h[n] = ret
    #ddprint(f"dfs {n} v1235 {v1} {v2} {v3} {v5} rtn {ret}")
    return ret

k = 400
def foo(n):
    if n<=k:
        return dfs(n)
    v1 = n*d
    m = n
    sm = 0
    while m>k:
        if m%2==1:
            if m%4==1:
                m -= 1
            else:
                m += 1
            sm += d
        m //= 2
        sm += a
    v2 = dfs(m)+sm

    m = n
    sm = 0
    while m>k:
        r = m%3
        if r==1:
            m -= 1
            sm += d
        elif r==2:
            m += 1
            sm += d
        m //= 3
        sm += b
    v3 = dfs(m)+sm

    m = n
    sm = 0
    while m>k:
        r = m%5
        if r<=2:
            m -= r
            sm += r*d
        else:
            m += 5-r
            sm += (5-r)*d
        m //= 5
        sm += c
    v5 = dfs(m)+sm

    #ddprint(f"foo v1235 {v1} {v2} {v3} {v5}")
    return min([v1,v2,v3,v5])

t = inn()
for tt in range(t):
    n,a,b,c,d = inm()
    h = {}
    print(dfs(n))

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
from collections import defaultdict
from math import log,floor

def solve(N,A,B,C,D):
    memo = defaultdict(lambda: float('inf'))
    memo[N] = 0
    q = [(0, N)]
    best = float('inf')
    while q:
        cost, u = heappop(q)
        if cost > memo[u] or cost > best:
            continue
        if u == 1:
            best = min(best, cost+D)



        for dc, nu, flag in (
            (A+D*(u%2), u//2, True),
            (A+D, u//2+1, u%2==1),
            (B+D*(u%3), u//3, u%3 <= 1),
            (B+D, u//3+1, u%3 > 1),
            (C+D*(u%5), u//5, u%5<=2),
            (C+D*((-u)%5), u//5+1, u%5>2)):
            if not flag:
                continue
            nc = cost+min(dc,(u-nu)*D)
            if memo[nu] > nc:
                memo[nu] = nc
                heappush(q, (nc,nu))
    return best
def solve2(N,A,B,C,D):
    pass


T = int(input())

for _ in range(T):
    print(solve(*map(int,input().split())))

Submission status: Accepted

Solution code:
t = int(input())

for i in range(t):
    n,a,b,c,d = map(int, input().split())
    dp = dict()
    dp[0] = 0
    def solve(now):
        if now in dp:
            return dp[now]
        if now == 1:
            dp[now] = d
            return d
        res = d*now
        if now%2 == 0:
            res = min(res,solve(now//2)+a)
        else:
            res = min(res,min(solve((now+1)//2),solve((now-1)//2))+a+d)
        if now%3 == 0:
            res = min(res,solve(now//3)+b)
        else:
            if now//3:
                res = min(res,min(solve(now//3)+d*(now%3),solve(now//3+1)+d*(3-now%3))+b)
            else:
                res = min(res,d*(now%3),d*(4-now%3)+b)
        if now%5 == 0:
            res = min(res,solve(now//5)+c)
        else:
            if now//5:
                res = min(res,min(solve(now//5)+d*(now%5),solve(now//5+1)+d*(5-now%5))+c)
            else:
                res = min(res, d*(now%5),d*(6-now%5)+c)
        dp[now] = res
        return res
    print(solve(n))

Submission status: Accepted

Solution code:
import heapq
T = int(input())

for loop in range(T):

    N,A,B,C,D = map(int,input().split())

    q = [(0,N)]
    end = {}
    ans = D * N
    dl = {}

    while len(q) > 0:

        tmp = heapq.heappop(q)
        dis,num = tmp

        if num in end:
            continue
        end[num] = 1


        if dis > ans:
            print (ans)
            break
        if num == 0:
            print (dis)
            break
        ans = min( ans , dis + num * D )
        

        nc = A
        xx = 2
        nd = num % xx
        if (num-nd)//xx not in end:
            if nd != 0 and (num-nd) == 0:
                dl[num-nd] = dis + num * D
                heapq.heappush(q , (dis + num * D,0))
            if (num-nd)//xx not in dl or dl[(num-nd)//xx] > dis+nc+nd*D:
                dl[(num-nd) // xx] = dis+nc+nd*D
                heapq.heappush(q , (dis+nc+nd*D , (num-nd) // xx))
        nd = xx - num % xx
        if (num+nd)//xx not in end:
            if (num+nd)//xx not in dl or dl[(num+nd)//xx] > dis+nc+nd*D:
                dl[(num+nd) // xx] = dis+nc+nd*D
                heapq.heappush(q , (dis+nc+nd*D , (num+nd) // xx))
        
        nc = B
        xx = 3
        nd = num % xx
        if (num-nd)//xx not in end:
            if nd != 0 and (num-nd) == 0:
                dl[num-nd] = dis + num * D
                heapq.heappush(q , (dis + num * D,0))
            if (num-nd)//xx not in dl or dl[(num-nd)//xx] > dis+nc+nd*D:
                dl[(num-nd) // xx] = dis+nc+nd*D
                heapq.heappush(q , (dis+nc+nd*D , (num-nd) // xx))
        nd = xx - num % xx
        if (num+nd)//xx not in end:
            if (num+nd)//xx not in dl or dl[(num+nd)//xx] > dis+nc+nd*D:
                dl[(num+nd) // xx] = dis+nc+nd*D
                heapq.heappush(q , (dis+nc+nd*D , (num+nd) // xx))
        
        nc = C
        xx = 5
        nd = num % xx
        if (num-nd)//xx not in end:
            if nd != 0 and (num-nd) == 0:
                dl[num-nd] = dis + num * D
                heapq.heappush(q , (dis + num * D,0))
            if (num-nd)//xx not in dl or dl[(num-nd)//xx] > dis+nc+nd*D:
                dl[(num-nd) // xx] = dis+nc+nd*D
                heapq.heappush(q , (dis+nc+nd*D , (num-nd) // xx))
        nd = xx - num % xx
        if (num+nd)//xx not in end:
            if (num+nd)//xx not in dl or dl[(num+nd)//xx] > dis+nc+nd*D:
                dl[(num+nd) // xx] = dis+nc+nd*D
                heapq.heappush(q , (dis+nc+nd*D , (num+nd) // xx))

Submission status: Accepted

Solution code:
from functools import lru_cache
T = int(input())
for _ in range(T):
    @lru_cache(maxsize=None)
    def f(n):
        if n == 0:
            return 0
        if n == 1:
            return D
        if n == 2:
            return min(2*D, A+D)
        temp = [D * n]
        d = n % 2
        temp.append(f(n // 2) + A + D * d)
        temp.append(f(n // 2 + 1) + A + D * (2-d))
        d = n % 3
        temp.append(f(n // 3) + B + D * d)
        temp.append(f(n // 3 + 1) + B + D * (3-d))
        d = n % 5
        temp.append(f(n // 5) + C + D * d)
        temp.append(f(n // 5 + 1) + C + D * (5-d))
        return min(temp)
    N, A, B, C, D = map(int, input().split())
    print(f(N))

Submission status: Accepted

Solution code:
T=int(input())
ABCD=[list(map(int,input().split())) for i in range(T)]
from collections import deque
for N,a,b,c,d in ABCD:
    dic={N:0}
    q=deque([N])
    while q:
        n=q.popleft()
        x=dic[n]
        if n%2:
            if (n-1)//2 not in dic or min(x+a+d,x+(n-(n-1)//2)*d)<dic[(n-1)//2]:
                dic[(n-1)//2]=min(x+a+d,x+(n-(n-1)//2)*d)
                q.append((n-1)//2)
            if (n+1)//2 not in dic or x+a+d<dic[(n+1)//2]:
                dic[(n+1)//2]=x+a+d
                q.append((n+1)//2)
            if n-1==0:
                dic[0]=min(dic[0],x+d)
        else:
            if n//2 not in dic or x+a<dic[n//2]:
                dic[n//2]=x+a
                q.append(n//2)
        if n%3:
            y=n-n//3*3
            if (n-y)//3 not in dic or min(x+b+d*y,x+(n-(n-y)//3)*d)<dic[(n-y)//3]:
                dic[(n-y)//3]=min(x+b+d*y,x+(n-(n-y)//3)*d)
                q.append((n-y)//3)
            if (n+3-y)//3 not in dic or x+b+d*(3-y)<dic[(n+3-y)//3]:
                dic[(n+3-y)//3]=x+b+d*(3-y)
                q.append((n+3-y)//3)
            if n-y==0:
                dic[0]=min(dic[0],x+d*y)
        else:
            if n//3 not in dic or x+b<dic[n//3]:
                dic[n//3]=x+b
                q.append(n//3)
        if n%5:
            y=n-n//5*5
            if (n-y)//5 not in dic or min(x+c+d*y,x+(n-(n-y)//5)*d)<dic[(n-y)//5]:
                dic[(n-y)//5]=min(x+c+d*y,x+(n-(n-y)//5)*d)
                q.append((n-y)//5)
            if (n+5-y)//5 not in dic or x+c+d*(5-y)<dic[(n+5-y)//5]:
                dic[(n+5-y)//5]=x+c+d*(5-y)
                q.append((n+5-y)//5)
            if n-y==0:
                dic[0]=min(dic[0],x+d*y)
        else:
            if n//5 not in dic or x+c<dic[n//5]:
                dic[n//5]=x+c
                q.append(n//5)
    print(dic[0])

Submission status: Accepted

Solution code:
import sys
import collections
import heapq

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()


INF = 1 << 62


def solve():
    N, A, B, C, D = nm()
    ans = D * N  # worst case
    mem = collections.defaultdict(lambda: INF)
    q = []
    heapq.heappush(q, (0, N))
    while q:
        coins, num = heapq.heappop(q)
        if mem[num] <= coins:
            continue
        mem[num] = coins
        if ans > num * D + coins:
            ans = num * D + coins
        if num == 0:
            continue
        tnum = num - (num % 2)
        heapq.heappush(q, (coins + (num - tnum) * D + A, tnum // 2))
        tnum = num + 2 - (num % 2)
        heapq.heappush(q, (coins + (tnum - num) * D + A, tnum // 2))

        tnum = num - (num % 3)
        heapq.heappush(q, (coins + (num - tnum) * D + B, tnum // 3))
        tnum = num + 3 - (num % 3)
        heapq.heappush(q, (coins + (tnum - num) * D + B, tnum // 3))

        tnum = num - (num % 5)
        heapq.heappush(q, (coins + (num - tnum) * D + C, tnum // 5))
        tnum = num + 5 - (num % 5)
        heapq.heappush(q, (coins + (tnum - num) * D + C, tnum // 5))

    return ans


def main():
    T = ni()
    for _ in range(T):
        print(solve())


main()