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 heapq
import sys
sys.setrecursionlimit(2000)
def A():
    T = int(input())
    for i in range(T):
        N, A, B, C, D = map(int, input().split())
        memo = {}
        def dfs(n):
            if n == 0:
                return 0
            if n == 1:
                return D
            if n in memo:
                return memo[n]
            l2 = (n//2)*2
            r2 = ((n+1)//2)*2
            l3 = (n//3)*3
            r3 = ((n+2)//3)*3
            l5 = (n//5)*5
            r5 = ((n+4)//5)*5
            res = n*D
            res = min(res, abs(n-l2)*D+A+dfs(l2//2))
            res = min(res, abs(n-r2)*D+A+dfs(r2//2))
            res = min(res, abs(n-l3)*D+B+dfs(l3//3))
            res = min(res, abs(n-r3)*D+B+dfs(r3//3))
            res = min(res, abs(n-l5)*D+C+dfs(l5//5))
            res = min(res, abs(n-r5)*D+C+dfs(r5//5))
            memo[n] = res
            return res
        print(dfs(N))
        # q = [(D, 1)] #increase by 1 is necessary cuz cant multiply by 0
        # heapq.heapify(q)
        # visited = set()
        # while True:
        #     # print(q)
        #     cost, cur = heapq.heappop(q)
        #     if cur == N:
        #         print(cost)
        #         break
        #     visited.add(cur)
        #     elif cur < N:
        #         if cur*2 not in visited:
        #             t = (cost+min(cur*D, A), cur*2)
        #             if t not in q:
        #                 heapq.heappush(q, t)
        #         if cur*3 not in visited:
        #             t = (cost+min(cur*2*D, B), cur*3)
        #             if t not in q:
        #                 heapq.heappush(q, t)
        #         if cur*5 not in visited:
        #             t = (cost+min(cur*4*D, C), cur*5)
        #             if t not in q:
        #                 heapq.heappush(q, t)
        #         if cur+1 not in visited:
        #             if (cost+D, cur+1) not in q:
        #                 heapq.heappush(q, (cost+D, cur+1))
        #     if cur > 0 and cur-1 not in visited:
        #         if (cost+D, cur-1) not in q:
        #             heapq.heappush(q, (cost+D, cur-1))
A()
# N = (2**a+d)*(3**b+e)*(5**c+d)+f
# minimize(a*A+b*B+c*C+*d+e+f)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**7)
import math
for n,a,b,c,d in nabcd:
  memo={0:0,1:d}
  def func(i):
    if i in memo:
      return memo[i]
    ret=math.inf
    ret=min(ret,func(i//2)+a+d*(i%2))
    ret=min(ret,func((i+2-1)//2)+a+d*((2-i%2)%2))
    ret=min(ret,func(i//3)+b+d*(i%3))
    ret=min(ret,func((i+3-1)//3)+b+d*((3-i%3)%3))
    ret=min(ret,func(i//5)+c+d*(i%5))
    ret=min(ret,func((i+5-1)//5)+c+d*((5-i%5)%5))
    ret=min(ret,d*i)
    memo[i]=ret
    return ret
  print(func(n))

Submission status: Accepted

Solution code:
from functools import lru_cache

T = int(input())


def resolver(a, b, c, d):
    @lru_cache(maxsize=None)
    def _resolver(n):
        if n == 0:
            return 0
        elif n == 1:
            return d
        else:
            div5f = n // 5
            div5c = n // -5 * -1
            div3f = n // 3
            div3c = n // -3 * -1
            div2f = n // 2
            div2c = n // -2 * -1
            return min(
                d * n,
                d * abs(n - div5f * 5) + c + _resolver(div5f),
                d * abs(n - div5c * 5) + c + _resolver(div5c),
                d * abs(n - div3f * 3) + b + _resolver(div3f),
                d * abs(n - div3c * 3) + b + _resolver(div3c),
                d * abs(n - div2f * 2) + a + _resolver(div2f),
                d * abs(n - div2c * 2) + a + _resolver(div2c),
            )

    return _resolver


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

Submission status: Accepted

Solution code:
from functools import lru_cache

T = int(input())


def resolver(a, b, c, d):
    @lru_cache(maxsize=None)
    def _resolver(n):
        if n == 0:
            return 0
        elif n == 1:
            return d
        else:
            div5f = n // 5
            div5c = (n + 4) // 5
            div3f = n // 3
            div3c = (n + 2) // 3
            div2f = n // 2
            div2c = (n + 1) // 2
            return min(
                d * n,
                d * abs(n - div5f * 5) + c + _resolver(div5f),
                d * abs(n - div5c * 5) + c + _resolver(div5c),
                d * abs(n - div3f * 3) + b + _resolver(div3f),
                d * abs(n - div3c * 3) + b + _resolver(div3c),
                d * abs(n - div2f * 2) + a + _resolver(div2f),
                d * abs(n - div2c * 2) + a + _resolver(div2c),
            )

    return _resolver


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
def dfs(n):
    if n in dic.keys():
        return dic[n]
    m = n*d
    m = min(dfs((n//2))+(n-(n//2)*2)*d+a,m)
    m = min(dfs(-(-n//2))+(-(-n//2)*2-n)*d+a,m)
    m = min(dfs((n//3))+(n-(n//3)*3)*d+b,m)
    m = min(dfs(-(-n//3))+(-(-n//3)*3-n)*d+b,m)
    m = min(dfs((n//5))+(n-(n//5)*5)*d+c,m)
    m = min(dfs(-(-n//5))+(-(-n//5)*5-n)*d+c,m)
    dic[n] = m
    return m
t = int(input())
for i in range(t):
    n,a,b,c,d = map(int,input().split())
    dic = {0:0,1:d}
    print(dfs(n))

Submission status: Accepted

Solution code:
import math
from functools import lru_cache

T = int(input())


class Resolver:
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    @lru_cache(maxsize=None)
    def resolve(self, n):
        if n == 0:
            return 0
        elif n == 1:
            return self.d
        else:
            div5f = n // 5
            div5c = (n + 4) // 5
            div3f = n // 3
            div3c = (n + 2) // 3
            div2f = n // 2
            div2c = (n + 1) // 2
            return min(
                self.d * n,
                self.d * abs(n - div5f * 5) + self.c + self.resolve(div5f),
                self.d * abs(n - div5c * 5) + self.c + self.resolve(div5c),
                self.d * abs(n - div3f * 3) + self.b + self.resolve(div3f),
                self.d * abs(n - div3c * 3) + self.b + self.resolve(div3c),
                self.d * abs(n - div2f * 2) + self.a + self.resolve(div2f),
                self.d * abs(n - div2c * 2) + self.a + self.resolve(div2c),
            )


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

Submission status: Accepted

Solution code:
from functools import lru_cache

T = int(input())


def gen_dp(a, b, c, d):
    @lru_cache(maxsize=None)
    def dp(n):

        if n == 0:
            return 0
        elif n == 1:
            return d
        else:
            return min(
                d * n,
                d * abs(n - (n // 5 * 5)) + c + dp(n // 5),
                d * abs(n - ((n + 4) // 5 * 5)) + c + dp((n + 4) // 5),
                d * abs(n - (n // 3 * 3)) + b + dp(n // 3),
                d * abs(n - ((n + 2) // 3 * 3)) + b + dp((n + 2) // 3),
                d * abs(n - (n // 2 * 2)) + a + dp(n // 2),
                d * abs(n - ((n + 1) // 2 * 2)) + a + dp((n + 1) // 2),
            )

    return dp


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

Submission status: Accepted

Solution code:
t = int(input())


def dfs(i):
    if i in memo:
        return memo[i]
    memo[i] = 10 ** 18
    s = d * i
    j = i // 5
    s = min(s, dfs(j) + c + d * (i - j * 5))
    j = (i + 4) // 5
    s = min(s, dfs(j) + c + d * (j * 5 - i))

    j = i // 3
    s = min(s, dfs(j) + b + d * (i - j * 3))
    j = (i + 2) // 3
    s = min(s, dfs(j) + b + d * (j * 3 - i))

    j = i // 2
    s = min(s, dfs(j) + a + d * (i - j * 2))
    j = (i + 1) // 2
    s = min(s, dfs(j) + a + d * (j * 2 - i))
    memo[i] = s
    return s


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a = 2, 3, 5

def f(n):
  m = memo.get(n)
  if m is None:
    nd = m = n * d
    for p, c in zip(a, b):
      p *= d
      k, r = divmod(nd, p);
      m = min(m, f(k) + r + c, r and f(k + 1) + p - r + c or m)
    memo[n] = m
  return m

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

Submission status: Accepted

Solution code:
a = 2, 3, 5

def f(n):
  m = memo.get(n)
  if m is None:
    nd = m = n * d
    for p, c in zip(a, b):
      p *= d
      k, r = divmod(nd, p);
      m = min(m, f(k) + r + c, f(k + 1) + p - r + c if r else m)
    memo[n] = m
  return m

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

Submission status: Accepted

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

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

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

        ANS=x*D

        two=x//2*2
        if two//2<x:
            ANS=min(ANS,abs(two-x)*D+A+calc(two//2))
        if two//2+1<x:
            ANS=min(ANS,abs(two+2-x)*D+A+calc(two//2+1))

        three=x//3*3
        if three//3<x:
            ANS=min(ANS,abs(three-x)*D+B+calc(three//3))
        if three//3+1<x:
            ANS=min(ANS,abs(three+3-x)*D+B+calc(three//3+1))

        five=x//5*5
        if five//5<x:
            ANS=min(ANS,abs(five-x)*D+C+calc(five//5))
        if five//5+1<x:
            ANS=min(ANS,abs(five+5-x)*D+C+calc(five//5+1))

        return ANS

    print(calc(N))

Submission status: Accepted

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

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

    DP=[N*D]*(10**5)
    DP[0]=0

    for i in range(10**5):
        for k in range(i-10,i+10):
            if 0<=k<10**5 and DP[k]>DP[i]+abs(i-k)*D:
                DP[k]=DP[i]+abs(i-k)*D
        #if 0<=i+1<10**5 and DP[i+1]>DP[i]+D:
        #    DP[i+1]=DP[i]+D
            
        #if 0<=i-1<10**5 and DP[i-1]>DP[i]+D:
        #    DP[i-1]=DP[i]+D

        if 0<=2*i<10**5 and DP[2*i]>DP[i]+A:
            DP[2*i]=DP[i]+A

        if 0<=3*i<10**5 and DP[3*i]>DP[i]+B:
            DP[3*i]=DP[i]+B

        if 0<=5*i<10**5 and DP[5*i]>DP[i]+C:
            DP[5*i]=DP[i]+C

    @lru_cache(maxsize=None)
    def calc(x):
        if x<=10:
            return DP[x]

        ANS=x*D

        two=x//2*2

        ANS=min(ANS,abs(two-x)*D+A+calc(two//2))
        ANS=min(ANS,abs(two+2-x)*D+A+calc(two//2+1))

        three=x//3*3
        ANS=min(ANS,abs(three-x)*D+B+calc(three//3))
        ANS=min(ANS,abs(three+3-x)*D+B+calc(three//3+1))

        five=x//5*5
        ANS=min(ANS,abs(five-x)*D+C+calc(five//5))
        ANS=min(ANS,abs(five+5-x)*D+C+calc(five//5+1))

        return ANS

    print(calc(N))

Submission status: Accepted

Solution code:
import functools
t = int(input())

@functools.lru_cache(maxsize=None)
def tk(v,a,b,c,d):
    if v == 0:
        return 9999999999
    elif v == 1:
        return d

    pas1 = v // 2
    if v == 2 :
        pas2 = 0  #無限ループ阻止のため
    else:
        pas2 = pas1 + 1 # vが2の時無限ループになる
    pam1 =  v % 2 
    pam2 = 2 - pam1
    pbs1 = v // 3
    pbs2 = pbs1 + 1
    pbm1 = v % 3 
    pbm2 = 3 -pbm1  
    pcs1 = v // 5
    pcs2 = pcs1 +  1
    pcm1 = v % 5 
    pcm2 = 5 - pcm1

    koho_a1 = tk(pas1,a,b,c,d) + pam1*d + a
    koho_b1 = tk(pbs1,a,b,c,d) + pbm1*d + b
    koho_c1 = tk(pcs1,a,b,c,d) + pcm1*d + c
    koho_a2 = tk(pas2,a,b,c,d) + pam2*d + a
    koho_b2 = tk(pbs2,a,b,c,d) + pbm2*d + b
    koho_c2 = tk(pcs2,a,b,c,d) + pcm2*d + c
    
    ret = min(v*d,koho_a1,koho_a2,koho_b1,koho_b2,koho_c1,koho_c2 ) 
    return ret

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

Submission status: Accepted

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

t = int(input())
  
for _ in range(t):
    n,a,b,c,d = map(int,input().split())
    @lru_cache(None)
    def f(k):
      if k == 1:return d
      if k == 0:return 0
      return min(k*d,f(k//5)+c+k%5*d,f(k//3)+b+k%3*d,f(k//2)+a+k%2*d,f((k+4)//5)+c+-k%5*d,f((k+2)//3)+b+-k%3*d,f((k+1)//2)+a+-k%2*d)
    print(f(n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
t=int(input())
for i in range(t):
  n,a,b,c,d=map(int,input().split())
  @lru_cache(maxsize=None)
  def f(n):
    if n==0:
      return 0
    if n==1:
      return d
    else:
      x=n*d
      
      q,r=divmod(n,2)
      if r==0:
        x=min(x,f(q)+a)
      else:
        x=min(x,f(q)+a+d,f(q+1)+a+d)
      
      q,r=divmod(n,3)
      if r==0:
        x=min(x,f(q)+b)
      elif r==1:
        x=min(x,f(q)+b+d,f(q+1)+b+d*2)
      else:
        x=min(x,f(q)+b+d*2,f(q+1)+b+d)
      
      q,r=divmod(n,5)
      if r==0:
        x=min(x,f(q)+c)
      elif r==1:
        x=min(x,f(q)+c+d,f(q+1)+c+d*4)
      elif r==2:
        x=min(x,f(q)+c+d*2,f(q+1)+c+d*3)
      elif r==3:
        x=min(x,f(q)+c+d*3,f(q+1)+c+d*2)
      else:
        x=min(x,f(q)+c+d*4,f(q+1)+c+d)
      
      return x
  
  print(f(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))
        if (x % 3) < (-x % 3):
            ret = min(ret, b + dfs(x // 3) + d * (x % 3))
        else:
            ret = min(ret, b + dfs((x - 1) // 3 + 1) + d * (-x % 3))
        if (x % 5) < (-x % 5):
            ret = min(ret, c + dfs(x // 5) + d * (x % 5))
        else:
            ret = min(ret, c + dfs((x - 1) // 5 + 1) + d * (-x % 5))

        memo[x] = ret
        return ret

    print(dfs(n))

Submission status: Accepted

Solution code:
divs = [2, 3, 5]

t = int(input())

for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    costs = [a, b, c]

    dp = {0: 0}

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

        ret = x * d

        for cost, div in zip(costs, divs):
            lx = x // div * div
            ret = min(ret, dfs(lx // div) + cost + (x - lx) * d)

            if lx == x:
                continue
            lx += div
            if lx // div >= x:
                continue
            ret = min(ret, dfs(lx // div) + cost + (lx - x) * d)

        dp[x] = ret
        return ret

    print(dfs(n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a = 2, 3, 5

def f(n):
  m = memo.get(n)
  if m is None:
    m = d * n
    for p, c in zip(a, b):
      m = min(m, *(f(k) + abs(p * k - n) * d + c for k in (n // p, -(-n // p))))
    memo[n] = m
  return m

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

Submission status: Accepted

Solution code:
a = 2, 3, 5

def f(n):
  m = memo.get(n)
  if m is None:
    m = d * n
    for p, c in zip(a, b):
      m = min(m, *(f(k) + abs(p * k - n) * d + c for k in {n // p, -(-n // p)}))
    memo[n] = m
  return m

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

Submission status: Accepted

Solution code:
a = 2, 3, 5

def f(n):
  m = memo.get(n)
  if m is None:
    m = d * n
    for p, c in zip(a, b):
      k, r = divmod(n, p);
      m = min(m, f(k) + r * d + c, r  and f(k + 1) + (p - r) * d + c or m)
    memo[n] = m
  return m

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

Submission status: Accepted

Solution code:
a = 2, 3, 5

def f(n):
  m = memo.get(n)
  if m is None:
    s = {(0, 0, 0)}.union(*({(n // p, p, c), (-(-n // p), p, c)} for p, c in zip(a, b)))
    m = min(f(x) + abs(x * p - n) * d + c for x, p, c in s)
    memo[n] = m
  return m

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

Submission status: Accepted

Solution code:
a = 2, 3, 5

def f(n):
  m = memo.get(n)
  if m is None:
    m = d * n
    for p, c in zip(a, b):
      k, r = divmod(n, p);
      m = min(m, f(k) + r * d + c)
      if r:
       m = min(m, f(k + 1) + (p - r) * d + c)
    memo[n] = m
  return m

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000100)

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

    used = {}

    def solve(t):
        if t in used:
            return used[t]
        if t <= 1:
            return t * d

        res = d * t
        for x, y in zip([2, 3, 5], [a, b, c]):
            if t % x == 0:
                res = min(res, solve(t // x) + y)
            else:
                res = min(res, solve(t // x) + y + (t - t // x * x) * d)
                res = min(res, solve(t // x + 1) + y + ((t // x + 1) * x - t) * d)

        used[t] = res
        return res

    print(solve(n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from functools import lru_cache
for _ in range(int(input())):
    n,a,b,c,d=map(int,input().split())
    @lru_cache(None)
    def f(k):
        if k==0:return 0
        if k==1:return d
        return min(k*d,f(k//5)+c+k%5*d,f(k//3)+b+k%3*d,f(k//2)+a+k%2*d,f((k+4)//5)+c+-k%5*d,f((k+2)//3)+b+-k%3*d,f((k+1)//2)+a+-k%2*d)
    print(f(n))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(int(1e6))
 
def solve():
    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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from functools import lru_cache


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

    @lru_cache(None)
    def dfs(n):  # n -> 0 になるまでのコスト
        if n == 0:
            return 0
        if n == 1:
            return D

        cost = n * D
        for div, c in zip((2, 3, 5), (A, B, C)):
            q, r = divmod(n, div)

            if r == 0:
                cost = min(cost, dfs(q) + c)
            else:
                cost = min(cost, dfs(q) + c + D * r)
                cost = min(cost, dfs(q+1) + c + D * (div - r))
        return cost

    return dfs(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:
def f(k):
    if k==1:return d
    if k==0:return 0
    if k in m:return m[k]
    s=k*d
    s=min(s,f(k//2)+a+k%2*d,f((k+1)//2)+a+-k%2*d,f(k//3)+b+k%3*d,f((k+2)//3)+b+-k%3*d,f(k//5)+c+k%5*d,f((k+4)//5)+c+-k%5*d)
    m[k]=s
    return s
for _ in range(int(input())):
    m={}
    n,a,b,c,d=map(int,input().split())
    print(f(n))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
t=int(input())
INF=10**19
def dfs(k):
    if k==1:return d
    if k==0:return 0
    if k in dic:return dic[k]
    ans=k*d
    ans=min(ans,dfs(k//2)+a+k%2*d,dfs((k+1)//2)+a+-k%2*d,dfs(k//3)+b+k%3*d,dfs((k+2)//3)+b+-k%3*d,dfs(k//5)+c+k%5*d,dfs((k+4)//5)+c+-k%5*d)
    dic[k]=ans
    return ans
for _ in range(t):
    dic={}
    n,a,b,c,d=map(int,input().split())
    print(dfs(n))

Submission status: Accepted

Solution code:
T = int(input())
##-----------------start coding-----------------
from heapq import *

for ti in range(1, T + 1):
    n, a, b, c, d = tuple(map(int, input().split()))
    pq = []
    heappush(pq, (0, n))  # cost, posi
    visited = set()  # positions
    while True:
        top = heappop(pq)
        cost, posi = top
        cost, posi = cost, posi
        if posi in visited:
            continue
        else:
            visited.add(posi)
        if posi == 0:
            print(cost)
            break
        costnaive = cost + d * posi
        heappush(pq, (costnaive, 0))
        for mode, margin in [(2, a), (3, b), (5, c)]:
            modulo = posi % mode
            costdown = cost + margin + modulo * d
            downto = (posi - modulo) // mode
            costup = cost + margin + (mode - modulo) * d
            upto = (posi + (mode - modulo)) // mode
            heappush(pq, (costdown, downto))
            heappush(pq, (costup, upto))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from functools import lru_cache

import sys
# sys.setrecursionlimit(10)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


# @mt
def slv(N, A, B, C, D):
    @lru_cache(maxsize=None)
    def f(n):
        if n == 1:
            return D
        if n == 0:
            return 0
        ans = n*D

        i = (n // 2) * 2
        ans = min(ans, f(i//2) + A + D*abs(n-i))
        i = -(-n // 2) * 2
        ans = min(ans, f(i//2) + A + D*abs(n-i))

        i = (n // 3) * 3
        ans = min(ans, f(i//3) + B + D*abs(n-i))
        i = -(-n // 3) * 3
        ans = min(ans, f(i//3) + B + D*abs(n-i))

        i = (n // 5) * 5
        ans = min(ans, f(i//5) + C + D*abs(n-i))
        i = -(-n // 5) * 5
        ans = min(ans, f(i//5) + C + D*abs(n-i))
        return ans

    return f(N)


def main():
    T = read_int()
    for _ in range(T):
        N, A, B, C ,D = read_int_n()
        print(slv(N, A, B, C, D))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
T = int(input())

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

    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:
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict

t = int(input())

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

    def calc(x):
        if(x==0):
            return 0
        if(dic[x] != 0):
            return dic[x]

        tmp = x*d
        if(x%2==0):
            tmp = min(tmp, calc(x//2) + a)
        else:
            tmp = min(tmp, calc(x//2) + a + d, calc(x//2 + 1) + a + d)
        if(x%3==0):
            tmp = min(tmp, calc(x//3) + b)
        elif(x%3==1):
            tmp = min(tmp, calc(x//3) + b + d)
        else:
            tmp = min(tmp, calc(1 + x//3) + b + d)
        if(x%5==0):
            tmp = min(tmp, calc(x//5) + c)
        elif(x%5 < 3):
            tmp = min(tmp, calc(x//5) + c + d*(x%5))
        else:
            tmp = min(tmp, calc(1 + x//5) + c + d*(5 - x%5))

        dic[x] = tmp
        return tmp

    print(calc(n))

Submission status: Accepted

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


def main():
    for _ in [0]*int(input()):
        N, A, B, C, D = map(int, input().split())
        S = {}

        def dfs(n):
            if n == 0:
                return 0
            if n == 1:
                return D
            if n in S:
                return S[n]

            cost = n*D
            r = n % 2
            if r == 0:
                cost = min(cost, dfs(n//2)+A)
            else:
                cost = min(cost, dfs(n//2)+A+D)
                cost = min(cost, dfs(n//2+1)+A+D)
            r = n % 3
            if r == 0:
                cost = min(cost, dfs(n//3)+B)
            else:
                cost = min(cost, dfs(n//3)+B+D*r, dfs(n//3+1)+B+D*(3-r))
            r = n % 5
            if r == 0:
                cost = min(cost, dfs(n//5)+C)
            else:
                cost = min(cost, dfs(n//5)+C+D*r, dfs(n//5+1)+C+D*(5-r))

            S[n] = cost
            return cost

        print(dfs(N))


if __name__ == '__main__':
    main()