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:
from functools import lru_cache

T = int(input())

caseList = []

for i in range(T):
    caseList.append(list(map(int, input().split())))


@lru_cache(maxsize=None)
def solve(n, A, B, C, D):
    if n == 0:
        return 0
    if n == 1:
        return D
    if n == 2:
        return min(D + D, A + D)

    ans = n * D

    for num, cost in zip([2, 3, 5], [A, B, C]):
        ans = min(
            solve((n + (num - n % num)) // num, A, B, C, D) + cost + D * (num - n % num),
            solve((n - n % num) // num, A, B, C, D) + cost + D * (n % num),
            ans,
        )

    return ans


for N, A, B, C, D in caseList:
    print(solve(N, A, B, C, D))

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(10**6)
T = int(input())
for _ in range(T):
    N, A, B, C, D = map(int, input().split())

    @lru_cache(maxsize=None)
    def solve(n):
        if n == 1:
            return D

        res = n * D
        for v, c in zip([2, 3, 5], [A, B, C]):
            if n < v:
                continue
            q, m = divmod(n, v)
            if m == 0:
                res = min(solve(q) + c, res)
            else:
                res = min(res, min(solve(q) + c + D * m,
                                   solve(q + 1) + c + D * (v - m)))
        return res

    print(solve(N))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from functools import lru_cache

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

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


    print(check(n))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
T=int(input())
def cost(n):
 if n in memo:
  return memo[n]
 else:
  ans=n*d
  if n//2 in memo:
   ans=min(memo[n//2]+a*min(1,memo[n//2])+(n%2)*d,ans)
  else:
   ans=min(cost(n//2)+a*min(1,cost(n//2))+(n%2)*d,ans)
  if n//3 in memo:
   ans=min(memo[n//3]+b*min(1,memo[n//3])+(n%3)*d,ans)
  else:
   ans=min(cost(n//3)+b*min(1,cost(n//3))+(n%3)*d,ans)
  if n//5 in memo:
   ans=min(memo[n//5]+c*min(1,memo[n//5])+(n%5)*d,ans)
  else:
   ans=min(cost(n//5)+c*min(1,cost(n//5))+(n%5)*d,ans)
  if n//2+1 in memo:
   ans=min(memo[n//2+1]+a+(2-(n%2))*d,ans)
  else:
   ans=min(cost(n//2+1)+a+(2-(n%2))*d,ans)
  if n//3+1 in memo:
   ans=min(memo[n//3+1]+b+(3-(n%3))*d,ans)
  else:
   ans=min(cost(n//3+1)+b+(3-(n%3))*d,ans)
  if n//5+1 in memo:
   ans=min(memo[n//5+1]+c+(5-(n%5))*d,ans)
  else:
   ans=min(cost(n//5+1)+c+(5-(n%5))*d,ans)
  memo[n]=ans
  return ans
for j in range(T):
 N,a,b,c,d = map(int,input().split())
 memo = {0:0,1:d,2:min(2*d,a+d)}
 print(cost(N))
 memo={}

Submission status: Accepted

Solution code:
def f(n):
 if (m:=s.get(n,-1))<0:s[n]=m=min([d*n]+[abs(p*k-n)*d+c+f(k)for p,c in zip((2,3,5),b)for k in(n//p,0--n//p)])
 return m
exec("n,*b,d=map(int,input().split());s={0:0,1:d};print(f(n));"*int(input()))

Submission status: Accepted

Solution code:
def f(n):
 if (m:=s.get(n,-1))<0:s[n]=m=min([d*n]+[abs(p*k-n)*d+c+f(k)for p,c in zip(a,b)for k in(n//p,0--n//p)])
 return m
exec("n,*b,d=map(int,input().split());a=2,3,5;s={0:0,1:d};print(f(n));"*int(input()))

Submission status: Accepted

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

def vc(value,cost,pt):
    if value==1:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost+d)     
        else:
            vcs[0]=cost+d     
        return value,cost+d
    elif value<=0:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost)     
        else:
            vcs[0]=cost
        return cost
    
    if pt==1:
        v=value//2
        cost=cost+a+(value-v*2)*d
    elif pt==2:
        v=value//3
        cost=cost+b+(value-v*3)*d
    elif pt==3:
        v=value//5
        cost=cost+c+(value-v*5)*d
    elif pt==4:
        v=value//2+1
        cost=cost+a+(v*2-value)*d
    elif pt==5:
        v=value//3+1
        cost=cost+b+(v*3-value)*d
    elif pt==6:
        v=value//5+1
        cost=cost+c+(v*5-value)*d
    elif pt==7:
        v=0
        cost=cost+(value-v)*d
    return v,cost
    
def dfc(value,cost):
    if value==1:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost+d)     
        else:
            vcs[0]=cost+d     
        return cost+d
    elif value<=0:
        if 0 in vcs.keys():
            vcs[0]=min(vcs[0],cost)     
        else:
            vcs[0]=cost
        return cost

    for i in range(7):
        value1,cost1=vc(value,cost,i+1)
#        print(i+1,":",value1,cost1)
        if value1 in vcs.keys():
            if vcs[value1]<=cost1:
                continue
            else:
                vcs[value1]=min(vcs[value1],cost1)     
                dfc(value1,cost1)
        else:
            vcs[value1]=cost1     
            dfc(value1,cost1)
        

t=int(input())
#t=1
for i in range(t):
    n,a,b,c,d=map(int,input().split())
#    n,a,b,c,d=11,1,2,4,8
#    n,a,b,c,d=11,1,2,2,8
#    n,a,b,c,d=32, 10, 8, 5, 4
#    n,a,b,c,d=29384293847243, 454353412, 332423423, 934923490, 1
#    n,a,b,c,d=900000000000000000, 332423423, 454353412, 934923490, 987654321
    
    vcs=dict()
    cost=dfc(n,0)
    print(vcs[0])

Submission status: Accepted

Solution code:
T = int(input())
K = []
for i in range(T):
    a = list(map(int,input().split()))
    K.append(a)

def pay(N):
    if N == 0:
        return 0
    if N == 1:
        return D
    if N in memo:
        return memo[N]

    m = float("inf")
    if N % 2 == 0:
        m = min(m, A + pay(N // 2))
    else:
        m = min(m, A + pay(N // 2) + D)
        m = min(m, A + pay(N // 2 + 1) + D)

    if N % 3 == 0:
        m = min(m, B + pay(N // 3))
    else:
        m = min(m, B + pay(N // 3) + D*(N%3))
        m = min(m, B + pay(N // 3 + 1) + D*(3 - N%3))

    if N % 5 == 0:
        m = min(m, C + pay(N // 5))
    else:
        m = min(m, C + pay(N // 5) + D*(N%5))
        m = min(m, C + pay(N // 5 + 1) + D*(5 - N%5))

    m = min(m, D*N)
    memo[N] = m
    return m

for i in range(T):
    memo = {}
    N, A, B, C, D = K[i]
    print(pay(N))

Submission status: Accepted

Solution code:
CACHE = None
A,B,C,D = None,None,None,None

def f(N):
    if N == 1:
        return D

    if N in CACHE:
        return CACHE[N]

    x = None
    if N%2 == 0:
        x = f(N//2) + A
    else:
        N2 = N//2
        x = min(f(N2+1), f(N2)) + A + D

    N3 = N%3
    if N3 == 0:
        x = min(x, f(N//3)+B)
    elif N3 == 1:
        x = min(x, f(N//3)+B+D)
    else:
        x = min(x, f(N//3+1)+B+D)
        
    if N >= 4:
        N5 = N%5
        if N5 == 0:
            x = min(x, f(N//5)+C)
        elif N5 <= 2:
            x = min(x, f(N//5)+C+D*N5)
        else:
            x = min(x, f(N//5+1)+C+D*(5-N5))

    if D <= x/N:
        x = min(x, D*N)
        
    CACHE[N] = x
    return x


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

Submission status: Accepted

Solution code:
T = int(input())
import sys
sys.setrecursionlimit(20000)

def f(n):
    if n == 0:
        return 0
    if n == 1:
        return D
    if n in dic:
        return dic[n]
    if n%2 == 0:
        n2 = f(n//2)+A
    else:
        n2 = min(f((n+1)//2), f((n-1)//2))+A+D
    if n%3 == 0:
        n3 = f(n//3)+B
    elif n%3 == 1:
        n3 = min(f((n-1)//3), f((n+2)//3)+D)+B+D
    else:
        n3 = min(f((n-2)//3)+D, f((n+1)//3))+B+D
    if n%5 == 0:
        n5 = f(n//5)+C
    elif n%5 == 1:
        n5 = min(f((n-1)//5)+D, f((n+4)//5)+4*D)+C
    elif n%5 == 2:
        n5 = min(f((n-2)//5)+2*D, f((n+3)//5)+3*D)+C
    elif n%5 == 3:
        n5 = min(f((n-3)//5)+3*D, f((n+2)//5)+2*D)+C
    else:
        n5 = min(f((n-4)//5)+4*D, f((n+1)//5)+D)+C
    res = min(n2, n3, n5, n*D)
    dic[n] = res
    return res
    
for _ in range(T):
    N,A,B,C,D = map(int, input().split())
    dic = {}
    print(f(N))

Submission status: Accepted

Solution code:
T = int(input())
K = []
for i in range(T):
    a = list(map(int,input().split()))
    K.append(a)

def pay(N):
    if N == 0:
        return 0
    if N == 1:
        return D
    if N in memo:
        return memo[N]

    m = float("inf")
    if N % 2 == 0:
        m = min(m, A + pay(N // 2))
    else:
        m = min(m, A + pay(N // 2) + D)
        m = min(m, A + pay(N // 2 + 1) + D)

    if N % 3 == 0:
        m = min(m, B + pay(N // 3))
    else:
        m = min(m, B + pay(N // 3) + D*(N%3))
        m = min(m, B + pay(N // 3 + 1) + D*(3 - N%3))

    if N % 5 == 0:
        m = min(m, C + pay(N // 5))
    else:
        m = min(m, C + pay(N // 5) + D*(N%5))
        m = min(m, C + pay(N // 5 + 1) + D*(5 - N%5))
        
    m = min(m, D*N)
    memo[N] = m
    return m

for i in range(T):
    memo = {}
    N, A, B, C, D = K[i]
    print(pay(N))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10**64

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

for N, A, B, C, D in Query:
    # ans = INF
    P = {}
    def solve(n):
        # print(n)
        if n == 0:
            return INF
        if n in P:
            return P[n]
        if n == 1:
            return D
        S = n*D
        if n%2 == 0:
            S = min(S, solve(n//2)+A)
        else:
            S = min(S, solve(n//2)+A+D)
            S = min(S, solve((n+1)//2)+A+D)
        if n%3 == 0:
            S = min(S, solve(n//3)+B)
        else:
            S = min(S, solve(n//3)+B+D*(n%3))
            S = min(S, solve(n//3+1)+B+D*(3-n%3))
        if n%5 == 0:
            S = min(S, solve(n//5)+C)
        else:
            S = min(S, solve(n//5)+C+D*(n%5))
            S = min(S, solve(n//5+1)+C+D*(5-n%5))
        P[n] = S
        # print(n, P)
        return S
    # print(P)
    print(solve(N))

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def solve(N, A, B, C, D):

        # Nを0にするために必要なコインをメモ化再帰で求める
        @lru_cache(None)
        def f(N):
            # 再帰終了条件
            if N == 0:
                return 0
            if N == 1:
                return D

            ret = D * N

            q, r = divmod(N, 2)
            # Nが2で割り切れる場合、必要な追加コインはA枚
            if r == 0:
                ret = min(ret, f(q) + A)
            # Nが2で割り切れない場合、必要な追加コインはA+D枚
            else:
                # f(q) + A + D：qを2倍した後に1を足す
                # f(q + 1) + A + D：q+1を2倍した後に1を引く
                ret = min(ret, f(q) + A + D, f(q + 1) + A + D)

            q, r = divmod(N, 3)
            # Nが3で割り切れる場合、必要な追加コインはB枚
            if r == 0:
                ret = min(ret, f(q) + B)
            # Nが3で割った余りが1の時、qを3倍して1を足すのが、最もコインが少なくて済む為、必要な追加コインはB+D枚
            elif r == 1:
                ret = min(ret, f(q) + B + D)
            # Nが3で割った余りが2の時、q+1を3倍した後に1を引くのが、最もコインが少なくて済む為、必要な追加コインはB+D枚
            else:
                ret = min(ret, f(q + 1) + B + D)

            q, r = divmod(N, 5)
            # Nが5で割り切れる場合、必要な追加コインはC枚
            if r == 0:
                ret = min(ret, f(q) + C)
            # Nが5で割った余りが1の時、qを5倍して1を足すのが、最もコインが少なくて済む為、必要な追加コインはC+D枚
            elif r == 1:
                ret = min(ret, f(q) + C + D)
            # Nが5で割った余りが2の時、qを5倍して2を足すのが、最もコインが少なくて済む為、必要な追加コインはC+2D枚
            elif r == 2:
                ret = min(ret, f(q) + C + D + D)
            # Nが5で割った余りが3の時、q+1を5倍して2を引くのが、最もコインが少なくて済む為、必要な追加コインはC+2D枚
            elif r == 3:
                ret = min(ret, f(q + 1) + C + D + D)
            # Nが5で割った余りが3の時、q+1を5倍して1を引くのが、最もコインが少なくて済む為、必要な追加コインはC+D枚
            else:
                ret = min(ret, f(q + 1) + C + D)

            return ret

        return f(N)

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def f(n):
 if(m:=s.get(n))is None:s[n]=m=min([d*n]+[abs(p*k-n)*d+c+f(k)for p,c in zip(a,b)for k in(n//p,0--n//p)])
 return m
exec("n,*b,d=map(int,input().split());a=2,3,5;s={0:0,1:d};print(f(n));"*int(input()))

Submission status: Accepted

Solution code:
a=2,3,5
def f(n):
 if(m:=s.get(n))is None:s[n]=m=min([d*n]+[abs(p*k-n)*d+c+f(k)for p,c in zip(a,b)for k in(n//p,0--n//p)])
 return m
exec("n,*b,d=map(int,input().split());s={0:0,1:d};print(f(n));"*int(input()))

Submission status: Accepted

Solution code:
a=2,3,5
def f(n):
 if(m:=s.get(n))is None:s[n]=m=min([d*n]+[abs(p*k-n)*d+c+f(k)for p,c in zip(a,b)for k in(n//p,0--n//p)])
 return m
for _ in[0]*int(input()):n,*b,d=map(int,input().split());s={0:0,1:d};print(f(n))

Submission status: Accepted

Solution code:
a=2,3,5
def f(n):
 if(m:=s.get(n))is None:s[n]=(m:=min([d*n]+[abs(p*k-n)*d+c+f(k)for p,c in zip(a,b)for k in(n//p,0--n//p)]))
 return m
for _ in[0]*int(input()):n,*b,d=map(int,input().split());s={0:0,1:d};print(f(n))

Submission status: Accepted

Solution code:
a=2,3,5
def f(n):
 m=s.get(n)
 if m is None:s[n]=(m:=min([d*n]+[abs(p*k-n)*d+c+f(k)for p,c in zip(a,b)for k in(n//p,0--n//p)]))
 return m
for _ in[0]*int(input()):n,*b,d=map(int,input().split());s={0:0,1:d};print(f(n))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from sys import setrecursionlimit
setrecursionlimit(10**8)
INF = float("inf")


def main():

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

        def f(n):
            memo[n] = n*D
            ans = memo[n]
            for cost, p in zip((A, B, C), (2, 3, 5)):
                d, m = divmod(n, p)
                if d not in memo:
                    f(d)
                if d+1 not in memo:
                    f(d+1)
                ans = min(ans, memo[d] + cost + m*D)
                ans = min(ans, memo[d+1] + cost + (p-m)*D)
            memo[n] = ans
            return ans
        print(f(N))

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Nから0にする
T = ir()

@lru_cache(None)
def F(x, A, B, C, D):
    if x == 1:
        return D
    elif x <= 0:
        return INF
    if x&1:
        a = min(F(x//2, A, B, C, D) + D + A, F((x+1)//2, A, B, C, D) + D + A)
    else:
        a = F(x//2, A, B, C, D) + A
    cnt2 = 0
    y = x
    while y%3 != 0:
        y -= 1
        cnt2 += 1
    b = F(y//3, A, B, C, D) + B + cnt2 * D
    if (x+1)%3 == 0:
        t = F((x+1)//3, A, B, C, D) + B + D
        b = min(b, t)
    cnt3 = 0
    y = x
    while y%5 != 0:
        y -= 1
        cnt3 += 1
    c = min(F(y//5, A, B, C, D) + C + cnt3 * D, F((y+5)//5, A, B, C, D) + C + (5-cnt3) * D)
    d = x * D
    ret = min(a, b, c, d)
    return ret

INF = float('inf')
for _ in range(T):
    N, A, B, C, D = lr()
    answer = F(N, A, B, C, D)
    print(answer)

Submission status: Accepted

Solution code:
a = 2, 3, 5
 
def f(n):
  m = memo.get(n)
  if m is None:
    m = min([d * n] + [f(k) + abs(p * k - n) * d + c for p, c in zip(a, b) for k in (n // p, 0--n // p)])
    memo[n] = m
  return m
 
t = int(input())
for _ in range(t):
  n, *b, d = map(int, input().split())
  memo = {0: 0, 1: d}
  print(f(n))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Nから0にする
T = ir()

@lru_cache(None)
def F(x, A, B, C, D):
    if x == 1:
        return D
    elif x <= 0:
        return INF
    if x&1:
        a = min(F(x//2, A, B, C, D) + D + A, F((x+1)//2, A, B, C, D) + D + A)
    else:
        a = F(x//2, A, B, C, D) + A
    cnt2 = 0
    y = x
    while y%3 != 0:
        y -= 1
        cnt2 += 1
    b = F(y//3, A, B, C, D) + B + cnt2 * D
    if (x+1)%3 == 0:
        t = F((x+1)//3, A, B, C, D) + B + D
        b = min(b, t)
    cnt3 = 0
    y = x
    while y%5 != 0:
        y -= 1
        cnt3 += 1
    c = min(F(y//5, A, B, C, D) + C + cnt3 * D, F((y+5)//5, A, B, C, D) + C + (5-cnt3) * D)
    ret = min(a, b, c)
    if x < 10 ** 12 or D < 10 ** 9:
        d = x * D
        ret = min(ret, d)
    return ret

INF = float('inf')
for _ in range(T):
    N, A, B, C, D = lr()
    answer = F(N, A, B, C, D)
    print(answer)

Submission status: Accepted

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

T = int(input())
INF = 10**18

for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    DC = tuple(zip((2, 3, 5), (A, B, C)))

    @lru_cache(maxsize=None)
    def search(now):
        if now == 0:
            return 0

        ret = now * D
        for div, cost in DC:
            q, r = divmod(now, div)
            ret = min(
                ret,
                search(q) + cost + r * D,
                search(q + 1) + cost + (div - r) * D if q + 1 < now else INF,
            )
        return ret

    print(search(N))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
t = int(input())
for _ in range(t):
    n, a, b, c, da = map(int, input().split())
    hq = [(0, n)]
    d = defaultdict(lambda: 10 ** 25)
    d[n] = 0
    while hq:
        cs, p = heapq.heappop(hq)
        if d[p] < cs:
            continue
        if d[p // 2] > cs + a + (p % 2) * da:
            heapq.heappush(hq, (cs + a + (p % 2) * da, p // 2))
            d[p // 2] = cs + a + (p % 2) * da
        if d[p // 2 + 1] > cs + a + da:
            heapq.heappush(hq, (cs + a + da, p // 2 + 1))
            d[p // 2 + 1] = cs + a + da
        if d[p // 3] > cs + b + (p % 3) * da:
            heapq.heappush(hq, (cs + b + (p % 3) * da, p // 3))
            d[p // 3] = cs + b + (p %3) * da
        if d[p // 3 + 1] > cs + b +  (1+(p%3)%2)* da:
            heapq.heappush(hq, (cs + b + (1+(p%3)%2) * da, p // 3 + 1))
            d[p // 3 + 1] = cs + b + (1+(p%3)%2) * da
        ccc = p % 5
        if ccc <= 2:
            if d[p//5] > cs+c+ccc*da:
                heapq.heappush(hq,(cs+c+ccc*da,p//5))
                d[p//5] = cs+c+ccc*da
            if d[p//5 +1] > cs+c+(ccc+1)*da:
                heapq.heappush(hq,(cs+c+(ccc+1)*da,p//5 +1))
                d[p//5 +1] = cs+c+(ccc+1)*da
        else:
            if d[p//5] > cs+c+(6-ccc)*da:
                heapq.heappush(hq,(cs+c+(6-ccc)*da,p//5))
                d[p//5] = cs+c+(6-ccc)*da
            if d[p//5 +1] > cs+c+(5-ccc)*da:
                heapq.heappush(hq,(cs+c+(5-ccc)*da,p//5 +1))
                d[p//5 +1] = cs+c+(5-ccc)*da
    ans = 10 ** 25
    for k, v in d.items():
        ans = min(ans, k * da + v)
    print(ans)

Submission status: Accepted

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

T = int(input())
INF = 10**18

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

    @lru_cache(maxsize=None)
    def search(now):
        if now == 0:
            return 0

        ret = now * D
        for div, cost in zip((2, 3, 5), (A, B, C)):
            q, r = divmod(now, div)
            ret = min(
                ret,
                search(q) + cost + r * D,
                search(q + 1) + cost + (div - r) * D if q + 1 < now else INF,
            )
        return ret

    print(search(N))

Submission status: Accepted

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

T = int(input())
INF = 10**18

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

    @lru_cache(maxsize=None)
    def search(now):
        if now == 0:
            return 0

        ret = INF
        for div, cost in zip((2, 3, 5), (A, B, C)):
            q, r = divmod(now, div)
            ret = min(
                ret,
                search(q) + cost + r * D,
                search(q + 1) + cost + (div - r) * D if q + 1 < now else INF,
                now * D
            )
        return ret

    print(search(N))

Submission status: Accepted

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

T = int(input())
INF = 10**18

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

    @lru_cache(maxsize=None)
    def search(now):
        if now == 0:
            return 0

        ret = INF
        for div, cost in zip((2, 3, 5), (A, B, C)):
            q, r = divmod(now, div)
            ret = min(
                ret,
                search(q) + cost + r * D,
                search(q + 1) + cost + (div - r) * D if q + 1 < now else INF,
                now * D
            )
        return ret

    print(search(N))

Submission status: Accepted

Solution code:
#10:35
t = int(input())
import heapq
def tr(score,number):
  try:
    if use[number] > score:
      use[number] = score
      heapq.heappush(now,[score,number])
  except:
    use[number] = score
    heapq.heappush(now,[score,number])
for _ in range(t):
  n,a,b,c,d = map(int,input().split())
  now = [[0,n]]
  ans = n * d
  use = {n:0}
  while True:
    sc,num = heapq.heappop(now)
    ans = min(ans,sc+num*d)
    if use[num] < sc:
      continue
    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())
for i in range(T):
    n, A, B, C, D = map(int, input().split())
    memo = {}

    def herasu(N):
        if N == 0:
            return 0
        if N == 1:
            return D
        if N in memo:
            return memo[N]
        m = 100000000000000000000000
        if N % 2 == 0:
            m = min([m, A + herasu(N//2)])
        else:
            m = min([m, A + herasu(N//2) + D])
            m = min([m, A + herasu(N//2 + 1) + D])
        if N % 3 == 0:
            m = min(m, B + herasu(N//3))
        else:
            m = min([m, B + herasu(N//3) + (N%3) * D])
            m = min([m, B + herasu(N//3 + 1) + (3-(N%3)) * D])
        if N % 5 == 0:
            m = min(m, C + herasu(N // 5))
        else:
            m = min([m, C + herasu(N//5) + (N%5) * D])
            m = min([m, C + herasu(N//5 + 1) + (5-(N%5)) * D])
        m = min([m, D * N])
        memo[N] = m
        return m

    print(herasu(n))

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
from heapq import *


def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    for _ in range(NI()):
        N,A,B,C,D = LI()

        q = []
        heapify(q)

        memo = {}

        def push(c,n):
            if memo.get(n,INF) > c :
                heappush(q,(c,n))
                memo[n] = c


        push(0,N)

        while q:
            c,n = heappop(q)
            m = [0] * 9
            if n == 1:
                print(c+D)
                break

            if n % 2 == 0:
                push(c+min(A,n//2*D),n//2)
            else:
                m[1] = m[-1] = 1
            if n % 3 == 0:
                push(c+min(B,n//3*2*D),n//3)
            else:
                m[3-(n%3)] = m[-(n%3)] = 1
            if n % 5 == 0:
                push(c+min(C,n//5*4*D),n//5)
            else:
                m[5-(n%5)] = m[-(n%5)] = 1
            for i in range(-4,5):
                if m[i] and n+i > 0: push(c+D*abs(i),n+i)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict, deque
t = int(input())
for _ in range(t):
    n, a, b, c, da = map(int, input().split())
    hq = [(0, n)]
    d = defaultdict(lambda: 10 ** 25)
    d[n] = 0
    while hq:
        cs, p = heapq.heappop(hq)
        if d[p] < cs:
            continue
        if d[p // 2] > cs + a + (p % 2) * da:
            heapq.heappush(hq, (cs + a + (p % 2) * da, p // 2))
            d[p // 2] = cs + a + (p % 2) * da
        if d[p // 2 + 1] > cs + a + (2 - p % 2):
            heapq.heappush(hq, (cs + a + (2 - p % 2) * da, p // 2 + 1))
            d[p // 2 + 1] = cs + a + (2 - p % 2)
        if d[p // 3] > cs + b + (p % 3) * da:
            heapq.heappush(hq, (cs + b + (p % 3) * da, p // 3))
            d[p // 3] = cs + b + (p % 3) * da
        if d[p // 3 + 1] > cs + b + (3 - p % 3) * da:
            heapq.heappush(hq, (cs + b + (3 - p % 3) * da, p // 3 + 1))
            d[p // 3 + 1] = cs + b + (3 - p % 3) * da
        if d[p // 5] > cs + c + (p % 5) * da:
            heapq.heappush(hq, (cs + c + (p % 5) * da, p // 5))
            d[p // 5] = cs + c + (p % 5) * da
        if d[p // 5 + 1] > cs + c + (5 - p % 5) * da:
            heapq.heappush(hq, (cs + c + (5 - p % 5) * da, p // 5 + 1))
            d[p // 5 + 1] = cs + c + (5 - p % 5) * da
    ans = 10 ** 25
    for k, v in d.items():
        ans = min(ans, k * da + v)
    print(ans)