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 collections import deque
import sys
sys.setrecursionlimit(10**7)
t = int(input())
memo = dict()
def calc(n):
    global a,b,c,d
    #print(n)
    if n in memo:
        return memo[n]
    if n <= 0:
        return 0
    elif n == 1:
        return d
    res = d * n
    #何らかの操作を行った後、2で割る
    if n % 2 == 0:
        res = min(res, calc(n//2) + a)
    else:
        res = min(res, calc((n + 1)//2) + a + d, calc((n - 1)//2) + a + d)
    
    if n % 3 == 0:
        res = min(res, calc(n//3) + b)
    else:
        res = min(res, calc((n - (n % 3))//3) + b + d * (n % 3),
         calc((n + (3 - (n % 3)))//3) + b + d * (3 - (n % 3)))

    
    if n % 5 == 0:
        res = min(res, calc(n//5) + c)
    else:
        res = min(res, calc((n - (n % 5))//5) + c + d * (n % 5),
         calc((n + (5 - (n % 5)))//5) + c + d * (5 - (n % 5)))
    memo[n] = res
    #print("n : {} ,  res : {}".format(n,memo[n]))
    return memo[n]

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

Submission status: Accepted

Solution code:
T = int(input())

def f(N, A, B, C, D):
  if N == 0:
    return 0
  elif N == 1:
    return D
  elif N in data:
    return data[N]
  else:
    cost = min(
      D * N,
      D * abs(N - (N // 2) * 2) + A + f(N//2, A, B, C, D),
      D * abs(N - ((N + 1)// 2) * 2) + A + f((N + 1)// 2, A, B, C, D),
      D * abs(N - (N // 3) * 3) + B + f(N//3, A, B, C, D),
      D * abs(N - ((N + (N % 3)) // 3) * 3) + B + f((N + (N % 3)) // 3, A, B, C, D),
      D * abs(N - (N // 5) * 5) + C + f(N//5, A, B, C, D),
      D * abs(N - ((N + (N % 5)) // 5) * 5) + C + f((N + (N % 5))//5, A, B, C, D)
    )
    data[N] = cost
    return cost
  
for _ in range(T):
  N, A, B, C, D = list(map(int, input().split()))
  data = {}
  print(f(N, A, B, C, D))

Submission status: Accepted

Solution code:
T = int(input())

while(T > 0):
    N, A, B, C, D = map(int, input().split())
    dp = {}

    def d(n):
        if n == 0:
            return 0
        if n == 1:
            return D

        if n in dp:
            return dp[n]

        ret = min(
            D * n,
            D * abs(n - (n // 2) * 2) + A + d(n // 2),
            D * abs(n - ((n+1) // 2) * 2) + A + d((n+1) // 2),
            D * abs(n - (n // 3) * 3) + B + d(n // 3),
            D * abs(n - ((n + 2) // 3) * 3) + B + d((n + 2) // 3),
            D * abs(n - (n // 5) * 5) + C + d(n // 5),
            D * abs(n - ((n + 4) // 5) * 5) + C + d((n + 4) // 5),
        )

        dp[n] = ret
        return ret

    print(d(N))
    T -= 1

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict
import math

def solve(n):
    q = deque()
    q.append(n)#n追加
    #dict[m] = mからNにするまで必要な費用
    dist = defaultdict(lambda: float('inf'))#無限個を無限で埋める
    dist[n] = 0#nにする費用は0
    while len(q):
        m = q.popleft()

        if m == 0:#0ならやめる
            continue
        if m == 1:#1のとき多分おかしくなるのでやっとく
            if dist[0] > dist[1] + d:
                dist[0] = dist[1] + d
                continue
        
        #5,3,2で割る
        for x,cost in ([5,c],[3,b],[2,a]):

            y = m%x #余り
            e = 1 if y else 0 #余りあるとき1
            #割り切れる数まで減らすor割り切れるなら普通に割る
            hiyou = min((n-(m//x))*d,dist[m]+cost+(e*d*y),dist[m]+ (m-(m//x))*d)#今の値から遷移するか+1し続けたときの安い方
            if dist[m//x] > hiyou:
                q.append(m//x)
                dist[m//x] = hiyou

            #割り切れる数まで増やす
            hiyou = min((n-(m//x)+1)*d,dist[m]+cost+((x-y)*d),dist[m]+ (m-(m//x-1))*d)
            if e and dist[m//x+1]> hiyou:
                q.append(m//x+1)
                dist[m//x+1] = hiyou
    

    return dist[0]


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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

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 rec(u):
    if dist[u] != INF:
        return dist[u]
    if u == 0:
        return 0
    res = abs(u)*d
    if u >= 5:
        x = u % 5
        v = (u-x) // 5
        res = min(res, rec(v) + c+d*x)
        if u % 5 != 0:
            x = 5 - u % 5
            v = (u+x) // 5
            res = min(res, rec(v) + c+d*x)
    if u >= 3:
        x = u % 3
        v = (u-x) // 3
        res = min(res, rec(v) + b+d*x)
        if u % 3 != 0:
            x = 3 - u % 3
            v = (u+x) // 3
            res = min(res, rec(v) + b+d*x)
    if u >= 2:
        x = u % 2
        v = (u-x) // 2
        res = min(res, rec(v) + a+d*x)
        if u % 2 != 0:
            x = 2 - u % 2
            v = (u+x) // 2
            res = min(res, rec(v) + a+d*x)
    dist[u] = res
    return res

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

    dist = defaultdict(lambda: INF)
    ans = rec(N)
    print(ans)

Submission status: Accepted

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


def read():
    N, A, B, C, D = map(int, input().strip().split())
    return N, A, B, C, D


def solve(N, A, B, C, D, INF=10**28):

    cmin = N * D
    cache = dict()
    cache[0] = 0
    cache[1] = D
    cache[2] = min(D+D, D+A)
    
    def dfs(n):
        if n in cache:
            return cache[n]
        c = n * D
        c = min(c, dfs(n//2) + A + (n%2) * D)
        c = min(c, dfs(n//2+1) + A + ((-n-1)%2+1) * D)
        c = min(c, dfs(n//3) + B + (n%3) * D)
        c = min(c, dfs(n//3+1) + B + ((-n-1)%3+1) * D)
        c = min(c, dfs(n//5) + C + (n%5) * D)
        c = min(c, dfs(n//5+1) + C + ((-n-1)%5+1) * D)
        cache[n] = c
        return c
    
    return min(cmin, dfs(N))


if __name__ == '__main__':
    T = int(input().strip())
    for i in range(T):
        inputs = read()
        outputs = solve(*inputs)
        if outputs is not None:
            print("{}".format(outputs))

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
    from collections import defaultdict

    que = [(0, src)]
    dist = defaultdict(lambda: INF)
    dist[src] = 0
    while que:
        cost, u = heappop(que)
        dist[0] = min(dist[0], cost+abs(u)*d)
        if u >= 5:
            x = u % 5
            v = (u-x) // 5
            if 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 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 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 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 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 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 = res[0]
    print(ans)

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 0 not in dist or dist[0] > cost+abs(u)*d:
            dist[0] =  cost+abs(u)*d
        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 = res[0]
    print(ans)

Submission status: Accepted

Solution code:
T = int(input())
for _ in range(T):
  N,a,b,c,d = map(int, input().split())
  
  memo = {}
  def solve(n):
    if n == 0:
      return 0
    if n == 1:
      return d
    if n in memo:
      return memo[n]
    tmp = n * d
    if n % 2 == 0:
      tmp = min(tmp, a + solve(n//2))
    else:
      tmp =  min(tmp, a + d + solve(n//2), a + d + solve(n//2+1))
    if n % 3 == 0:
      tmp = min(tmp, b + solve(n//3))
    else:
      ret1 = n % 3
      ret2 = 3 - ret1
      tmp = min(tmp, b + d*ret1 + solve(n//3), b + d*ret2 + solve(n//3+1))
    if n % 5 == 0:
      tmp = min(tmp, c + solve(n//5))
    else:
      ret1 = n % 5
      ret2 = 5 - ret1
      tmp = min(tmp, c + d*ret1 + solve(n//5), c + d*ret2 + solve(n//5+1))
    memo[n] = tmp
    return memo[n]
    
  print(solve(N))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

minCoin = 0
N = 0
A = 0
B = 0
C = 0
D = 0
memo = []

def main():
    T = int(input())
    for _ in range(T):
        global minCoin,N,A,B,C,D,memo
        N,A,B,C,D  = map(int, input().split()) 
        memo = {}
        minCoin = N*D
        bfs(N,0)
        print(minCoin)

def bfs(tempX,tempC):
    global minCoin,N,A,B,C,D,memo
    if(tempC>=minCoin):
        return
    
    minCoin = min(tempC+(D*tempX),minCoin)

    if(tempX==1):
        return

    if(tempX in memo):
        if tempC < memo[tempX]:
            memo[tempX] = tempC
        else:
            return
    else:
        memo[tempX] = tempC


    if(tempX%2==0):
        bfs(tempX//2,tempC+A)
    else:
        bfs((tempX+1)//2,tempC+A+D)
        bfs((tempX-1)//2,tempC+A+D)
    if(tempX%3==0):
        bfs(tempX//3,tempC+B)
    else:
        mod = tempX%3
        bfs((tempX-mod+3)//3,tempC+B+(D*(3-mod)))
        bfs((tempX-mod)//3,tempC+B+(D*mod))
    if(tempX%5==0):
        bfs(tempX//5,tempC+C)
    else:
        mod = tempX%5
        bfs((tempX-mod+5)//5,tempC+C+(D*(5-mod)))
        bfs((tempX-mod)//5,tempC+C+(D*mod))





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#c=float('inf')
v={}
def rec(n,a,b,c,d):
    if n in v:
        return v[n]
    x=float('inf')
    if n==0:
        return 0
    if n==1:
        return d
    x=n*d
    if n%2==0:
            x=min(x,rec(n//2,a,b,c,d)+a)
    else:
            low=n//2
            up=n//2+1
            x=min(x,rec(low,a,b,c,d)+d*(n-low*2)+a)
            x=min(x,rec(up,a,b,c,d)+d*(up*2-n)+a)
    if n%3==0:
            x=min(x,rec(n//3,a,b,c,d)+b)
    else:
            low=n//3
            up=n//3+1
            x=min(x,rec(low,a,b,c,d)+d*(n-low*3)+b)
            x=min(x,rec(up,a,b,c,d)+d*(up*3-n)+b)
    if n%5==0:
            x=min(x,rec(n//5,a,b,c,d)+c)
    else:
            low=n//5
            up=n//5+1
            x=min(x,rec(low,a,b,c,d)+d*(n-low*5)+c)
            x=min(x,rec(up,a,b,c,d)+d*(up*5-n)+c)
    v[n]=x
    return x

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

Submission status: Accepted

Solution code:
_, *e = [[*map(int, t.split())] for t in open(0)]

for n, a, b, c, d in e:
    mem = {0: 0, 1: d}
    mult_cost = {2: a, 3: b, 5: c}

    def solve(n):
        if n not in mem:
            tmp = n*d
            for k in mult_cost:
                if n % k == 0:
                    tmp = min(tmp, solve(n//k) + mult_cost[k])
                else:
                    tmp = min(tmp, solve(
                        n//k) + mult_cost[k] + (n % k)*d, solve(n//k + 1) + mult_cost[k] + k*d - (n % k)*d)
            mem[n] = tmp
        return mem[n]

    print(solve(n))

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = 10**20

def solve(N,A,B,C,D):
    memo = dict()
    def rec(n):
        if n in memo:
            return memo[n]
        elif n==0:
            return 0
        elif n==1:
            return D
        
        ret = D * n
        if n%2==0:
            ret = min(ret, rec(n//2)+A)
        else:
            ret = min(ret, rec(n//2)+A+D, rec(n//2+1)+A+D)
        
        if n%3==0:
            ret = min(ret, rec(n//3)+B)
        else:
            ret = min(ret, rec(n//3)+B+D*(n%3), rec(n//3+1)+B+D*(3-n%3))
        
        if n%5==0:
            ret = min(ret, rec(n//5)+C)
        else:
            ret = min(ret, rec(n//5)+C+D*(n%5), rec(n//5+1)+C+D*(5-n%5))
        
        memo[n] = ret
        return ret    
    return rec(N)

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

for a in answer:
    print(a)

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

T = int(input())


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


    def f(n):
        if n == 0:
            return 0
        if n == 1:
            return D
        if n in memo.keys():
            return memo[n]

        ret = 1 << 100
        ret = min(ret, f(n // 2) + (n - n // 2 * 2) * D + A, f(n // 2) + (n - n // 2) * D)
        ret = min(ret, f(n // 3) + (n - n // 3 * 3) * D + B, f(n // 3) + (n - n // 3) * D)
        ret = min(ret, f(n // 5) + (n - n // 5 * 5) * D + C, f(n // 5) + (n - n // 5) * D)
        ret = min(ret, f((n + 1) // 2) + ((n + 1) // 2 * 2 - n) * D + A, f((n + 1) // 2) + (n - (n + 1) // 2) * D)
        ret = min(ret, f((n + 2) // 3) + ((n + 2) // 3 * 3 - n) * D + B, f((n + 2) // 3) + (n - (n + 2) // 3) * D)
        ret = min(ret, f((n + 4) // 5) + ((n + 4) // 5 * 5 - n) * D + C, f((n + 4) // 5) + (n - (n + 4) // 5) * D)
        memo[n] = ret
        return ret

    print(f(N))

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

from heapq import heappush, heappop

def calc(N, A, B, C, D):
    abc = list(map(lambda x: (x[0], x[1], x[0]*x[1]/((x[0]-1)*D)) ,[(2, A), (3, B), (5, C),]))
    ans = N * D
    ans2 = min(2*D, D+A)

    dq = []

    heappush(dq, (0, N))
    seen = set()
    while dq:
        cost, rest = heappop(dq)

        if rest in seen:
            continue
        else:
            seen.add(rest)

        if rest <= 2:
            if rest == 1:
                cost += D
            elif rest == 2:
                cost += ans2
            else:
                cost += -rest * D
            ans = min(ans, cost)
            continue

        if cost >= ans:
            continue

        for r, co1, n2 in abc:
            if rest < n2:
                ans = min(ans, rest*D + cost)
                continue

            a1, a2 = divmod(rest, r)

            if a2 == 0:
                heappush(dq, (cost+co1, a1))
                continue

            a3 = r - a2
            if a2 == a3:
                heappush(dq, (cost + co1 + a3*D, a1+1))
            elif a2 > a3:
                a1 += 1
                a2 = a3

            heappush(dq, (cost + co1 + a2*D, a1))

    return ans


def resolve():
    T = int(input())
    S = [list(iim()) for i in range(T)]


    ans = []
    for s in S:
        ans.append(calc(*s))

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    memo = {}
    def f(x):
        if x in memo:
            return memo[x]
        if x == 0:
            return 0
        if abs(x) == 1:
            return d

        ans = [x * d]
        if x % 2 == 0:
            ans.append(f(x // 2) + a)
        else:
            ans.append(f((x+1) // 2) + a + d)
            ans.append(f((x-1) // 2) + a + d)

        if x % 3 == 0:
            ans.append(f(x // 3) + b)
        elif x % 3 == 1:
            ans.append(f((x-1) // 3) + b + d)
        elif x % 3 == 2:
            ans.append(f((x+1) // 3) + b + d)

        if x % 5 == 0:
            ans.append(f(x // 5) + c)
        elif x % 5 == 1:
            ans.append(f((x-1) // 5) + c + d)
        elif x % 5 == 2:
            ans.append(f((x-2) // 5) + c + 2 * d)
        elif x % 5 == 3:
            ans.append(f((x+2) // 5) + c + 2 * d)
        elif x % 5 == 4:
            ans.append(f((x+1) // 5) + c + d)

        memo[x] = min(ans)
        return memo[x]

    print(f(n))

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(10**6)


def main():
    T = int(input())
    TESTCASEs = [list(map(int, input().split())) for _ in range(T)]


    def calc_cost(N, A, B, C, D):


        @lru_cache(maxsize=None)
        def calc(N):
            if N == 0:
                return 0
            if N == 1:
                return D

            cost = N * D
            
            for T, Tcost in ((2, A), (3, B), (5, C)):
                div, mod = divmod(N, T)

                cost = min(cost, calc(div) + Tcost + mod * D)
                if mod:
                    cost = min(cost, calc(div + 1) + Tcost + (T - mod) * D)

            return cost


        return calc(N)


    for TESTCASE in TESTCASEs:
        total_cost = calc_cost(*TESTCASE)
        print(total_cost)


if __name__ == '__main__':
    main()

sys.exit()

Submission status: Accepted

Solution code:
T=int(input())
for i in range(T):
  N,a,b,c,d=map(int, input().split())
  memo={}
  memo[0]=0
  memo[1]=d
  
  def f(n):
    if n in memo:
      return memo[n]
    e2,e3,e5=n%2,n%3,n%5
    dd=min(d*n,d*e2+a+f((n-e2)//2),d*e2+a+f((n+e2)//2),d*e3+b+f((n-e3)//3),d*(3-e3)+b+f((n+3-e3)//3),d*e5+c+f((n-e5)//5),d*(5-e5)+c+f((n+5-e5)//5))
    memo[n]=dd
    return dd
  print(f(N))

Submission status: Accepted

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

    def dist(n):
        if n==0:
            return 0
        if n==1:
            return D
        if n in memo:
            return memo[n]

        ret = min(
            D*n,
            D*abs(n-(n//5)*5)+C+dist(n//5),
            D*abs(n-(n+4)//5*5)+C+dist((n+4)//5),
            D*abs(n-n//3*3)+B+dist(n//3),
            D*abs(n-(n+2)//3*3)+B+dist((n+2)//3),
            D*abs(n-n//2*2)+A+dist(n//2),
            D*abs(n-(n+1)//2*2)+A+dist((n+1)//2)
        )
        memo[n]=ret
        return ret
    print(dist(N))

Submission status: Accepted

Solution code:
from collections import defaultdict
def f(n):
    if memo[n]!=float('inf'):
        return memo[n]
    if n==0:
        return 0
    if n==1:
        return D
    ans=n*D
    for x,c in [(2,A),(3,B),(5,C)]:
        ans=min(ans,f(n//x)+c+n%x*D)
        if n%x:
            ans=min(ans,f(n//x+1)+c+(x-n%x)*D)
    memo[n]=ans
    return memo[n]
T=int(input())
for _ in range(T):
    N,A,B,C,D=map(int,input().split())
    memo=defaultdict(lambda :float('inf'))
    print(f(N))

Submission status: Accepted

Solution code:
def pay(n, a, b, c, d):
    ops = ((2, a), (3, b), (5, c))
    dp = {0:0, 1:d, 2:d + min(a, d)}
    
    def helper(n):
        if n in dp:
            return dp[n]
        
        m = min(op[1] + min(helper(n//op[0]) + (n-n//op[0]*op[0])*d, 
                helper(-(-n//op[0])) + ((-(-n//op[0]))*op[0]-n)*d) for op in ops)
        m = min(n*d, m)
        dp[n] = m
        return m
        
    return helper(n)

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

Submission status: Accepted

Solution code:
from math import ceil,floor,log
#from decimal import Decimal,ROUND_CEILING,ROUND_FLOOR,getcontext
from heapq import *
import sys
input=sys.stdin.readline
T=int(input())
cases=[list(map(int,input().split())) for _ in range(T)]
#getcontext().prec=20
num=0
cnt=0
def main():
    for i in cases:
        l2=[0]*3
        N,l2[0],l2[1],l2[2],D=i
        d = {}
        num=0
        cnt=0
        for j in range(60):         #2の累乗
            for k in range(38):     #3の累乗
                for l in range(26): #5の累乗
                    div=pow(2,j)*pow(3,k)*pow(5,l)
                    x=N//div
                    #x=Decimal(N)/Decimal(div)
                    if N%div!=0:
                        c=x+1
                    else:
                        c=x
                    f=x
                    if d.get(c)==None:
                        d[c]=float("inf")
                    if d.get(f)==None:
                        d[f]=float("inf")
        d[N]=0
        #print(d)
        q=[]
        q.append((0,N))
        heapify(q)
        #print(d)
        while True:
            dist,u=heappop(q)
            if d[u]<dist: continue
            if u==0:
                print(dist)
                break
            for j in range(3):
                num=1+pow(2,j)
                cnt=l2[j]
                x =u//num
                if u%num!=0:
                    v1 = x+1
                else:
                    v1 = x
                v2 = x
                # v1=ceil(u/2)
                # v2=floor(u/2)
                alt1 = d[u] + min(cnt+((num-(u%num))%num)*D,(u-v1)*D)
                alt2 = d[u] + min(cnt+(u%num)*D,(u-v2)*D)
                if d[v1] > alt1:
                    d[v1] = alt1
                    heappush(q, (alt1, v1))
                if d[v2] > alt2:
                    d[v2] = alt2
                    heappush(q, (alt2, v2))
            #print(d)
            #input()
        #print(d[0])
        #print(len(d))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# この回答は
# mnbvmar さんの回答を参考に実装してる
# https://atcoder.jp/contests/agc044/submissions/13537408
# 自力で解法を得たわけではない

memo = {}
INF = 10 ** 18

t = int(input())

a = 0
b = 0
c = 0
d = 0

def solve(n):
  global memo, a, b, c, d
  
  if n == 0:
    return 0
  if n in memo:
    return memo[n]
  ans = INF
  
  # ansの最大値の検証
  # n を すべて+1枚で実現できる場合、ans の初期値を変更
  if n <= (INF/d):
    ans = n * d
  
  # d の後に 2で割るケース
  for p in range(-1, 2):
    # p = dとして選択できるパターン
    x = n + p
    if x < 0 or x % 2 != 0:
      continue
    # y = d の後に2で割った値
    y = x // 2
    if y < n:
      ans = min(ans, a + (abs(p) * d) + solve(y))
  
  # d の後に 3で割るケース
  for p in range(-2, 3):
    x = n + p
    if x < 0 or x % 3 != 0:
      continue
    y = x // 3
    if y < n:
      ans = min(ans, b + (abs(p) * d) + solve(y))
  
  # d の後に 5で割るケース
  for p in range(-4, 5):
    x = n + p
    if x < 0 or x % 5 != 0:
      continue
    y = x // 5
    if y < n:
      ans = min(ans, c + (abs(p) * d) + solve(y))
  
  memo[n] = ans
  return ans
    

def test():
  # 1回分の入力受付
  global memo, a, b, c, d
  n, a, b, c, d = map(int, input().split())
  # メモ初期化
  memo = {}
  # 計算し、結果を表示
  #print(n, a, b, c, d)
  print(solve(n))

for i in range(t):
  test()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
def run():
    T = int(input())
    for ii in range(T):
        N, A, B, C, D = map(int, input().split())
        stack = [(0, N)]
        min_num = float('inf')
        visited = {}
        while stack:
            money, current = heappop(stack)
            if current > N:continue
            if current in visited.keys():
                continue
            visited[current] = 0
            if current == 0:break

            for pro, cost in ((2, A), (3, B), (5, C)):
                tmp = current % pro
                next_num1 = (current - tmp)//pro
                next_num2 = (current + pro - tmp)//pro
                cond1 = N >= current + pro - tmp
                if pro == 2:
                    heappush(stack, (min(cost, D * next_num1) + tmp * D + money, next_num1))
                    if next_num2 != tmp:# and (not next_num2 % 3 or not next_num2 % 5):
                        heappush(stack, (min((2 - tmp) * D + cost + money, (next_num2 - tmp) * D + money), next_num2))
                elif pro == 3:
                    heappush(stack, (min(cost, D * (2 * next_num1))+ tmp * D + money, next_num1))
                    #if 2 * next_num2 != tmp:# and (not next_num2 % 2 or not next_num2 % 5):
                    heappush(stack, (min((3 - tmp) * D + cost + money, (2 * next_num2 - 3 + tmp) * D + money), next_num2))
                else:
                    heappush(stack, (min(cost, D * (4 * next_num1))+ tmp * D + money, next_num1))
                    #if 4 * next_num2 != tmp:# and (not next_num2 % 2 or not next_num2 % 3):
                    heappush(stack, (min((5 - tmp) * D + cost + money, (4 * next_num2 - 5 + tmp) * D + money), next_num2))

                #if next_num1 < min_num:
                #    heappush(stack, (min(cost, D * ((pro-1) * next_num1))+ tmp * D + money, next_num1))
                #if next_num2 < min_num and (pro - 1) * next_num2 != tmp and current < 5:
                #    heappush(stack, (min((pro - tmp) * D + cost + money, ((pro-1) * next_num2 - tmp) * D + money), next_num2))
        print(money)
if __name__ == "__main__":
    run()

Submission status: Accepted

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

def dfs(n):
  if n in dic:
    return dic[n]
  ret=n*d
  if n%2==0:
    ret=min(ret,a+dfs(n//2))
  elif n%2==1:
    ret=min(ret,a+d+dfs((n-1)//2))
    ret=min(ret,a+d+dfs((n+1)//2))
  if n%3==0:
    ret=min(ret,b+dfs(n//3))
  elif n%3==1:
    ret=min(ret,b+d+dfs((n-1)//3))
    ret=min(ret,b+2*d+dfs((n+2)//3))
  elif n%3==2:
    ret=min(ret,b+2*d+dfs((n-2)//3))
    ret=min(ret,b+d+dfs((n+1)//3))
  if n%5==0:
    ret=min(ret,c+dfs(n//5))
  elif n%5==1:
    ret=min(ret,c+d+dfs((n-1)//5))
    ret=min(ret,c+4*d+dfs((n+4)//5))
  elif n%5==2:
    ret=min(ret,c+2*d+dfs((n-2)//5))
    ret=min(ret,c+3*d+dfs((n+3)//5))
  elif n%5==3:
    ret=min(ret,c+3*d+dfs((n-3)//5))
    ret=min(ret,c+2*d+dfs((n+2)//5))
  elif n%5==4:
    ret=min(ret,c+4*d+dfs((n-4)//5))
    ret=min(ret,c+d+dfs((n+1)//5))
  dic[n]=ret
  return ret

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