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:
        fb,fc = 1,1
        if t % 5 == 0:
            fc = 0
            if c > 4*t//5 * d:
                fin = min(fin,ans+t*d)
            else:
                if t//5 not in dic1:
                    solve(t//5,ans+c)
                elif dic1[t//5] > ans+c:
                    solve(t//5,ans+c)
        if t % 3 == 0:
            fb = 0
            if b > 2*t//3 * d:
                fin = min(fin,ans+t*d)
            else:
                if t//3 not in dic1:
                    solve(t//3,ans+b)
                elif dic1[t//3] > ans+b:
                    solve(t//3,ans+b)

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

            if u % 2 == 0 and -2<i<2:
                if a > u//2 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//2 not in dic1:
                        solve(u//2,ans_temp+a)
                    elif dic1[u//2] > ans_temp+a:
                        solve(u//2,ans_temp+a)
        # 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:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


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


t = int(input())

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

Submission status: Accepted

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


t = int(input())

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import heapq


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

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

    if value in seen_values:
      continue

    seen_values.add(value)

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

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

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

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


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


if __name__ == '__main__':
  main()

Submission status: Accepted

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

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

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

    print(solve(n))

Submission status: Accepted

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


t = int(input())

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

Submission status: Accepted

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

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

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

    memo[n] = ans
    return ans

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

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

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

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

  if coin >= MAX:
    return sys.maxsize

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

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

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

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

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

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

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

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

Submission status: Accepted

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

sys.setrecursionlimit(2 * 10 ** 6)


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


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

Submission status: Accepted

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

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

    if N in memo:
        return memo[N]

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

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

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

    memo[N] = min(
        N * D,

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

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

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

    return memo[N]

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


##再帰する.割り切れないなら割り切れる近くの数について考える.
import sys
sys.setrecursionlimit(int(1e6))

def solve(N_,A,B,C,D):
    num = {}
    def saiki(N):
        ##なんであれN*Dは移動できる
        res = N*D
        if N == 0:
            return 0
        elif N == 1:
            return D
        if N in num:
            return num[N]
        
        if N%2 == 0:
            res = min(res,saiki(N//2)+A)
        else:##割り切れないとき,近い割り切れる数へと移動し,割り切る.
            res = min(res,saiki((N+1)//2)+A+D,saiki((N-1)//2)+A+D)
        
        if N%3 == 0:
            res = min(res,saiki(N//3)+B)
        else:
            res = min(res,saiki(N//3)+D*(N%3)+B,saiki(N//3+1)+D*(3-N%3)+B)
        
        if N%5 == 0:
            res = min(res,saiki(N//5)+C)
        else:
            res = min(res,saiki(N//5)+D*(N%5)+C,saiki(N//5+1)+D*(5-N%5)+C)
        
        ##メモ化
        num[N] = res

        return res
    
    print(saiki(N))

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

Submission status: Accepted

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

t = int(input())

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

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

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

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

        tmp = now*d

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

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

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

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

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

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

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

    ans = dfs(n)
    print(ans)

Submission status: Accepted

Solution code:
T = int(input())
for i in range(T):
    N,A,B,C,D = map(int,input().split())
    memo = {0:0,1:D}
    def f(n):
        if n in memo:
            return memo[n]
        else:
            res = D*n
            r2 = n%2
            r3 = n%3
            r5 = n%5
            res = min(res,f(n//2)+A+r2*D,f(n//3)+B+r3*D,f(n//5)+C+r5*D)
            res = min(res,f((n+1)//2)+A+(2-r2)*D,f((n+2)//3)+B+(3-r3)*D,f((n+4)//5)+C+(5-r5)*D)
            memo[n] = res
            return res
    print(f(N))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

t = ni()
from functools import lru_cache

for _ in range(t):
    n,a,b,c,d = na()

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(5000000)

def nasu(N, n):
  if N in DP:
    return n + DP[N]
  if N == 0:
    return n
  if N == 1:
    return n + D
  ans = n + D * N
  a = N % 2
  if a == 0:
    ans = min(ans, nasu(N // 2, n + A))
  else:
    if a > 1:
      ans = min(ans, nasu((N - 1) // 2, n + D + A))
    ans = min(ans, nasu((N + 1) // 2, n + D + A))
  b = N % 3
  if b == 0:
    ans = min(ans, nasu(N // 3, n + B))
  else:
    if N > 2:
      ans = min(ans, nasu((N - b) // 3, n + (b * D) + B)) 
    ans = min(ans, nasu((N + (3 - b)) // 3, n + ((3 - b) * D) + B)) 
  c = N % 5
  if c == 0:
    ans = min(ans, nasu(N // 5, n + C))
  else:
    if N > 4:
      ans = min(ans, nasu((N - c) // 5, n + (c * D) + C))
    ans = min(ans, nasu((N + (5 - c)) // 5, n + ((5 - c) * D) + C)) 

  DP[N] = ans - n
  return ans

T = int(input())
M = [list(map(int, input().split())) for _ in range(T)]
for N, A, B, C, D in M:
  DP = {}
  ans = nasu(N, 0)
  print(ans)

Submission status: Accepted

Solution code:

from heapq import heapify, heappop, heappush, heappushpop

class PriorityQueue:
    def __init__(self, heap=None):
        '''
        heap ... list
        '''
        self.heap = heap or []
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)


def solve(N,A,B,C,D):
    pq = PriorityQueue()
    visited = dict()

    best = 2 ** 63
    pq.push((0, N))

    while len(pq) > 0:
        cost, now = pq.pop()
        if now < 0:
            continue
        if now in visited and visited[now] <= cost:
            continue
        visited[now] = cost

        # debug("cost %lld, now %lld, [%d]\n", cost, now, last);
        if now == 0:
            best = min(best, cost)

        for d in range(-4, 5):
            x = now + d
            c = cost + D*abs(d)
            if x == 0:
                best = min(best, c)
            if x % 5 == 0:
                minc = min(C, D*(x - x//5))
                pq.push((c+minc, x//5))

        for d in range(-2, 3):
            x = now + d
            c = cost + D*abs(d)
            if x == 0:
                best = min(best, c)
            if x % 3 == 0:
                minc = min(B, D*(x - x//3))
                pq.push((c+minc, x//3))

        for d in range(-1, 2):
            x = now + d
            c = cost + D*abs(d)
            if x == 0:
                best = min(best, c)
            if x % 2 == 0:
                minc = min(A, D*(x - x//2))
                pq.push((c+minc, x//2))

    return best

if __name__ == '__main__':
    T = int(input())
    for t in range(T):
        N,A,B,C,D = map(int, input().split(' '))
        print(solve(N,A,B,C,D))

Submission status: Accepted

Solution code:
t = int(input())
testcase = [list(map(int, input().split())) for _ in range(t)]

dp={}
def f(n, a, b, c, d):
    
#    print(f'n={n} a={a} b={b} c={c} d={d}')
    if n in dp:
        return dp[n]
    
    if n==0:
        dp[n]=10**20
        return dp[n]
    if n==1:
        dp[n]=d
        return dp[n]
#    elif n==2:
#        dp[n]=min(n*d, d+a)
#        return dp[n]
#    elif n==3:
#        dp[n]=min(n*d, d+b, d+a+d)
#        return dp[n]
#    elif n==5:
#        dp[n]=min(n*d, d+a+a+d, d+c, d+b+d+d, d+a+b+d)
    
    l=[d*n]
    if n%2==0:
#        print(f'f({n//2},{a},{b},{c},{d})')
        l.append(f(n//2,a,b,c,d)+a)
        #３の倍数の近い方
        x=(n+1)//3*3
        dx=abs(x-n)
#        print(f'f({x//3},{a},{b},{c},{d}+{b}+{dx}*{d})')
        l.append(f(x//3,a,b,c,d)+b+dx*d)
        #5の倍数の近い方
        x=(n+2)//5*5
        dx=abs(x-n)
        l.append(f(x//5,a,b,c,d)+c+dx*d)
    else:
        l.append(f((n-1)//2, a,b,c,d)+a+d)
        l.append(f((n+1)//2, a,b,c,d)+a+d)
        #３の倍数の近い方
        x=(n+1)//3*3
        dx=abs(x-n)
        l.append(f(x//3,a,b,c,d)+b+dx*d)
        #5の倍数の近い方
        x=(n+2)//5*5
        dx=abs(x-n)
        l.append(f(x//5,a,b,c,d)+c+dx*d)

    dp[n]=min(l)
    return dp[n]

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

for tc in testcase:
    solve(*tc)
    dp.clear()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
from collections import defaultdict

input = sys.stdin.readline
T = int(input())
NABCD = [list(map(int,input().split())) for i in range(T)]

for N,A,B,C,D in NABCD:
    h = [(N,0)]
    ans = D*N
    dic = defaultdict(lambda:D*N+1)
    while h:
        val, cost = heappop(h)

        if ans <= cost:
            continue

        if dic[val] <= cost:
            continue
        dic[val] = cost

        if val == 0:
            ans = min(ans,cost)
            continue
        if val == 1:
            ans = min(ans,cost+D)
            continue

        heappush(h,(0,cost + val*D))
        m2 = val % 2
        if m2 == val:
            heappush(h,(0,cost+D))
        elif m2 == 0:
            heappush(h,(val//2,cost+A))
        else:
            heappush(h,((val+1)//2,cost+A+D))
            heappush(h,((val-1)//2,cost+A+D))
        
        m3 = val % 3
        if m3 == val:
            heappush(h,(0,cost+m3*D))
        elif m3 == 0:
            heappush(h,(val//3,cost+B))
        else:
            heappush(h,((val-m3)//3,cost+B+m3*D))
            heappush(h,((val+3-m3)//3,cost+B+(3-m3)*D))

        m5 = val % 5
        if m5 == val:
            heappush(h,(0,cost+m5*D))
        elif m5 == 0:
            heappush(h,(val//5,cost+C))
        else:
            heappush(h,((val-m5)//5,cost+C+m5*D))
            heappush(h,((val+5-m5)//5,cost+C+(5-m5)*D))
    print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
 
sys.setrecursionlimit(10 ** 9)
 
t = int(input())
 
for _ in range(t):
  n,a,b,c,d = map(int, input().split())
  #辞書形式で最低枚数を管理
  dic = {0:0, 1:d}
  @lru_cache(maxsize = None)
  def f(n):
    if n in dic:
      return dic[n]
    #dを全部使う
    nn = n * d
    #nの直近の5の倍数を経由、以下同様
    n5 = (n % 5) * d + c + f(n // 5)
    if n % 5 != 0:
      ##n = 11の場合、n % 5 = 1, -n % 5 = 4
      n5 = min(n5, (-n % 5) * d + c + f((n // 5) + 1))
    n3 = (n % 3) * d + b + f(n // 3)
    if n % 3 != 0:
      n3 = min(n3, (-n % 3) * d + b + f((n // 3) + 1))
    n2 = (n % 2) * d + a + f(n // 2)
    if n % 2 != 0:
      n2 = min(n2, (n % 2) * d + a + f((n // 2) + 1))

    ret = min(nn, n2, n3, n5)
    dic[n] = ret
    return ret
 
  print(f(n))

Submission status: Accepted

Solution code:
def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

used = {}
used[0] = 0
gg = {}

def dfs(n, a, b, c, d):
    global used
    # print(n)
    if n in used: return used[n]
    ret = n*d
    for i in range(-4, 4):
        now = n + i
        if now%2==0 and now > 0 and abs(i) < 2: ret = min(ret, abs(i)*d + a + dfs(now//2, a, b, c, d))
        if now%3==0 and now > 0 and abs(i) < 3: ret = min(ret, abs(i)*d + b + dfs(now//3, a, b, c, d))
        if now%5==0 and now > 0: ret = min(ret, abs(i)*d + c + dfs(now//5, a, b, c, d))
    used[n] = ret
    return ret
        


def solve():
    n,a,b,c,d = NextInts()
    global used
    used = {}
    gg = {}
    used[0] = 0
    used[1] = d
    used[2] = min(d*2, d+a)
    return dfs(n, a, b, c,d)
    
def main():
    t = NextInt()
    ans = [solve() for i in range(t)]
    for i in range(t):
        print(ans[i])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

hpush = heapq.heappush
hpop = heapq.heappop
for _ in [0]*T:
    ans = 10**18
    N,A,B,C,D = map(int,input().split())
    hq = [(0,N)]
    made = set()
    while hq:
        cost,n = hpop(hq)
        if n==0:
            ans = min(ans,cost)
            continue
        if n in made:continue
        made.add(n)

        n2 = n//2
        cost2 = cost + min(D*(n-n2),A+D*(n%2))
        hpush(hq,(cost2,n2))

        n2b = (n-1)//2+1
        cost2b = cost + min(D*(n-n2b),A+D*((-n)%2))
        hpush(hq,(cost2b,n2b))

        n3 = n//3
        cost3 = cost + min(D*(n-n3),B+D*(n%3))
        hpush(hq,(cost3,n3))

        n3b = (n-1)//3+1
        cost3b = cost + min(D*(n-n3b),B+D*((-n)%3))
        hpush(hq,(cost3b,n3b))

        n5 = n//5
        cost5 = cost + min(D*(n-n5),C+D*(n%5))
        hpush(hq,(cost5,n5))
        
        n5b = (n-1)//5+1
        cost5b = cost + min(D*(n-n5b),C+D*((-n)%5))
        hpush(hq,(cost5b,n5b))

    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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


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