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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import heapq
from collections import defaultdict
# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


def defLarge():
    return 10 ** 18
def main():
    T = int(input())
    for ti in range(T):
        N,A,B,C,D = map(int,input().split())
        current = defaultdict(defLarge)
        current[N] = 0
        visited = defaultdict(defLarge)
        minValue = 10**18

        def insertIf(dict,value,index):
            if visited[index] > value and dict[index] > value:
                dict[index] = value
        while len(current) != 0:
            next = defaultdict(defLarge)
            for n in current:
                c = current[n]
                if n == 1:
                    minValue = min(minValue,c+D)
                    continue
                elif n < 0:
                    continue
                if n %2 == 0:
                    insertIf(next,min(c+A,c+n//2*D),n//2)
                else:
                    insertIf(next,c+D,n+1)
                    insertIf(next,c+D,n-1)
                if n %3 == 0:
                    insertIf(next,c+min(B,n//3*2*D),n//3)
                else:
                    m = n%3
                    insertIf(next,c+(3-m)*D,(n+3-m))
                    if n-m > 0:
                        insertIf(next,c+m*D,(n-m))
                if n % 5 == 0:
                    insertIf(next, min(c + C,c+n//5*4*D), n // 5)
                else:
                    m = n%5
                    insertIf(next,c+(5-m)*D,(n+5-m))
                    if n-m > 0:
                        insertIf(next,c+m*D,(n-m))
            for key in next:
                if next[key] < visited[key]:
                    visited[key] = next[key]
            current = next
        print(minValue)
        # if N == 1:
        #     print(D)
        # else:
        #     factors = prime_factorize(N)
        #     cost = D
        #     current = 1
        #     for f in factors:
        #         if f == 2:
        #             nowCost = A
        #             nowCost = min(nowCost,current*D)
        #             nowCost = min(nowCost,C + current*D)
        #             cost += nowCost
        #             current*=2
        #         elif f == 3:
        #             nowCost = B
        #             nowCost = min(nowCost,2*current*D)
        #             nowCost = min(nowCost,A + current*D)
        #             cost += nowCost
        #             current *=3
        #         elif f == 5:
        #             nowCost = C
        #             nowCost = min(nowCost,2*A + current*D)
        #             nowCost = min(nowCost,B + 2*current*D)
        #             cost += nowCost
        #             current *= 5
        #         else:
        #             pass
        #     print(factors)
        #     print(cost)


    # Failed to predict input format
    pass

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

def cost_compare(v,w,L,K,Z):
    if w in L:
        return min(K[v]+Z,K[w])
    elif w in K:
        return K[w]
    else:
        return K[v]+Z

T=int(input())


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

    K={0:0} #最小のコストの辞書
    L={0:0} #Kのうち未確定のものへの制限

    g=0
    while g<=10:
        v=min(L)

        del L[v]
        
        m=cost_compare(v,2*v,L,K,A)
        if (2*v in L) or (2*v not in K):
            L[2*v]=m
        K[2*v]=m

        m=cost_compare(v,3*v,L,K,B)
        if (3*v in L) or (3*v not in K):
            L[3*v]=m
        K[3*v]=m

        m=cost_compare(v,5*v,L,K,C)
        if (5*v in L) or (5*v not in K):
            L[5*v]=m
        K[5*v]=m

        m=cost_compare(v,v+1,L,K,D)
        if (v+1 in L) or (v+1 not in K):
            L[v+1]=m
        K[v+1]=m

        if v>=1:
            m=cost_compare(v,v-1,L,K,D)
            if (v-1 in L) or (v-1 not in K):
                L[v-1]=m
            K[v-1]=m

        if v==N:g=1
        if g!=0:
            g+=1
        
    print(K[N])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
    
def tempmin(start, waru2, hiku1, temp):
    count = 0
    while(start != 0):
        if start % 2 == 0:
            start = start // 2
            count += waru2
        else:
            start -= 1
            count += hiku1
    return min(count, temp)
n = (int)(input())
a=[list(map(int, input().split(" "))) for i in range(n)]

for i in range(n):
    queue = deque([[a[i][0], 0]])
    tmini = a[i][0] * a[i][4]
    mini = tempmin(a[i][0], a[i][1], a[i][4], tmini)
    while(len(queue) > 0):
        node = queue.popleft()
        if node[1] > mini:
            continue
        if node[0] == 0:
            if node[1] < mini:
                mini = node[1]
            continue

        if node[0] % 5 == 0 and node[1] + a[i][3]< mini:
            queue.append([node[0] // 5, node[1] + a[i][3]])
        if node[0] % 3 == 0 and node[1] + a[i][2]< mini:
            queue.append([node[0] // 3, node[1] + a[i][2]])
        if node[0] % 2 == 0 and node[1] + a[i][1]< mini:
            queue.append([node[0] // 2, node[1] + a[i][1]])
        if node[1] + a[i][4] < mini:
            queue.append([node[0] + 1, node[1] + a[i][4]])
            queue.append([node[0] - 1, node[1] + a[i][4]])
    print(mini)

Submission status: Time Limit Exceeded

Solution code:
t = int(input())
  
def solve(n,a,b,c,d):
  sol = [n*d]
  if n>=2:
    if n%2 == 0:
      sol.append(a+solve(n//2,a,b,c,d))
    else:
      sol.append(a+d+solve((n+1)//2,a,b,c,d))
      sol.append(a+d+solve((n-1)//2,a,b,c,d))
  if n>=3:
    if n%3 == 0:
      sol.append(b+solve(n//3,a,b,c,d))
    else:
      bd = n%3
      sol.append(b+bd*d+solve((n-bd)//3,a,b,c,d))
      sol.append(b+(3-bd)*d+solve((n-bd+3)//3,a,b,c,d))
  if n>=5:
    if n%5 == 0:
      sol.append(c+solve(n//5,a,b,c,d))
    else:
      cd = n%5
      sol.append(c+cd*d+solve((n-cd)//5,a,b,c,d))
      sol.append(c+(5-cd)*d+solve((n-cd+5)//5,a,b,c,d))
  return min(sol)

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

Submission status: Time Limit Exceeded

Solution code:
T = int(input())
N_list = []
A_list = []
B_list = []
C_list = []
D_list = []

for i in range(T):
    N, A, B, C, D = map(int, input().split())
    N_list.append(N)
    A_list.append(A)
    B_list.append(B)
    C_list.append(C)
    D_list.append(D)

for N, A, B, C, D in zip(N_list, A_list, B_list, C_list, D_list):
    count = 0
    coin = 0
    count_temp = 0
    coin_temp = 0
    answers = []
    answers.append(D * N)
    
    #Aの場合
    while N != count:
        if coin == 0:
            count = count + 1
            coin += D
        if count * 2 < N:
            count = count * 2
            coin += A
        else:
            if coin_temp == 0:
                count_temp = count
                coin_temp = coin
            count = count + 1
            coin += D
        #print("A+", coin, count)
    answers.append(coin)
    count = count_temp
    coin = coin_temp
    count_temp = 0
    coin_temp = 0

    while N != count:
        if count < N:
            count = count * 2
            coin += A
        if N < count:
            count = count - 1
            coin += D
        #print("A-", coin, count)
    answers.append(coin)
    coin = 0
    count = 0
        
    #Bの場合
    while N != count:
        if coin == 0:
            count = count + 1
            coin += D
        if count * 3 < N:
            count = count * 3
            coin += B
        else:
            if coin_temp == 0:
                count_temp = count
                coin_temp = coin
            count = count + 1
            coin += D
        #print("A+", coin, count)
    answers.append(coin)
    count = count_temp
    coin = coin_temp
    count_temp = 0
    coin_temp = 0

    while N != count:
        if count < N:
            count = count * 3
            coin += B
        if N < count:
            count = count - 1
            coin += D
        #print("A-", coin, count)
    answers.append(coin)
    coin = 0
    count = 0
        
    #Cの場合
    while N != count:
        if coin == 0:
            count = count + 1
            coin += D
        if count * 5 < N:
            count = count * 5
            coin += C
        else:
            if coin_temp == 0:
                count_temp = count
                coin_temp = coin
            count = count + 1
            coin += D
        #print("A+", coin, count)
    answers.append(coin)
    count = count_temp
    coin = coin_temp
    count_temp = 0
    coin_temp = 0

    while N != count:
        if count < N:
            count = count * 5
            coin += C
        if N < count:
            count = count - 1
            coin += D
        #print("A-", coin, count)
    answers.append(coin)
    coin = 0
    count = 0
        

    print(min(answers))

Submission status: Time Limit Exceeded

Solution code:
import heapq



def pay(N,A,B,C,D):
  q = []
  heapq.heapify(q)
  num = {}
  num[0] = 0
  num[-1] = -1
  heapq.heappush(q,( 0, 0 ))
  while q:
    c, n = heapq.heappop(q)
#    print(n,c)
    if n == N:
      break
    if num.setdefault(n*2,N*D+1) > c+A:
      heapq.heappush(q,( c+A, n*2 ))
      num[n*2] = c+A
    if num.setdefault(n*3,N*D+1) > c+B:
      heapq.heappush(q,( c+B, n*3 ))
      num[n*3] = c+B
    if num.setdefault(n*5,N*D+1) > c+C:
      heapq.heappush(q,( c+C, n*5 ))
      num[n*5] = c+C
    if num.setdefault(n+1,N*D+1) > c+D:
      heapq.heappush(q,( c+D, n+1 ))
      num[n+1] = c+D
    if num.setdefault(n-1,N*D+1) > c+D:
      heapq.heappush(q,( c+D, n-1 ))
      num[n-1] = c+D
  #
  print(num.setdefault(N,-1))
#

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

Submission status: Time Limit Exceeded

Solution code:
t = int(input())

for i in range(t):
    N,a,b,c,d = map(int, input().split())
    ans = d #コイン枚数
    n_like = round(N,-1)
    print(n_like)
    n = 1
    ans = d
    while (n_like != n):
        if n_like >= n*5:
            n *= 5
            ans += c
        elif n_like >= n*3:
            n *= 3
            ans += b
        else:
            n *= 2
            ans += a
    while (N != n):
        if n < N:
            n += 1
            ans += d
        else:
            n -= 1
            ans += d
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
T = int(input())
N_list = []
A_list = []
B_list = []
C_list = []
D_list = []

for i in range(T):
    N, A, B, C, D = map(int, input().split())
    N_list.append(N)
    A_list.append(A)
    B_list.append(B)
    C_list.append(C)
    D_list.append(D)

for N, A, B, C, D in zip(N_list, A_list, B_list, C_list, D_list):
    count = 0
    coin = 0
    answers = []
    answers.append(D * N)
    
    #Aの場合
    while N != count:
        if coin == 0:
            count = count + 1
            coin += D
        if count < N:
            count = count * 2
            coin += A
        if N < count:
            count = count - 1
            coin += D
        #print("A-", coin, count)
    answers.append(coin)
    coin = 0
    count = 0
    
    while N != count:
        if coin == 0:
            count = count + 1
            coin += D
        if count * 2 < N:
            count = count * 2
            coin += A
        else:
            count = count + 1
            coin += D
        #print("A+", coin, count)
    answers.append(coin)
    coin = 0
    count = 0
    
    #Bの場合
    while N != count:
        if coin == 0:
            count = count + 1
            coin += D
        if count < N:
            count = count * 3
            coin += B
        if N < count:
            count = count - 1
            coin += D
        #print("B-", coin, count)
    answers.append(coin)
    coin = 0
    count = 0
    
    while N != count:
        if coin == 0:
            count = count + 1
            coin += D
        if count * 3 < N:
            count = count * 3
            coin += B
        else:
            count = count + 1
            coin += D
        #print("B+", coin, count)
    answers.append(coin)
    coin = 0
    count = 0
    
    #Cの場合
    while N != count:
        if coin == 0:
            count = count + 1
            coin += D
        if count < N:
            count = count * 5
            coin += C
        if N < count:
            count = count - 1
            coin += D
        #print("C-", coin, count)
    answers.append(coin)
    coin = 0
    count = 0
    
    while N != count:
        if coin == 0:
            count = count + 1
            coin += D
        if count * 5 < N:
            count = count * 5
            coin += C
        else:
            count = count + 1
            coin += D
        #print("C+", coin, count)
    answers.append(coin)
    coin = 0
    count = 0    
    
    print(min(answers))

Submission status: Time Limit Exceeded

Solution code:
def even(s):
    c1 = five(n)
    c2 = three(n)
    c3 = two(n)
    return c1*c+c2*b+c3*a+d


def odd(u):
    x = n-1
    c1 = five(x)
    c2 = three(x)
    c3 = two(x)
    return c1*c+c2*b+c3*a+2*d


def five(t):

    count1 = 0
    while(n % 5 != 0):
        count1 += 1
    return count1


def two(v):
    count2 = 0
    while(n % 2 != 0):
        count2 += 1
    return count2


def three(w):
    count3 = 0
    while(n % 3 != 0):
        count3 += 1
    return count3


t = int(input())
for i in range(t-1):
    n, a, b, c, d = map(int, input().split())
if n % 2 == 0:
    even(n)
else:
    odd(n)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
import heapq
import cProfile
from collections import Counter, defaultdict, deque
from functools import reduce
import math

def get_int():
    return int(stdin.readline().strip())


def get_tuple():
    return map(int, stdin.readline().split())


def get_list():
    return list(map(int, stdin.readline().split()))


def solve():
    n,a,b,c,d = map(int,input().strip().split())
    dp = [0,d]
    i = 2
    while i<=n+1:
        ans = dp[-1]+d
        if i%2==0:
            ans = min(ans,dp[i//2]+a)
        if i%3==0:
            ans = min(ans, dp[i // 3 ] + b)
        if i%5==0:
            ans = min(ans, dp[i // 5] + c)
        dp[-1] = min(ans+d,dp[-1])
        dp.append(ans)
        i += 1
    print(dp[-2])

def main():
    solve()


TestCases = True

if TestCases:
    for i in range(get_int()):
        main()
else:
    main()

Submission status: Time Limit Exceeded

Solution code:
T = int(input())
N_list = []
A_list = []
B_list = []
C_list = []
D_list = []

for i in range(T):
    N, A, B, C, D = map(int, input().split())
    N_list.append(N)
    A_list.append(A)
    B_list.append(B)
    C_list.append(C)
    D_list.append(D)

for N, A, B, C, D in zip(N_list, A_list, B_list, C_list, D_list):
    count = 0
    coin = 0
    while N != count:
        if (A > B and A > C and A > D and count > 0 and N > count) or (coin > 0 and N > count):
            count = count * 2
            coin += A
        if (B > A and B > C and B > D and count > 0 and N > count) or (coin > 0 and N > count):
            count = count * 3
            coin += B
        if (C > A and C > B and C > D and count > 0 and N > count) or (coin > 0 and N > count):
            count = count * 5
            coin += C
        if (D > A and D > B and D > C and N > count) or coin == 0:
            count = count + 1
            coin += D
        if D > A and D > B and D > C and count > N:
            count = count - 1
            coin += D
    if coin > D * N:
        print(D * N)
    else:
        print(coin)

Submission status: Time Limit Exceeded

Solution code:
T = int(input())

for i in range(T):
  x = 0
  coin = 0
  N,A,B,C,D = map(int, input().split())
  for j in range(100000000000):
    if x == N:
      print(coin)
      break
    elif N // 2 >= 1 and N % 2 == 0:
      N = N / 2
      coin = coin + A
    elif N // 3 >= 1 and N % 3 == 0:
      N = N / 3
      coin = coin + B
    elif N // 5 >= 1 and N % 5 == 0:
      N = N / 5
      coin = coin + C
    elif (N - 1) // 2 >= 1 and (N - 1) % 2 == 0:
      N = (N - 1) / 2
      coin = coin + A + D
    elif (N - 1) // 3 >= 1 and (N - 1) % 3 == 0:
      N = (N - 1) / 3
      coin = coin + B + D
    elif (N - 1) // 5 >= 1 and (N - 1) % 5 == 0:
      N = (N - 1) / 5
      coin = coin + C + D
    elif (N + 1) // 2 >= 1 and (N + 1) % 2 == 0:
      N = (N + 1) / 2
      coin = coin + A + D
    elif (N + 1) // 3 >= 1 and (N + 1) % 3 == 0:
      N = (N + 1) / 3
      coin = coin + B + D
    elif (N + 1) // 5 >= 1 and (N + 1) % 5 == 0:
      N = (N + 1) / 5
      coin = coin + C + D
    else:
      N = N - 1

Submission status: Time Limit Exceeded

Solution code:
for i in range(10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000):
  1+1

Submission status: Time Limit Exceeded

Solution code:
t=int(input())
l=[list(map(int,input().split())) for i in range(t)]
for i in range(t):
  ans=[]
  for j1 in range(70):
    for j2 in range(70):
      for j3 in range(70):
        x=(2**j1)*(3**j2)*(5**j3)
        ans.append(l[i][1]*j1+l[i][2]*j2+l[i][3]*j3+l[i][4]+l[i][4]*(abs(x-l[i][0])))
  print(min(ans))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

T = int(input())

for i in range(T):
    N, A, B, C, D = map(int, input().split())
    h = [(0, N)]
    used = set()
    while h:
        cost, v = heappop(h)

        if v in used:
            continue

        if v == 1:
            print(cost + D)
            break

        used.add(v)

        d, m = divmod(v, 5)
        if d > 0:
            heappush(h, (cost + m * D + C, d))
        if m > 0:
            heappush(h, (cost + (5-m) * D + C, d+1))

        d, m = divmod(v, 3)
        if d > 0:
            heappush(h, (cost + m * D + B, d))
        if m > 0:
            heappush(h, (cost + (3-m) * D + B, d+1))

        d, m = divmod(v, 2)
        if d > 0:
            heappush(h, (cost + m * D + A, d))
        if m > 0:
            heappush(h, (cost + (2-m) * D + A, d+1))

        heappush(h, (cost + (v-1) * D, 1))

Submission status: Accepted

Solution code:
t = int(input())
for _ 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]
        res = min(
            d*n,
            d*((n+1)//2*2-n)+a+dfs((n+1)//2),
            d*(n-n//2*2)+a+dfs(n//2),
            d*((n+2)//3*3-n)+b+dfs((n+2)//3),
            d*(n-n//3*3)+b+dfs(n//3),
            d*((n+4)//5*5-n)+c+dfs((n+4)//5),
            d*(n-n//5*5)+c+dfs(n//5),
        )
        memo[n] = res
        return res

    print(dfs(n))

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
from bisect import bisect_left as lb, bisect_right as ub
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from math import gcd, ceil, sqrt
rd = lambda: int(sys.stdin.readline())
rds = lambda: map(int, sys.stdin.readline().split())
rdl = lambda: list(map(int, sys.stdin.readline().split()))
inf = 2 * 10 ** 18
sys.setrecursionlimit(10 ** 7)
rg = range
pr = print


T = rd()
for i in rg(T):
  n, a, b, c, d = rds()

  @lru_cache(maxsize=10 ** 7)
  def f(m):
    # print(m)
    if m == 1:
      return d
    ret = d * m
    # 2
    q, r = m // 2, m % 2
    if q:
      ret = min(ret, f(q) + d * r + a)
    if r:
      ret = min(ret, f(q + 1) + d * (2 - r) + a)

    q, r = m // 3, m % 3
    if q:
      ret = min(ret, f(q) + d * r + b)
    if r:
      ret = min(ret, f(q + 1) + d * (3 - r) + b)

    q, r = m // 5, m % 5
    if q:
      ret = min(ret, f(q) + d * r + c)
    if r:
      ret = min(ret, f(q + 1) + d * (5 - r) + c)
    return ret

  pr(f(n))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)

T=int(input())



def saiki(n):

    if n in memo:
        return memo[n]
        
    if n==0:
        return 0
    elif n==1:
        return D
    else:
        value=min(
            D*n,
            saiki(n//2)    +A+ D *abs(n - n//2*2),
            saiki((n+1)//2)+A+ D *abs(n - (n+1)//2*2),
            saiki(n//3)    +B+ D *abs(n - n//3*3),
            saiki((n+2)//3)+B+ D *abs(n - (n+2)//3*3),
            saiki(n//5)    +C+ D *abs(n - n//5*5),
            saiki((n+4)//5)+C+ D *abs(n - (n+4)//5*5)
            )
        
    memo[n]=value
    return value

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
def f():
  n, a, b, c, d = map(int, input().split())
  dp = dict()
  def dfs(n):
    if n == 0:
      return 0
    if n == 1:
      return d
    if n in dp:
      return dp[n]
    res = n*d
    for s, k in ((a, 2), (b, 3), (c, 5)):
      q, r = divmod(n, k)
      res = min(res, dfs(q)+d*r+s)
      if r:
        res = min(res, dfs(q+1)+d*(k-r)+s)
    dp[n] = res
    return res
  ans = dfs(n)
  print(ans)
t = int(input())
for _ in range(t):
  f()

Submission status: Accepted

Solution code:


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
t = int(input())
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
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007

#+++++

def ggg(n,a,b,c,d):
	init = n
	open = queue.PriorityQueue()
	close = set()
	open.put((0, n))
	min_v = n*d
	while not open.empty():
		cost, pos = open.get()
		if pos in close:
			continue
		if cost > min_v:
			continue
		
		min_v = min(min_v, cost+pos*d)
		for c, add in zip([a,b,c],[2,3,5]):
			k = pos % add
			nc = cost + k*d + c
			np = pos // add
			if nc <= min_v and np not in close:
				open.put((nc, np))
				#pa((nc,np))
			nnc = cost + (add-k) *d + c
			nnp = (pos + add) // add
			if nnc <= min_v and nnp not in close:
				open.put((nnc, nnp))
				#pa((nnc,nnp))
		close.add(pos)
	return min_v
		
		



def main():
	t = int(input())
	for i in range(t):
		n, a, b , c, d = tin()
		r = ggg(n,a,b,c,d)
		print(r)
	#s = input()
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from functools import lru_cache
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def f(N, E, memo):
    if N == 0:
        return 0
    
    if N == 1:
        return E[-1]

    if N in memo:
        return memo[N]

    res = N * E[-1]
    for k in (2, 3, 5):
        l = (N // k) * k
        r = ((N - 1) // k + 1) * k

        res = min(res, (N - l) * E[-1] + E[k] + f(l // k, E, memo))
        res = min(res, (r - N) * E[-1] + E[k] + f(r // k, E, memo))
    memo[N] = res
    return res
   

def main():
    T = int(input())
    for _ in range(T):
        N, A, B, C, D = read_values()
        E = (0, 0, A, B, 0, C, D)
        memo = dict()
        print(f(N, E, memo))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#A:Pay to Win
import sys
sys.setrecursionlimit(10 ** 9)

t = int(input())
a,b,c,d = 0,0,0,0
p = {}
INF = float('inf')

def calc(x):
  global a,b,c,d,p
  #print(x)
  if x in p:
    return p[x]
  if x == 1:
    res = d
  else:
    res = INF
    if x%2 == 0:
      res = min(min(a,d*(x-x//2))+calc(x//2),res)
    else:
      res = min(min(a+d*(2-x%2),d*(x-(x+2-x%2)//2))+calc((x+2-x%2)//2),res)
      if x-x%2 > 0:
        res = min(min(a+d*(x%2),d*(x-(x-x%2)//2))+calc((x-x%2)//2),res)
    if x%3 == 0:
      res = min(min(b,d*(x-x//3))+calc(x//3),res)
    else:
      res = min(min(b+d*(3-x%3),d*(x-(x+3-x%3)//3))+calc((x+3-x%3)//3),res)
      if x-x%3 > 0:
        res = min(min(b+d*(x%3),d*(x-(x-x%3)//3))+calc((x-x%3)//3),res)
    if x%5 == 0:
      res = min(min(c,d*(x-x//5))+calc(x//5),res)
    else:
      res = min(min(c+d*(5-x%5),d*(x-(x+5-x%5)//5))+calc((x+5-x%5)//5),res)
      if x-x%5 > 0:
        res = min(min(c+d*(x%5),d*(x-(x-x%5)//5))+calc((x-x%5)//5),res)
  if x in p:
    p[x] = min(p[x],res)
  else:
    p[x] = res
  return res

def solve():
  global a,b,c,d,p
  n,a,b,c,d = map(int,input().split())
  p = {}
  #print(calc(n))
  #print(min(calc(n),calc(n+2-n%2)+d*(2-n%2),calc(n+3-n%3)+d*(3-n%3),calc(n+5-n%5)+d*(5-n%5),n*d))
  print(min(calc(n),n*d))

for i in range(t):
  solve()

Submission status: Accepted

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect

sys.setrecursionlimit(10**6)
t=int(input())
def cost(n):
    if n in dist:
        return dist[n]
    ret = min(
        D * n,
        D * abs(n - n//5*5) + C + cost(n//5),
        D * abs(n - (n+4)//5*5) + C + cost((n+4)//5),
        D * abs(n - n//3*3) + B + cost(n//3),
        D * abs(n - (n+2)//3*3) + B + cost((n+2)//3),
        D * abs(n - n//2*2) + A + cost(n//2),
        D * abs(n - (n+1)//2*2) + A + cost((n+1)//2)
    )

    dist[n]=ret
    return ret
for i in range(t):
    ans=0
    n,A,B,C,D=map(int,input().split())
    dist={0:0,1:D}
    print(cost(n))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def main():
    n, a, b, c, d = map(int, input().split())
    memo = {}
    def dfs(x):
        if x == 0:
            return 0
        elif x == 1:
            return d
        elif x in memo:
            return memo[x]
        else:
            ret = min(
                d * x,
                d * (x - x//2*2) + a + dfs(x//2),
                d * ((x+1)//2*2 - x) + a + dfs((x+1)//2),
                d * (x - x//3*3) + b + dfs(x//3),
                d * ((x+2)//3*3 - x) + b + dfs((x+2)//3),
                d * (x - x//5*5) + c + dfs(x//5),
                d * ((x+4)//5*5 - x) + c + dfs((x+4)//5)
            )
            memo[x] = ret
            return ret
    print(dfs(n))

t = int(input())
for i in range(t):
    main()

Submission status: Accepted

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

dic = dict()

def search(n, a, b, c, d):
    # print(n, dic)
    if n == 0:
        return 0
    if n == 1:
        return d
    if n in dic:
        return dic[n]

    ret = n * d

    tgt = n // 2
    ret = min(ret, search(tgt, a, b, c, d) + a + d * abs(tgt * 2 - n))
    tgt = (n + 1) // 2
    ret = min(ret, search(tgt, a, b, c, d) + a + d * abs(tgt * 2 - n))

    tgt = n // 3
    ret = min(ret, search(tgt, a, b, c, d) + b + d * abs(tgt * 3 - n))
    tgt = (n + 2) // 3
    ret = min(ret, search(tgt, a, b, c, d) + b + d * abs(tgt * 3- n))

    tgt = n // 5
    ret = min(ret, search(tgt, a, b, c, d) + c + d * abs(tgt * 5 - n))
    tgt = (n + 4) // 5
    ret = min(ret, search(tgt, a, b, c, d) + c + d * abs(tgt * 5 - n))

    dic[n] = ret
    return ret

def solve():
    N, A, B, C, D = getList()
    dic.clear()
    print(search(N, A, B, C, D))

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    main()
    # solve()