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:
from math import log
T=int(input())
for i in range(T):
  N,A,B,C,D=map(int,input().split())
  ans=10**18
  for a in range(61):
    for b in range(39):
      for c in range(27):
        for d in range(-10,10):
          n=2**a*3**b*5**c+d
          cost=A*a+B*b+C*c+D*(1+abs(d))
          if N==n:
            ans=min(ans,cost)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi, log
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    now = {2: min(a+d, d+d), 3: b+d, 5: c+d}
    mae = {2: min(a+d, d+d), 3: b+d, 5: c+d, 1: d}
    sep = min(d*n, floor(log(n, 2))*a+(n + 1 - 2**floor(log(n, 2)))*d, floor(log(n, 3))*b+(n + 1 - 3**floor(log(n, 3)))*d, floor(log(n, 5))*c+(n + 1 - 5**floor(log(n, 5)))*d)
    while True:
        if len(now) == 0: break
        dic = {}
        for k, v in now.items():
            if k == 0: continue
            if v >= sep: continue
            if k > n:
                sep = min(sep, v+d*abs(k - n))
                continue
            # a
            tugi = k * 2
            cost = v + a
            if tugi == n:
                sep = min(sep, cost)
            elif tugi in mae:
                if mae[tugi] > cost:
                    dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                    mae[tugi] = dic[tugi]
            else:
                dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                mae[tugi] = dic[tugi]
            # b
            tugi = k * 3
            cost = v + b
            if tugi == n:
                sep = min(sep, cost)
            elif tugi in mae:
                if mae[tugi] > cost:
                    dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                    mae[tugi] = dic[tugi]
            else:
                dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                mae[tugi] = dic[tugi]
            # c
            tugi = k * 5
            cost = v + c
            if tugi == n:
                sep = min(sep, cost)
            elif tugi in mae:
                if mae[tugi] > cost:
                    dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                    mae[tugi] = dic[tugi]
            else:
                dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                mae[tugi] = dic[tugi]
            # d
            tugi = k + 1
            cost = v + d
            if tugi == n:
                sep = min(sep, cost)
            elif tugi in mae:
                if mae[tugi] > cost:
                    dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                    mae[tugi] = dic[tugi]
            else:
                dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                mae[tugi] = dic[tugi]
            # e
            tugi = k - 1
            cost = v + d
            if tugi == n:
                sep = min(sep, cost)
            elif tugi in mae:
                if mae[tugi] > cost:
                    dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                    mae[tugi] = dic[tugi]
            else:
                dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                mae[tugi] = dic[tugi]
        now = deepcopy(dic)
    print(sep)

Submission status: Time Limit Exceeded

Solution code:
'''
T = 5
N = 11
A = 1#*2
B = 2#*3
C = 4#*5
D = 8#+1
'''


T = int(input())
#T = 1
for _ in range(T):
	N, A, B, C, D = map(int, input().split())
	#[A, B, C, D]
	memo = [0, D]#{1: D}
	for i in range(2, N+2):
		cost = memo[i-1] + D
		if i%2==0:
			cost = min([cost, memo[i//2] + A])
		if i%3==0:
			cost = min([cost, memo[i//3] + B])
		if i%5==0:
			cost = min([cost, memo[i//5] + C])
		#memo[i] = cost
		memo.append(cost)
		memo[i-1] = min([memo[i-1], cost + D])
		#print(str(i)+' >>> '+str(cost))
	print(memo[N])
print()

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
                visited[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
                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, c + min(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))
            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:
T = input()
T = int(T)

TEST_CASE = []
for t in range(T):
    line = input()
    line = line.split()
    intline = []
    for l in line:
        l = int(l)
        intline.append(l)
    TEST_CASE.append(intline)

def ope1(a, coin, mynum):
    return coin-a, mynum*2

def ope2(b, coin, mynum):
    return coin-b, mynum*3

def ope3(c, coin, mynum):
    return coin-c, mynum*5

def ope4(d, coin, mynum):
    return coin-d, mynum+1

def ope5(d, coin, mynum):
    return coin-d, mynum-1

def solve(problem):
    N, A, B, C, D = problem[0], problem[1], problem[2], problem[3], problem[4]
    dp = [[0 for n in range(2*N+1)] for r in range(max(A,B,C,D))]
    dp[-1][0] = 1
    nowcoin = 0

    while dp[-1][N] == 0:
        nowcoin += 1
        newline = list(dp[-1])
        for n in range(2*N+1):
            if newline[n] == 0:
                if n%2 == 0:
                    if dp[-A][int(n/2)] == 1:
                        newline[n] = 1
                if n%3 == 0:
                    if dp[-B][int(n/3)] == 1:
                        newline[n] = 1
                if n%5 == 0:
                    if dp[-C][int(n/5)] == 1:
                        newline[n] = 1
                if nowcoin >= D:
                    if n+1 <= 2*N:
                        if dp[-D][int(n+1)] == 1:
                            newline[n] = 1
                    if n-1 >= 0:
                        if dp[-D][int(n-1)] == 1:
                            newline[n] = 1
        dp.pop(0)
        dp.append(newline)
    return nowcoin

for test in TEST_CASE:
    print(solve(test))

Submission status: Time Limit Exceeded

Solution code:
costs = {}
searching = {}

def init(a, b, c, d):
    my_costs = {}
    my_costs[0] = 0
    frontier = set([0])
    for depth in range(8):
        new_frontier = set()
        for f in frontier:
            for ff, cst in [(f*2, a), (f*3, b), (f*5, c), (f-1, d), (f+1, d)]:
                if ff < 0:
                    continue
                if ff not in my_costs:
                    my_costs[ff] = my_costs[f] + cst
                else:
                    my_costs[ff] = min(my_costs[f] + cst, my_costs[ff])
                new_frontier.add(ff)
        frontier = new_frontier
    for k in range(20):
        costs[k] = my_costs[k]

def solve(n, a, b, c, d):
    if n in costs:
        return costs[n]

    next_step = {}
    for delta in range(-5, 5+1):
        m = n + delta
        for div, div_cost in [(2, a), (3, b), (5, c)]:
            if m % div == 0:
                cst = d * abs(delta) + div_cost
                r = m // div
                if r not in next_step:
                    next_step[r] = cst
                else:
                    next_step[r] = min(next_step[r], cst)

    #print(f'next step for {n} is {list(next_step.keys())}')
    costs_lst = []
    for r in next_step:
        cst = solve(r, a, b, c, d) + next_step[r]
        costs_lst.append(cst)
    costs[n] = min(costs_lst + [n*d])
    return costs[n]

t = int(input())

for casenum in range(1, t+1):
    n, a, b, c, d = map(int, input().split())
    costs = {}
    searching = {}

    init(a, b, c, d)
    answer = solve(n, a, b, c, d)
    #print(f'answer for {n, a, b, c, d} = {answer}')
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
min_coin = 0
def min_way(N, c, n, A, B, C, D):
    global min_coin
    if c > min_coin:
        return N*D
    if n < 0:
        return D*N
    if n == 0:
        if c < min_coin:
            min_coin = c
        return c
    AA = min_way(N, c+A+((n%2)*D), int(n/2), A, B, C, D)
    BB = min_way(N, c+B+((n%3)*D), int(n/3), A, B, C, D)
    CC = min_way(N, c+C+((n%5)*D), int(n/5), A, B, C, D)
    DD = min_way(N, c+D, n-1, A, B, C, D)
    DDD = min_way(N, c+D, n+1, A, B, C, D)
    return min(AA, BB, CC, DD, DDD)
T = int(input())
for _ in range(T):
    N, A, B, C, D = np.array(list(map(int, input().split())))
    min_coin = N*D
    print(min_way(N, 0, N, A, B, C, D))

Submission status: Time Limit Exceeded

Solution code:
'''
T = 5
N = 11
A = 1#*2
B = 2#*3
C = 4#*5
D = 8#+1
'''


T = int(input())
#T = 1
for _ in range(T):
	N, A, B, C, D = map(int, input().split())
	#[A, B, C, D]
	memo = [0, D]#{1: D}
	for i in range(2, N+2):
		cost = memo[i-1] + D
		if i%2==0:
			cost = min(cost, memo[int(i/2)] + A)
		if i%3==0:
			cost = min(cost, memo[int(i/3)] + B)
		if i%5==0:
			cost = min(cost, memo[int(i/5)] + C)
		#memo[i] = cost
		memo.append(cost)
		memo[i-1] = min(memo[i-1], cost + D)
		#print(str(i)+' >>> '+str(cost))
	print(memo[N])
print()

Submission status: Time Limit Exceeded

Solution code:


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

    # 各テストケースの計算
    for t in range(n_test):
        # 入力
        N, A, B, C, D = map(int, input().split())

        # 動的計画法
        is_update = True
        inf = 1e8
        global dp
        dp = [inf for i in range(N*2 + 1)]
        dp[0] = 0
        dp[1] = D
        while is_update:
            is_update_ = False
            for i in range(2, N*2):
                # 変更前
                dp_i = dp[i]

                # 2 * 3 * 5の倍数の場合
                if i % 30 == 0:
                    dp[i] = min(dp[i // 2] + A, dp[i // 3] + B, dp[i // 5] + C, dp[i + 1] + D, dp[i - 1] + D)
                # 3 * 5の倍数の場合
                elif i % 15 == 0:
                    dp[i] = min(dp[i // 3] + B, dp[i // 5] + C, dp[i + 1] + D, dp[i - 1] + D)
                # 2 * 5の倍数の場合
                elif i % 10 == 0:
                    dp[i] = min(dp[i // 2] + A, dp[i // 5] + C, dp[i + 1] + D, dp[i - 1] + D)
                # 2 * 3の倍数の場合
                elif i % 6 == 0:
                    dp[i] = min(dp[i // 2] + A, dp[i // 3] + B, dp[i + 1] + D, dp[i - 1] + D)
                # 5の倍数の場合
                elif i % 5 == 0:
                    dp[i] = min(dp[i // 5] + C, dp[i + 1] + D, dp[i - 1] + D)
                # 3の倍数の場合
                elif i % 3 == 0:
                    dp[i] = min(dp[i // 3] + B, dp[i + 1] + D, dp[i - 1] + D)
                # 2の倍数の場合
                elif i % 2 == 0:
                    dp[i] = min(dp[i // 2] + A, dp[i + 1] + D, dp[i - 1] + D)
                # 2, 3, 5の倍数でないとき
                else:
                    dp[i] = min(dp[i + 1] + D, dp[i - 1] + D)

                # 変更の有無のチェック
                if dp[i] != dp_i:
                    is_update_ = True

            if not is_update_:
                is_update = False

        print(dp[N])


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.items(),key=lambda x:x[1])[0]

        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:
def get(target,cost_one,cost_two,cost_three,cost_five):
  dp = [float("inf") for _ in range(target+10)]
  if target ==1:
    return cost_one
  if target == 0:
    return 0
  dp[1] = cost_one
  dp[2] = min(dp[1]*2,dp[1] + cost_two,dp[1] + cost_three + cost_one,dp[1] + cost_five + 3*cost_one)
  for i in range(3,target + 5):
    minima = float("inf")
    minima = min(minima, dp[1]*i)
    if i%2 == 0:
      minima = min(minima,dp[i//2] + cost_two)
    if i%3 == 0:
      minima = min(minima,dp[i//3] + cost_three)
    if i%5 == 0:
      minima = min(minima,dp[i//5] + cost_five)
    dp[i] = min(minima,dp[i-1] + cost_one)
  for j in range(target+1,target+5):
    dp[target] = min(dp[target],dp[j] + (j-target)*cost_one)
  return dp[target]
for _ in range(int(input())):
  target,cost_two,cost_three,cost_five,cost_one  =list(map(int,input().split()))
  print(get(target,cost_one,cost_two,cost_three,cost_five))

Submission status: Time Limit Exceeded

Solution code:
'''
T = 5
N = 11
A = 1#*2
B = 2#*3
C = 4#*5
D = 8#+1
'''


T = int(input())
#T = 1
for _ in range(T):
	N, A, B, C, D = map(int, input().split())
	#[A, B, C, D]
	memo = [None for _ in range(N+2)]#[0, D]#{1: D}
	memo[0] = 0
	memo[1] = D
	for i in range(2, N+2):
		cost = memo[i-1] + D
		if not i%2:
			cost = min(cost, memo[int(i/2)] + A)
		if not i%3:
			cost = min(cost, memo[int(i/3)] + B)
		if not i%5:
			cost = min(cost, memo[int(i/5)] + C)
		memo[i] = cost
		#memo.append(cost)
		memo[i-1] = min(memo[i-1], cost + D)
		#print(str(i)+' >>> '+str(cost))
	print(memo[N])

Submission status: Time Limit Exceeded

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


def solve():
  N, A, B, C, D = map(int, input().split())
  min_cost = 1e+18
  min_value = N + 1
  queue = []
  heapq.heappush(queue, (0, N))

  while True:
    if len(queue) == 0:
      print(min_cost)
      return

    c, n = heapq.heappop(queue)

    if n > min_value * 2:
      continue

    if n == 0:
      print(c)
      return

    min_value = n

    if n < 1e+9:
      min_cost = min(c + D * n, min_cost)

    if n < 2:
      continue

    m2 = n % 2

    if m2 == 0:
      heapq.heappush(queue, (c + A, n // 2))
    else:
      heapq.heappush(queue, (c + A + D, (n - 1) // 2))

    if n < 3:
      continue

    m3 = n % 3

    if m3 == 0:
      heapq.heappush(queue, (c + B, n // 3))
    elif m3 == 1:
      heapq.heappush(queue, (c + B + D, (n - 1) // 3))
    else:
      heapq.heappush(queue, (c + B + D, (n + 1) // 3))

    if n < 5:
      continue

    m5 = n % 5

    if m5 == 0:
      heapq.heappush(queue, (c + C, n // 5))
    elif m5 == 1:
      heapq.heappush(queue, (c + C + D, (n - 1) // 5))
    elif m5 == 2:
      heapq.heappush(queue, (c + C + D + D, (n - 2) // 5))
    elif m5 == 3:
      heapq.heappush(queue, (c + C + D + D, (n + 2) // 5))
    else:
      heapq.heappush(queue, (c + C + D, (n + 1) // 5))


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


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import resource
n = int(input())
e = [[int(i) for i in input().split()] for i in range(n)]
sys.setrecursionlimit(10 ** 9)


class Solve:

    def __init__(self,n,e):
        self.min = False
        self.T = n
        self.E = e
        self.i = 0

    def solve(self,num,cnt):
        if (num == self.E[self.i][0]):
            if min == False:
                self.min = cnt
            elif self.min > cnt:
                self.min = cnt
            return cnt
        if (num > self.E[self.i][0]):
            return cnt + (num - self.E[self.i][0]) * self.E[self.i][4]
        if (self.min != False) and (self.min < cnt):
            return self.cnt
        else:
            a = self.solve(num*2,cnt+self.E[self.i][1])
            b = self.solve(num*3,cnt+self.E[self.i][2])
            c = self.solve(num*5,cnt+self.E[self.i][3])
            d = cnt + (self.E[self.i][0] - num ) * self.E[self.i][4]
            e = self.solve(num+1,cnt+self.E[self.i][4])
            res = min(a,b,c,d,e)
            return res

    def init_func(self):
        for i in range(self.T):
            ans = self.solve(1,self.E[self.i][4])
            print(ans)
            self.i += 1
            self.min = False

sv = Solve(n,e)

sv.init_func()

Submission status: Time Limit Exceeded

Solution code:
def get(target,cost_one,cost_two,cost_three,cost_five):
  dp = [float("inf") for _ in range(target+1000)]
  if target ==1:
    return cost_one
  if target == 0:
    return 0
  dp[1] = cost_one
  dp[2] = min(dp[1]*2,dp[1] + cost_two,dp[1] + cost_three + cost_one,dp[1] + cost_five + 3*cost_one)
  for i in range(3,target + 101):
    minima = float("inf")
    minima = min(minima, dp[1]*i)
    if i%2 == 0:
      minima = min(minima,dp[i//2] + cost_two)
    if i%3 == 0:
      minima = min(minima,dp[i//3] + cost_three)
    if i%5 == 0:
      minima = min(minima,dp[i//5] + cost_five)
    dp[i] = min(minima,dp[i-1] + cost_one)
  for j in range(target+1,target+101):
    dp[target] = min(dp[target],dp[j] + (j-target)*cost_one)
  return dp[target]
for _ in range(int(input())):
  target,cost_two,cost_three,cost_five,cost_one  =list(map(int,input().split()))
  print(get(target,cost_one,cost_two,cost_three,cost_five))

Submission status: Time Limit Exceeded

Solution code:
import heapq
import collections


def main():
    INF = 10**30
    T = int(input())
    cases = [list(map(int, input().split())) for _ in range(T)]
    for case in cases:
        N, A, B, C, D = case
        coins = collections.defaultdict(lambda : INF)
        coins[0] = 0
        frontier = [(0, 0)]
        ans = 0
        while len(frontier) > 0:
            c, node = heapq.heappop(frontier)
            if node == N:
                ans = c
                break
            candidates = [
                (c + A, 2 * node),
                (c + B, 3 * node),
                (c + C, 5 * node),
                (c + D, node + 1),
                (c + D, node - 1)
            ]
            for cand in candidates:
                if cand[1] > 0 and cand[0] < coins[cand[1]]:
                    heapq.heappush(frontier, cand)
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
'''
T = 5
N = 11
A = 1#*2
B = 2#*3
C = 4#*5
D = 8#+1
'''


T = int(input())
#T = 1
for _ in range(T):
	N, A, B, C, D = map(int, input().split())
	#[A, B, C, D]
	memo = [0, D]#{1: D}
	for i in range(2, N+2):
		cost = memo[i-1] + D
		if not i%2:
			cost = min(cost, memo[int(i/2)] + A)
		if not i%3:
			cost = min(cost, memo[int(i/3)] + B)
		if not i%5:
			cost = min(cost, memo[int(i/5)] + C)
		#memo[i] = cost
		memo.append(cost)
		memo[i-1] = min(memo[i-1], cost + D)
		#print(str(i)+' >>> '+str(cost))
	print(memo[N])
print()

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heapify, heappop, heappush

def solve():
      input = sys.stdin.readline
      T = int(input())
      Ans = [0] * T
      for i in range(T):
            N, A, B, C, D = map(int, input().split())
            minPay = dict()
            minPay[0] = N * D
            q = []
            heapify(q)
            heappush(q, (0, N))
            while q:
                  cost, n = heappop(q)
                  if n not in minPay and n >= 0:
                        minPay[n] = cost
                        minPay[0] = min(minPay[0], cost + D * n)
                        if n % 2 == 0: heappush(q, (cost + A, n // 2))
                        else:
                              heappush(q, (cost + D, n + 1))
                              heappush(q, (cost + D, n - 1))
                        if n % 3 == 0: heappush(q, (cost + B, n // 3))
                        else:
                              m = n % 3
                              heappush(q, (cost + D * (3 - m), n + (3 - m)))
                              heappush(q, (cost + D * m, n - m))
                        if n % 5 == 0: heappush(q, (cost + C, n // 5))
                        else:
                              m = n % 5
                              heappush(q, (cost + D * (5 - m), n + (5 - m)))
                              heappush(q, (cost + D * m, n - m))
                  elif n == 0:
                        minPay[n] = min(minPay[n], cost)
                        break

            Ans[i] = minPay[0]
                        
      print(*Ans, sep="\n")


      return 0

if __name__ == "__main__":
      solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heapify, heappop, heappush

def solve():
      input = sys.stdin.readline
      T = int(input())
      Ans = [0] * T
      for i in range(T):
            N, A, B, C, D = map(int, input().split())
            minPay = dict()
            minPay[0] = N * D
            q = []
            heapify(q)
            heappush(q, (0, N))
            while q:
                  cost, n = heappop(q)
                  if n not in minPay and n >= 0:
                        minPay[n] = cost
                        minPay[0] = min(minPay[0], cost + D * n)
                        if n % 2 == 0: heappush(q, (cost + A, n // 2))
                        else:
                              heappush(q, (cost + D, n + 1))
                              heappush(q, (cost + D, n - 1))
                        if n % 3 == 0: heappush(q, (cost + B, n // 3))
                        else:
                              m = n % 3
                              heappush(q, (cost + D * (3 - m), n + (3 - m)))
                              heappush(q, (cost + D * m, n - m))
                        if n % 5 == 0: heappush(q, (cost + C, n // 5))
                        else:
                              m = n % 5
                              heappush(q, (cost + D * (5 - m), n + (5 - m)))
                              heappush(q, (cost + D * m, n - m))
                  elif n == 0:
                        minPay[n] = min(minPay[n], cost)

            Ans[i] = minPay[0]
                        
      print(*Ans, sep="\n")


      return 0

if __name__ == "__main__":
      solve()

Submission status: Time Limit Exceeded

Solution code:
'''
T = 5
N = 11
A = 1#*2
B = 2#*3
C = 4#*5
D = 8#+1
'''


T = int(input())
for _ in range(T):
	N, A, B, C, D = map(int, input().split())
	#[A, B, C, D]
	memo = {1: D}
	for i in range(2, N+2):
		cost = memo[i-1] + D
		if not i%2:
			cost = min(cost, memo[i/2] + A)
		if not i%3:
			cost = min(cost, memo[i/3] + B)
		if not i%5:
			cost = min(cost, memo[i/5] + C)
		memo[i] = cost
		memo[i-1] = min(memo[i-1], cost + D)
		#print(str(i)+' >>> '+str(cost))
	print(memo[N])
print()

Submission status: Time Limit Exceeded

Solution code:
DP = {}

def solve(n, a, b, c, d):
    if n <= 0: 
        return 0
    if n == 1:
        return d
    if n in DP:
        return DP[n]
    ans = float('inf')
    for i in range(-4, 5):
        num = n + i
        trash = abs(i)*d
        if num < 0:
            continue
        if num%5 == 0 and num // 5 < n:
            ans = min(ans, solve(num//5, a, b, c, d) + min(c, d*(num-(num//5))) + trash)
        if num%3 == 0 and num // 3 < n:
            ans = min(ans, solve(num//3, a, b, c, d) + min(b, d*(num-(num//3))) + trash)
        if num%2 == 0 and num // 2 < n:
            ans = min(ans, solve(num//2, a, b, c, d) + min(a, d*(num-(num//2))) + trash)
        # print(str(n) + ' ' + str(ans) + ' ' + str(num) + ' ' + str(i))
    DP[n] = int(ans)

    return int(ans)

def solve2():
    DP.clear()
    ans = float('inf')
    n, a, b, c, d = map(int, input().split())
    # for i in range(0, 65):
    #     for j in range(0, 30):
    #             for k in range(0, 10):
    #                 val = pow(2, i)*pow(3, j)*pow(5, k)
    #                 ans = min(ans, a*i + b*j + c*k + abs(n - val)*(d))
    # print(ans)
                    
    print(solve(n, a, b, c,d))
    
t = int(input())
for _ in range(t):
    solve2()