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)
from collections import defaultdict
t = int(input())


def solve():
    n,a,b,c,d = map(int, input().split())
    memo = defaultdict(int)
    def f(n):
        if memo[n] != 0:
            return memo[n]
        if n == 2:
            return min(a+d,2*d)
        if n == 1:
            return d #最後-1する
        if n == 0:
            return 0 #0になったらおしまいです
        # 2の操作
        r2 = n % 2
        n_p_2 = n + 2 - r2
        n_m_2 = n - r2
        d_p_2 = f(n_p_2//2) + d*(2-r2) + a
        d_m_2 = f(n_m_2//2) + d*(r2) + a
        r3 = n % 3
        n_p_3 = n + 3 - r3
        n_m_3 = n - r3
        d_p_3 = f(n_p_3//3) + d*(3-r3) + b
        d_m_3 = f(n_m_3//3) + d*(r3) + b
        r5 = n % 5
        n_p_5 = n + 5 - r5
        n_m_5 = n - r5
        d_p_5 = f(n_p_5//5) + d*(5-r5) + c
        d_m_5 = f(n_m_5//5) + d*(r5) + c
        ret = min(n*d,d_p_2,d_p_3,d_p_5,d_m_2,d_m_3,d_m_5)
        memo[n] = ret
        return ret
    ans = f(n)
    return ans
     

ans = []
for _ in range(t):
    ans.append(solve())

for a in ans:
    print(a)

Submission status: Accepted

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

T = int(input())

memo = {}
def solve(n, a, b, c, d):
  global memo
  if n in memo:
    return memo[n]
  res = []
  flag = [True] * 6
  for i in range(5):
    n1 = n - i; n2 = n + i
    if n1:
      if n1 % 2 == 0 and flag[0]:
        flag[0] = False
        v = solve(n1//2, a, b, c, d) + min(a + i*d, (n1//2 + i)*d)
        res.append(v)
      if n1 % 3 == 0 and flag[2]:
        flag[2] = False
        v = solve(n1//3, a, b, c, d) + min(b + i*d, (2*n1//3 + i)*d)
        res.append(v)
      if n1 % 5 == 0 and flag[4]:
        flag[4] = False
        v = solve(n1//5, a, b, c, d) + min(c + i*d, (4*n1//5 + i)*d)
        res.append(v)
    if n2 % 2 == 0 and flag[1]:
      flag[1] = False
      v = solve(n2//2, a, b, c, d) + min(a + i*d, abs(n-n2//2)*d)
      res.append(v)
    if n2 % 3 == 0 and flag[3]:
      flag[3] = False
      v = solve(n2//3, a, b, c, d) + min(b + i*d, abs(n-n2//3)*d)
      res.append(v)
    if n2 % 5 == 0 and flag[5]:
      flag[5] = False
      v = solve(n2//5, a, b, c, d) + min(c + i*d, abs(n-n2//5)*d)
      res.append(v)
  v = min(res)
  memo[n] = v
  return v


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

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

Submission status: Accepted

Solution code:
# もらうDPをメモ化再帰にしました的な実装
t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    memo = {0: 0, 1: d}

    def dfs(n):
        if n in memo.keys():
            return memo[n]

        res1 = n*d
        r = n % 2
        res2 = a+r*d+dfs((n-r)//2)
        if r != 0:
            tmp = a+(2-r)*d+dfs((n+(2-r))//2)
            if tmp < res2:
                res2 = tmp

        r = n % 3
        res3 = b+r*d+dfs((n-r)//3)
        if r != 0:
            tmp = b+(3-r)*d+dfs((n+(3-r))//3)
            if tmp < res3:
                res3 = tmp

        r = n % 5
        res5 = c+r*d+dfs((n-r)//5)
        if r != 0:
            tmp = c+(5-r)*d+dfs((n+(5-r))//5)
            if tmp < res5:
                res5 = tmp

        memo[n] = min(res1, res2, res3, res5)
        return memo[n]

    print(dfs(n))

Submission status: Accepted

Solution code:
from functools import *
from math import *

t = int(input())

@lru_cache(maxsize=None)
def sol(n, a, b, c, d):
    if n == 1: return d
    ans = n * d
    cn = (n + 1) // 2
    fn = n // 2
    if cn: ans = min(ans, sol(cn, a, b, c, d) + abs(cn * 2 - n) * d + a)
    if fn: ans = min(ans, sol(fn, a, b, c, d) + abs(fn * 2 - n) * d + a)
    cn = (n + 2) // 3
    fn = n // 3
    if cn: ans = min(ans, sol(cn, a, b, c, d) + abs(cn * 3 - n) * d + b)
    if fn: ans = min(ans, sol(fn, a, b, c, d) + abs(fn * 3 - n) * d + b)
    cn = (n + 4) // 5
    fn = n // 5
    if cn: ans = min(ans, sol(cn, a, b, c, d) + abs(cn * 5 - n) * d + c)
    if fn: ans = min(ans, sol(fn, a, b, c, d) + abs(fn * 5 - n) * d + c)
    # print(str(n) + ", " + str(ans))
    return ans

for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    sol.cache_clear()
    print(min(d * n, sol(n, a, b, c, d)))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


t = I()
for _ in range(t):
    n, a, b, c, d = LI()
    D = defaultdict(int)
    def f(x):
        if D[x]:
            return D[x]
        if x == 0:
            return 0
        if x == 1:
            return d
        ret = INF
        ret = min(ret, f(x // 2) + x % 2 * d + a)
        ret = min(ret, f(x // 3) + x % 3 * d + b)
        ret = min(ret, f(x // 5) + x % 5 * d + c)
        if x % 2:
            ret = min(ret, f(x // 2 + 1) + (2 - x % 2) * d + a)
        if x % 3:
            ret = min(ret, f(x // 3 + 1) + (3 - x % 3) * d + b)
        if x % 5:
            ret = min(ret, f(x // 5 + 1) + (5 - x % 5) * d + c)
        ret = min(ret, x * d)
        D[x] = ret
        return ret

    print(f(n))

Submission status: Accepted

Solution code:
from math import ceil
import sys
sys.setrecursionlimit(10**7)
t=int(input())
for _ in range(t):
    memo=dict()
    n,a,b,c,d=map(int,input().split())
    def dfs(x):
        if x==0:
            return 0
        if x==1:
            return d
        if x in memo:
            return memo[x]
        l2=2*(x//2)
        r2=2*((x+1)//2)
        l3=3*(x//3)
        r3=3*((x+2)//3)
        l5=5*(x//5)
        r5=5*((x+4)//5)
        mini=d*x
        mini=min(mini,abs(l2-x)*d+a+dfs(l2//2))
        mini=min(mini,abs(r2-x)*d+a+dfs(r2//2))
        mini=min(mini,abs(l3-x)*d+b+dfs(l3//3))
        mini=min(mini,abs(r3-x)*d+b+dfs(r3//3))
        mini=min(mini,abs(l5-x)*d+c+dfs(l5//5))
        mini=min(mini,abs(r5-x)*d+c+dfs(r5//5))
        memo[x]=mini
        return mini
    print(dfs(n))

Submission status: Accepted

Solution code:
t = int(input())

import sys
sys.setrecursionlimit(10 ** 6)

def calc(x):
    if x in dp:
        return dp[x]#メモ済の場合はそれを利用
    
    divs = [5, 3, 2]
    costs = [c, b, a]
    res = d * x #全てDでいった場合が初期設定
    for div, cost in zip(divs, costs):
        dived = x//div
        res = min(res, calc(dived) + cost + abs(x-dived*div) * d)#floorでの再帰
        if x > div:#Nのほうが小さい場合は不要
            dived = x//div+1
            res = min(res, calc(dived) + cost + abs(x-dived*div) * d)#ceilでの再帰
    dp[x] = res#メモしておく
    return res

for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    dp = {}#辞書で管理
    dp[0] = 0
    dp[1] = d
    print(calc(n))

Submission status: Accepted

Solution code:
t = int(input())

import sys

sys.setrecursionlimit(10 ** 6)


def calc(x):
    if x in dp:
        return dp[x]

    divs = [5, 3, 2]
    costs = [c, b, a]
    res = d * x

    for div, cost in zip(divs, costs):
        dived = x // div
        res = min(res, calc(dived) + cost + abs(x - dived * div) * d)
        if x > div:
            dived = x // div + 1
            res = min(res, calc(dived) + cost + abs(x - dived * div) * d)
    dp[x] = res

    return res


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def solve():
    N,A,B,C,D=map(int,input().split())
    memo={}
    def rec(x):
        if x in memo:
            return memo[x]
        if x==1:
            return D
        if x==0:
            return 0
        res=D*x
        for y,cost in zip([2,3,5],[A,B,C]):
            res=min(res,rec(x//y)+abs(x-(x//y*y))*D+cost)
            res=min(res,rec((x+y-1)//y)+abs(x-(((x+y-1)//y)*y))*D+cost)
            
        memo[x]=res
        return res
    print(rec(N))

T=int(input())
for i in range(T):
    solve()

Submission status: Accepted

Solution code:
from math import floor,ceil
import sys
sys.setrecursionlimit(10**7)
def solve():
    N,A,B,C,D=map(int,input().split())
    memo={}
    def dist(n):
        if n in memo:
            return memo[n]
        if n==1:
            return D
        if n==0:
            return 0
        res = 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]=res
        return res
    print(dist(N))

T=int(input())
for i in range(T):
    solve()

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)
@lru_cache(maxsize=None)
def dfs(N,A,B,C,D):
  ans=N*D
  for x, y in [(2, A), (3, B), (5, C)]:
    if N%x==0:
      N0=N//x
      a=dfs(N0,A,B,C,D)+y
      ans=min(a,ans)
    elif x<=N:
      z=N%x
      N0=(N-z)//x
      N1=(N-z+x)//x
      a=dfs(N0,A,B,C,D)+z*D+y
      b=dfs(N1,A,B,C,D)+((x-z)*D)+y
      ans=min(a,b,ans)
  return ans
T=int(input())
for _ in range(T):
  N,A,B,C,D=map(int,input().split())
  print(dfs(N,A,B,C,D))

Submission status: Accepted

Solution code:
t=int(input())
from functools import lru_cache
for _ in range(t):
    n,a,b,c,d=map(int,input().split())
    @lru_cache(maxsize=100000)
    def f(n):
        if n==0:
            return 0
        if n==1:
            return d
        ans=d*n
        q,r=divmod(n,2)
        if r==0:
            ans=min(ans,f(q)+a+d*r)
        else:
            ans=min(ans,f(q)+a+d*r,f(q+1)+a+d*(2-r))
        q,r=divmod(n,3)
        if r==0:
            ans=min(ans,f(q)+b+d*r)
        else:
            ans=min(ans,f(q)+b+d*r,f(q+1)+b+d*(3-r))
        q,r=divmod(n,5)
        if r==0:
            ans=min(ans,f(q)+c+d*r)
        else:
            ans=min(ans,f(q)+c+d*r,f(q+1)+c+d*(5-r))
        return ans
    print(f(n))

Submission status: Accepted

Solution code:
t = int(input())

import sys
sys.setrecursionlimit(10 ** 6)

def calc(x):
    if x in dp:
        return dp[x]
    
    divs = [5, 3, 2]
    costs = [c, b, a]
    res = d * x
    for div, cost in zip(divs, costs):
        dived = x//div
        res = min(res, calc(dived) + cost + abs(x-dived*div) * d)
        if x > div:
            dived = x//div+1
            res = min(res, calc(dived) + cost + abs(x-dived*div) * d)
    dp[x] = res
    return res

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

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


t = I()
for _ in range(t):
    n, a, b, c, d = LI()
    memo = {0: 0, 1: d}
    def dfs(x):
        if x in memo:
            return memo[x]
        ret = x * d
        ret = min(ret, min(dfs(x // 2), dfs((x - 1) // 2 + 1)) + a + d * (x % 2))
        ret = min(ret, min(dfs(x // 3) + b + d * (x % 3), dfs((x - 1) // 3 + 1) + b + d * (-x % 3)))
        ret = min(ret, min(dfs(x // 5) + c + d * (x % 5), dfs((x - 1) // 5 + 1) + c + d * (-x % 5)))
        memo[x] = ret
        return ret

    print(dfs(n))

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache

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 rec(n):
        if n == 0:
            return 0

        min_ = n * D
        min_ = min(min_, (n % 2) * D + A + rec(n // 2))
        if n // 2 + 1 != n:
            min_ = min(min_, (2 - n % 2) * D + A + rec(n // 2 + 1))

        min_ = min(min_, (n % 3) * D + B + rec(n // 3))
        if n // 3 + 1 != n:
            min_ = min(min_, (3 - n % 3) * D + B + rec(n // 3 + 1))

        min_ = min(min_, (n % 5) * D  + C + (rec(n // 5)))
        if n // 5 + 1 != n:
            min_ = min(min_, (5 - n % 5) * D + C + rec(n // 5 + 1))

        return min_

    print(rec(N))

Submission status: Accepted

Solution code:
#import sys
#sys.setrecursionlimit(20000)

times = int(input())
x = []
for t in range(times):
    x.append(list(map(int, input().split())))


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
    elif n%2 == 1:
        n2 = min(f((n-1) // 2) + d, f((n+1) // 2) + d) + a

    if n%3 == 0:
        n3 = f(n // 3) + b
    elif n%3 == 1:
        n3 = min(f((n-1) // 3) + d, f((n+2) // 3) + 2*d) + b
    elif n%3 == 2:
        n3 = min(f((n-2) // 3) + 2*d, f((n+1) // 3) + d) + b

    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
    elif n%5 == 4:
        n5 = min(f((n-4) // 5) + 4*d, f((n+1) // 5) + d) + c

    Y = min(n2, n3, n5, n*d)
    dic[n] = Y
    return Y


for t in range(times):
    n, a, b, c, d = x[t][0], x[t][1], x[t][2], x[t][3], x[t][4]
    dic = {}
    print(f(n))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc044/submissions/13542551

def main():
    from heapq import heappush, heappop

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

        h = [(0, N)]  # cost,value
        checked = set()

        ans = N * D + 1
        while h:
            cost, x = heappop(h)
            if cost >= ans: continue
            if x in checked: continue
            checked.add(x)

            # 0まで1ずつ減らす
            ans = min(ans, cost + x * D)

            for d, c in ((2, A), (3, B), (5, C)):
                # すでにheapqからnxがpopしていれば
                # より低コストでnxを生成できているので
                # nxの生成は不要
                nx, r = divmod(x, d)
                if nx not in checked:
                    heappush(h, (cost + r * D + c, nx))
                if (r > 0) and ((nx + 1) not in checked):
                    heappush(h, (cost + (d - r) * D + c, nx + 1))

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc044/submissions/13542551

def main():
    from heapq import heappush, heappop

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

        h = [(0, N)]  # cost,value
        checked = set()

        ans = N * D + 1
        while h:
            cost, x = heappop(h)
            if cost >= ans: continue
            if x in checked: continue
            checked.add(x)

            # 0まで1ずつ減らす
            if ans > cost + x * D:
                ans = cost + x * D

            for d, c in ((2, A), (3, B), (5, C)):
                # すでにheapqからnxがpopしていれば
                # より低コストでnxを生成できているので
                # nxの生成は不要
                nx, r = divmod(x, d)
                if nx not in checked:
                    heappush(h, (cost + r * D + c, nx))
                if (r > 0) and ((nx + 1) not in checked):
                    heappush(h, (cost + (d - r) * D + c, nx + 1))

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000)

times = int(input())
n, a, b, c, d = list(), list(), list(), list(), list()
for t in range(times):
    x = list(map(int, input().split()))
    n.append(x[0])
    a.append(x[1])
    b.append(x[2])
    c.append(x[3])
    d.append(x[4])


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
    elif N%2 == 1:
        N2 = min(f((N-1) // 2) + D, f((N+1) // 2) + D) + A

    if N%3 == 0:
        N3 = f(N // 3) + B
    elif N%3 == 1:
        N3 = min(f((N-1) // 3) + D, f((N+2) // 3) + 2*D) + B
    elif N%3 == 2:
        N3 = min(f((N-2) // 3) + 2*D, f((N+1) // 3) + D) + B

    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
    elif N%5 == 4:
        N5 = min(f((N-4) // 5) + 4*D, f((N+1) // 5) + D) + C

    Y = min(N2, N3, N5, N*D)
    dic[N] = Y
    return Y


for t in range(times):
    N, A, B, C, D = n[t], a[t], b[t], c[t], d[t]
    dic = {}
    print(f(N))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc044/submissions/13542551

def main():
    from heapq import heappush, heappop

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

        h = [(0, N)]  # cost,value
        checked = set()

        ans = N * D + 1
        while h:
            cost, x = heappop(h)
            if cost >= ans: continue
            if x in checked: continue
            checked.add(x)

            # 0まで1ずつ減らす
            if ans > cost + x * D:
                ans = cost + x * D

            for d, c in ((2, A), (3, B), (5, C)):
                # すでにheapqからnxがpopしていれば
                # より低コストでnxを生成できているので
                # nxの生成は不要
                nx, r = divmod(x, d)
                if nx not in checked:
                    heappush(h, (cost + r * D + c, nx))
                if (nx + 1) not in checked:
                    heappush(h, (cost + (d - r) * D + c, nx + 1))

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from functools import lru_cache

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

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

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**7)

t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    memo = {0: 0, 1: d}
    def cost(N):
        if N in memo:
            return memo[N]
        ans = N * d
        ks = [2, 3, 5]
        abc = [a, b, c]
        for i in range(3):
            k = ks[i]
            coin = abc[i]
            div, mod = divmod(N, k)
            pay = mod * d + coin

            # D枚コインを払って1だけ増減させる。
            # その際に行き着く先として、div(減らす場合) or div+1(増やす場合)
            # 増やす場合は、現在の状態から、最寄りの倍数まで足す必要があり、これはmodからkまでの距離と等しい。
            ans = min(ans, pay + cost(div))
            if mod == 0:
                continue
            pay = (k - mod) * d + coin
            ans = min(ans, pay + cost(div + 1))
        memo[N] = ans
        return ans
    print(cost(n))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import deque
import heapq

t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    hq = []
    memo = dict()
    memo[n] = 0
    heapq.heappush(hq, -n)
    while hq:
        val = -heapq.heappop(hq)
        for base, cost in zip([2, 3, 5], (a, b, c)):
            diff = val % base
            nval_p = val // base
            if nval_p in memo:
                # use half div
                memo[nval_p] = min(memo[nval_p], memo[val] + cost + d * diff)
                # walk
                memo[nval_p] = min(memo[nval_p], memo[val] + (val - nval_p) * d)
            else:
                heapq.heappush(hq, -nval_p)
                # use half div
                memo[nval_p] = min(memo[val] + cost + d * diff, memo[val] + (val - nval_p) * d)
            if val % base != 0:
                nval_n = ((val - diff + base) // base)
                if nval_n in memo:
                    memo[nval_n] = min(memo[nval_n], memo[val] + cost + d * (base - diff))
                    # walk
                    memo[nval_n] = min(memo[nval_n], memo[val] + (val - nval_n) * d)
                else:
                    heapq.heappush(hq, -nval_n)
                    memo[nval_n] = min(memo[val] + cost + d * (base - diff), memo[val] + (val - nval_n) * d)
    print(memo[0])

Submission status: Accepted

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

def solve(x,a,b,c,d):
    @lru_cache(None)
    def dfs(x):
        if x == 0:
            return 0
        if x == 1:
            return d
        l2 = x//2
        r2 = (x+1)//2
        l3 = x//3
        r3 = (x+2)//3
        l5 = x//5
        r5 = (x+4)//5
        count = x*d
        count = min(count,abs(l2*2-x)*d+a+dfs(l2))
        count = min(count,abs(r2*2-x)*d+a+dfs(r2))
        count = min(count,abs(l3*3-x)*d+b+dfs(l3))
        count = min(count,abs(r3*3-x)*d+b+dfs(r3))
        count = min(count,abs(l5*5-x)*d+c+dfs(l5))
        count = min(count,abs(r5*5-x)*d+c+dfs(r5))
        return count
    return dfs(x)
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:
from functools import lru_cache

T = int(input())

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

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

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

        return ret

    print(dist(N))

Submission status: Accepted

Solution code:
#https://wakabame.hatenablog.com/entry/2020/05/24/031143

#from collections import defaultdict
#from pprint import pprint
#from collections import deque
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
#import numpy as np
#import math
# = map(int,input().split())

# = list(map(int,input().split()))

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

def func(i):
    if i == 0:
        return 0
    elif i == 1:
        return d
    elif i in memo:
        return memo[i]
    else:
        min_val = int(min(
            d*i,
            d*abs(i-i//2*2) + a + func(i//2),
            d*abs(i-(i+1)//2*2) + a + func((i+1)//2),
            d*abs(i-i//3*3) + b + func(i//3),
            d*abs(i-(i+2)//3*3) + b + func((i+2)//3),
            d*abs(i-i//5*5) + c + func(i//5),
            d*abs(i-(i+4)//5*5) + c + func((i+4)//5)
        ))

    memo[i] = min_val
    return min_val



t = int(input())

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


for i in range(t):
    n = nabcd[i][0]
    a = nabcd[i][1]
    b = nabcd[i][2]
    c = nabcd[i][3]
    d = nabcd[i][4]

    memo = {}


    print(func(n))
    #print(memo)

Submission status: Accepted

Solution code:

#from collections import defaultdict
#from pprint import pprint
#from collections import deque
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(N) #N回まで再起を許可する。
#import numpy as np
#import math
# = map(int,input().split())

# = list(map(int,input().split()))

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

def func(i):
    if i == 0:
        return 0
    elif i == 1:
        return d
    elif i in memo:
        return memo[i]
    else:
        min_val = int(min(
            d*i,
            d*abs(i-i//2*2) + a + func(i//2),
            d*abs(i-(i+1)//2*2) + a + func((i+1)//2),
            d*abs(i-i//3*3) + b + func(i//3),
            d*abs(i-(i+2)//3*3) + b + func((i+2)//3),
            d*abs(i-i//5*5) + c + func(i//5),
            d*abs(i-(i+4)//5*5) + c + func((i+4)//5)
        ))

    memo[i] = min_val
    return min_val



t = int(input())

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


for i in range(t):
    n = nabcd[i][0]
    a = nabcd[i][1]
    b = nabcd[i][2]
    c = nabcd[i][3]
    d = nabcd[i][4]

    memo = {}


    print(func(n))
    #print(memo)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def dfs(x):
    if x == 0:
        return 0
    if x == 1:
        return d
    if x in dic:
        return dic[x]
    l2 = x//2
    r2 = (x+1)//2
    l3 = x//3
    r3 = (x+2)//3
    l5 = x//5
    r5 = (x+4)//5
    count = min(x*d,10**18)
    count = min(count,abs(l2*2-x)*d+a+dfs(l2))
    count = min(count,abs(r2*2-x)*d+a+dfs(r2))
    count = min(count,abs(l3*3-x)*d+b+dfs(l3))
    count = min(count,abs(r3*3-x)*d+b+dfs(r3))
    count = min(count,abs(l5*5-x)*d+c+dfs(l5))
    count = min(count,abs(r5*5-x)*d+c+dfs(r5))
    dic[x] = count
    return count

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

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
from functools import lru_cache
def input(): return sys.stdin.readline().strip()


def main():

    """
    0から出発してNになるようにすると2^a 3^b 5^cをあらかじめ求めておかないといけなくて大変だったが
    Nから出発して0に向かうようにすれば数字がどんどん小さくなるから前計算不要なのか。。。

    そして\pm 1を掛け算のたびに挟むことになるから手詰まりになっていたけど、
    次の割り算をするのに、割り切れる数まで\pm 1してからさらに\pm 1をするのは確実に無駄とわかるから
    （\pm 1で移動→割り算）を１セットにして再帰してやれば確実に小さくなっていく！
    最後あたりに無限ループが起きる可能性があるから、そこは適切に処理すればよい。
    """

    T = int(input())
    for _ in range(T):
        N, a, b, c, d = map(int, input().split())

        @lru_cache(maxsize=None)
        def func(n):
            if n == 0: return 0
            if n == 1: return d
            val1 = func(n // 2) + a + d * (n % 2)
            val2 = func(n // 2 + 1) + a + d * (2 - (n % 2)) if n % 2 != 0 else float("inf")
            val3 = func(n // 3) + b + d * (n % 3)
            val4 = func(n // 3 + 1) + b + d * (3 - (n % 3)) if n % 3 != 0 else float("inf")
            val5 = func(n // 5) + c + d * (n % 5)
            val6 = func(n // 5 + 1) + c + d * (5 - (n % 5)) if n % 5 != 0 else float("inf")
            return min(val1, val2, val3, val4, val5, val6, d * n)
        
        print(func(N))


if __name__ == "__main__":
    main()