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:
import sys

sys.setrecursionlimit(10**6)

# def dfs(t,ans):
#     global a,b,c,d fin
#     if t % 5 == 0:
#         if c > 4*t//5 * d:
#             fin = min(fin,ans+4*t//5*d)
#         else:
#             dfs(t//5,ans+c)
#     if t % 3 == 0:
#         if b > 2*t//3 * d:
#             fin = min(fin,ans+2*t//3*d)
#         else:
#             dfs(t//3,ans+b)
#     if t % 2 == 0:
#         if a > t//2 * d:
#             fin = min(fin,ans+t//2*d)
#         else:
#             dfs(t//2,ans+a)
def solve(t,ans):
    global a,b,c,d,fin,al,dic1
    # print(t)
    dic1[t] = ans
    if t < 5:
        if t==1:
            fin = min(fin,ans+d)
        elif t == 2:
            fin = min(fin,ans+2*d,ans+a+d,)
        elif t == 3:
            fin = min(fin,ans+3*d,ans+b+d,ans+a+2*d)
        else:
            fin = min(fin,ans+2*d+c,ans+4*d,ans+2*d+b,ans+2*a+d,ans+a+2*d)
    else:
        if t % 5 == 0:
            if c > 4*t//5 * d:
                fin = min(fin,ans+t*d)
            else:
                if t//5 not in dic1:
                    solve(t//5,ans+c)
                elif dic1[t//5] > ans+c:
                    solve(t//5,ans+c)
        if t % 3 == 0:
            if b > 2*t//3 * d:
                fin = min(fin,ans+t*d)
            else:
                if t//3 not in dic1:
                    solve(t//3,ans+b)
                elif dic1[t//3] > ans+b:
                    solve(t//3,ans+b)

        if t % 2 == 0:
            if a > t//2 * d:
                fin = min(fin,ans+t*d)
            else:
                if t//2 not in dic1:
                    solve(t//2,ans+a)
                elif dic1[t//2] > ans+a:
                    solve(t//2,ans+a)
  
        for i in al:
            u = t+i
            ans_temp = ans + d*abs(i)
            if u % 5 == 0:
                if c > 4*u//5 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//5 not in dic1:
                        solve(u//5,ans_temp+c)
                    elif dic1[u//5] > ans_temp+c:
                        solve(u//5,ans_temp+c)
            if u % 3 == 0:
                if b > 2*u//3 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//3 not in dic1:
                        solve(u//3,ans_temp+b)
                    elif dic1[u//3] > ans_temp+b:
                        solve(u//3,ans_temp+b)

            if u % 2 == 0:
                if a > u//2 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//2 not in dic1:
                        solve(u//2,ans_temp+a)
                    elif dic1[u//2] > ans_temp+a:
                        solve(u//2,ans_temp+a)
        # while fa or fb or fc:
        #     u = t+cnt
        #     ans_temp = ans + d*abs(i)
        #     if u % 5 == 0:
        #         if c > 4*u//5 * d:
        #             fin = min(fin,ans_temp+u*d)
        #         else:
        #             solve(u//5,ans_temp+c)
        #     if u % 3 == 0:
        #         if b > 2*u//3 * d:
        #             fin = min(fin,ans_temp+u*d)
        #         else:
        #             solve(u//3,ans_temp+b)
        #     if u % 2 == 0:
        #         if a > u//2 * d:
        #             fin = min(fin,ans_temp+u*d)
        #         else:
        #             solve(u//2,ans_temp+a)
            # if u == 1:
            #     fin = min(fin,ans_temp+d)
t = int(input())
al = [1,-1,2,-2]


for i in range(t):
    n,a,b,c,d = map(int,input().split())
    fin = 10**30
    dic1 = {}
    solve(n,0)
    print(fin)

Submission status: Time Limit Exceeded

Solution code:
t=int(input())
for _ in range(t):
  n,a,b,c,d=map(int,input().split())
  ans=d*n
  current=1
  counter2=0
  counter3=0
  counter5=0
  while pow(2,counter2)<=2*n:
    counter3=0
    while pow(2,counter2)*pow(3,counter3)<=3*n:
      counter5=0
      while pow(2,counter2)*pow(3,counter3)*pow(5,counter5)<=5*n:
        objective=abs(n-pow(2,counter2)*pow(3,counter3)*pow(5,counter5))
        tempcounter2=counter2
        tempcounter3=counter3
        tempcounter5=counter5
        tempbest=objective
        tempbest2=counter2
        tempbest3=counter3
        tempbest5=counter5
        dcounter=0
        breakflag=0
        while objective>0:
          tempbest=objective
          for i in range(tempcounter2+1):
            if pow(2,i)>2*objective:
              break
            for j in range(tempcounter3+1):
              if pow(2,i)*pow(3,j)>3*objective:
                break
              for k in range(tempcounter5+1):
                if pow(2,i)*pow(3,j)*pow(5,k)>5*objective:
                  break
                if abs(pow(2,i)*pow(3,j)*pow(5,k)-objective)<tempbest:
                  tempbest2=i
                  tempbest3=j
                  tempbest5=k
                  tempbest=abs(pow(2,i)*pow(3,j)*pow(5,k)-objective)
                if tempbest==0:
                  breakflag=1
                  break
              if breakflag==1:
                break
            if breakflag==1:
              break
          tempcounter2=tempbest2
          tempcounter3=tempbest3
          tempcounter5=tempbest5
          r=(pow(2,tempbest2)*pow(3,tempbest3)*pow(5,tempbest5))
          if r<=objective:
            dcounter+=objective//r
            objective=objective%r
          else:
            dcounter+=1
            objective=r-objective
          if breakflag==1:
            break
        ans=min(counter2*a+counter3*b+counter5*c+dcounter*d,ans)
        counter5+=1
      counter3+=1
    counter2+=1
  print(ans+d)

Submission status: Time Limit Exceeded

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


dic = dict({})
min_coin = 100

def  solve(n,cost,coin,flag):
    global min_coin
    global dic

    if n == 1:
        return min(coin+cost[3],min_coin)
    if coin >= min_coin:
        return min_coin
    
    if dic.get(n,-1)==-1 or dic[n] > coin:
        dic[n] = min_coin
    elif dic[n] <= coin:
        return dic[n]
    
    
    if n%2==0:
        flag = 0
        min_coin = solve(n//2,cost,coin+cost[0],flag)
    if n%3==0:
        flag = 0
        min_coin = solve(n//3,cost,coin+cost[1],flag)
    if n%5==0:
        flag = 0
        min_coin = solve(n//5,cost,coin+cost[2],flag)
    
    if flag == 0:
        min_coin = solve(n-1,cost,coin+cost[3],1)
        min_coin = solve(n+1,cost,coin+cost[3],-1)
    if flag==1:
        min_coin = solve(n-1,cost,coin+cost[3],1)
    if flag==-1:
        min_coin = solve(n+1,cost,coin+cost[3],-1)

    return min_coin

def main():
    t = int(input())
    for poipoi in range(t):
        n,a,b,c,d = map(int,sys.stdin.readline().rstrip().split())
        cost = [a,b,c,d]
        global dic
        global min_coin
        dic.clear()
        min_coin = cost[3]*n
        ans = solve(n,cost,0,0)
        print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

t = int(input())

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

INF = float('inf')
from functools import lru_cache
@lru_cache(None)
def dfs(now,cost,a,b,c,d):
    if now == 0:
        return cost
    elif now == 1:
        return cost + d
    elif now == 2:
        return min(cost+d+a, cost+d*2)
    elif now <0:
        return INF

    tmp = cost + now*d

    # over 2
    sho = now//2+1
    fusoku = sho*2 - now
    over2 = dfs(sho,cost+d*fusoku+a,a,b,c,d)

    # not over 2
    sho = now//2
    amari = now-sho*2
    nver2 = dfs(sho,cost+d*amari+a,a,b,c,d)

    # over 3
    sho = now//3+1
    fusoku = sho*3 - now
    over3 = dfs(sho,cost+d*fusoku+b,a,b,c,d)

    # not over 3
    sho = now//3
    amari = now-sho*3
    nver3 = dfs(sho,cost+d*amari+b,a,b,c,d)

    # over 5
    sho = now//5+1
    fusoku = sho*5 - now
    over5 = dfs(sho,cost+d*fusoku+c,a,b,c,d)

    # not over 5
    sho = now//5
    amari = now-sho*5
    nver5 = dfs(sho,cost+d*amari+c,a,b,c,d)

    return min(tmp,over2,nver2,over3,nver3,over5,nver5)


for n,a,b,c,d in nabcd:
    ans = dfs(n,0,a,b,c,d)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
T = int(input())

caseList = []

for i in range(T):
    caseList.append(list(map(int, input().split())))
    
for N, A, B, C, D in caseList:
    dic = {N: 0}
    
    minAns = 999999999999
    searchSet = set([N])

    count = 0
    k=N
    while True:
        tmpSet = set()

        v = dic[k]

        if k == 1:
            continue

        # A
        if k % 2 == 0:
            dic[k // 2] = dic.get(k // 2, minAns)
            if dic[k // 2] > v + A:
                dic[k // 2] = v + A
                tmpSet.add(k // 2)

        # B
        if k % 3 == 0:
            dic[k // 3] = dic.get(k // 3, minAns)
            if dic[k // 3] > v + B:
                dic[k // 3] = v + B
                tmpSet.add(k // 3)

        # C
        if k % 5 == 0:
            dic[k // 5] = dic.get(k // 5, minAns)
            if dic[k // 5] > v + C:
                dic[k // 5] = v + C
                tmpSet.add(k // 5)

        # D
        dic[k + 1] = dic.get(k + 1, minAns)
        if dic[k + 1] > v + D:
            dic[k + 1] = v + D
            tmpSet.add(k + 1)

        dic[k - 1] = dic.get(k - 1, minAns)
        if dic[k - 1] > v + D:
            dic[k - 1] = v + D
            tmpSet.add(k - 1)

        del dic[k]
        k=min(dic, key=dic.get)


        count += 1
        if 1 in dic.keys():
            if minAns > dic[1] + D:
                minAns = dic[1] + D
            #             print(minAns)
            else:
                break
    print(minAns)

Submission status: Time Limit Exceeded

Solution code:
t=int(input())
while t!=0:
	t-=1
	n,a,b,c,d = map(int,input().split())
	i=62
	j=38
	k=27
	mn = 2**62
	for i in range(62,-1,-1):
		for j in range(38,-1,-1):
			for k in range(27,-1,-1):
				for l in range(3):
					for p in range(5):
						if l%3 == 0:
							ans = (2**i) * (3**j + p) * (5**k)
						elif l%3 == 1:
							ans = (2**i+p) * (3**j) * (5**k)
						else:
							ans = (2**i) * (3**j) * (5**k+p)
						cost = (a*i) + (b*j) + (c*k)
						cost += (abs(ans-n)*d)
						mn=min(mn,cost)
	print(mn+d)

Submission status: Time Limit Exceeded

Solution code:
def Next(): return input()
def NextInt(): return int(Next())
def NextInts(): return map(int,input().split())
def Nexts(): return map(str,input().split())
def NextIntList(): return list(map(int,input().split()))
def RowInts(n): return [input() for i in range(n)]

used = {}
used[0] = 0
gg = {}

def dfs(n, a, b, c, d):
    global used
    # print(n)
    if n in used: return used[n]
    ret = n*d
    for i in range(-4, 4):
        now = n + i
        if now%2==0 and now > 0 and abs(i) < 2: ret = min(ret, abs(i)*d + a + dfs(now//2, a, b, c, d))
        if now%3==0 and now > 0 and abs(i) < 3: ret = min(ret, abs(i)*d + b + dfs(now//3, a, b, c, d))
        if now%5==0 and now > 0: ret = min(ret, abs(i)*d + c + dfs(now//5, a, b, c, d))
    return ret

def solve():
    n,a,b,c,d = NextInts()
    global used
    used = {}
    gg = {}
    used[0] = 0
    used[1] = d
    used[2] = min(d*2, d+a)
    return dfs(n, a, b, c,d)
    
def main():
    t = NextInt()
    ans = [solve() for i in range(t)]
    for i in range(t):
        print(ans[i])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
T = int(input())
for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    data = [[N, 0]]
    ans = 10**18
    while data:
        n, m = heapq.heappop(data)
        if ans < m:
            continue
        if n == 1:
            ans = min(ans, m+D)
            continue
        if n%2 == 0:
            heapq.heappush(data, [n//2, m+min(A, (n-n//2)*D)])
        else:
            heapq.heappush(data, [(n+1)//2, m+min(A+D, (n-(n+1)//2)*D)])
            heapq.heappush(data, [(n-1)//2, m+min(A+D, (n-(n-1)//2)*D)])
        if n%3 == 0:
            heapq.heappush(data, [n//3, m+min(B, (n-n//3)*D)])
        elif n%3 == 1:
            heapq.heappush(data, [(n-1)//3, m+min(B+D, (n-(n-1)//3)*D)])
            heapq.heappush(data, [(n+2)//3, m+min(B+D*2, (n-(n+2)//3)*D)])
        elif n>3:
            heapq.heappush(data, [(n+1)//3, m+min(B+D, (n-(n+1)//3)*D)])
            heapq.heappush(data, [(n-2)//3, m+min(B+D*2, (n-(n-2)//3)*D)])
        if n%5 == 0:
            heapq.heappush(data, [n//5, m+min(C, (n-n//5)*D)])
        elif n%5 == 1:
            heapq.heappush(data, [(n-1)//5, m+min(C+D, (n-(n-1)//5)*D)])
            heapq.heappush(data, [(n+4)//5, m+min(C+D*4, (n-(n+4)//5)*D)])
        elif n%5 == 2 and n>5:
            heapq.heappush(data, [(n-2)//5, m+min(C+D*2, (n-(n-2)//5)*D)])
            heapq.heappush(data, [(n+3)//5, m+min(C+D*3, (n-(n+3)//5)*D)])
        elif n%5 == 3 and n>5:
            heapq.heappush(data, [(n-3)//5, m+min(C+D*3, (n-(n-3)//5)*D)])
            heapq.heappush(data, [(n+2)//5, m+min(C+D*2, (n-(n+2)//5)*D)])
        elif n%5 == 4 and n>5:
            heapq.heappush(data, [(n-4)//5, m+min(C+D*4, (n-(n-4)//5)*D)])
            heapq.heappush(data, [(n+1)//5, m+min(C+D, (n-(n+1)//5)*D)])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
t=int(input())
while t!=0:
	t-=1
	n,a,b,c,d = map(int,input().split())
	i=62
	j=38
	k=27
	mn = 2**62
	for i in range(62,-1,-1):
		for j in range(38,-1,-1):
			for k in range(27,-1,-1):
				for l in range(3):
					for p in range(10):
						if l%3 == 0:
							ans = (2**i) * (3**j + p) * (5**k)
						elif l%3 == 1:
							ans = (2**i+p) * (3**j) * (5**k)
						else:
							ans = (2**i) * (3**j) * (5**k+p)
						cost = (a*i) + (b*j) + (c*k)
						cost += (abs(ans-n)*d)
						mn=min(mn,cost)
	print(mn+d)

Submission status: Time Limit Exceeded

Solution code:
t=int(input())
while t!=0:
	t-=1
	n,a,b,c,d = map(int,input().split())
	i=62
	j=38
	k=27
	mn = 2**62
	for i in range(62,-1,-1):
		for j in range(38,-1,-1):
			for k in range(27,-1,-1):
				for l in range(3):
					for p in range(10):
						if i%3 == 0:
							ans = (2**i) * (3**j + p) * (5**k)
						elif i%3 == 1:
							ans = (2**i+p) * (3**j) * (5**k)
						else:
							ans = (2**i) * (3**j) * (5**k+p)
						cost = (a*i) + (b*j) + (c*k)
						cost += (abs(ans-n)*d)
						mn=min(mn,cost)
	print(mn+d)

Submission status: Time Limit Exceeded

Solution code:
t=int(input())
while t!=0:
	t-=1
	n,a,b,c,d = map(int,input().split())
	i=62
	j=38
	k=27
	mn = 2**62
	for i in range(62,-1,-1):
		for j in range(38,-1,-1):
			for k in range(27,-1,-1):
				for l in range(3):
					for p in range(100):
						if i%3 == 0:
							ans = (2**i) * (3**j + p) * (5**k)
						elif i%3 == 1:
							ans = (2**i+p) * (3**j) * (5**k)
						else:
							ans = (2**i) * (3**j) * (5**k+p)
						cost = (a*i) + (b*j) + (c*k)
						cost += (abs(ans-n)*d)
						mn=min(mn,cost)
	print(mn+d)

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
    lbound = 0
    ubound = 2

    while dp[-1][N] == 0:
        nowcoin += 1
        newline = list(dp[-1])
        if newline[lbound] == 1:
            lbound += 1
        print(lbound)

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

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

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}
    for z in [2, 3, 5]:
        x, y = 1, d
        while True:
            x *= z
            if x in mae:
                mae[x] = min(mae[x], y)
            else:
                mae[x] = y
            if x > n:break
    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 k == 1: 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] = cost
                    mae[tugi] = cost
            else:
                dic[tugi] = cost
                mae[tugi] = cost
            # b
            tugi = k * 3
            cost = v + b
            if tugi == n:
                sep = min(sep, cost)
            elif tugi in mae:
                if mae[tugi] > cost:
                    dic[tugi] = cost
                    mae[tugi] = cost
            else:
                dic[tugi] = cost
                mae[tugi] = cost
            # c
            tugi = k * 5
            cost = v + c
            if tugi == n:
                sep = min(sep, cost)
            elif tugi in mae:
                if mae[tugi] > cost:
                    dic[tugi] = cost
                    mae[tugi] = cost
            else:
                dic[tugi] = cost
                mae[tugi] = cost
            # d
            tugi = k + 1
            cost = v + d
            if tugi == n:
                sep = min(sep, cost)
            elif tugi in mae:
                if mae[tugi] > cost:
                    dic[tugi] = cost
                    mae[tugi] = cost
            else:
                dic[tugi] = cost
                mae[tugi] = cost
            # e
            tugi = k - 1
            cost = v + d
            if tugi == n:
                sep = min(sep, cost)
            elif tugi in mae:
                if mae[tugi] > cost:
                    dic[tugi] = cost
                    mae[tugi] = cost
            else:
                dic[tugi] = cost
                mae[tugi] = cost
        now = deepcopy(dic)
    print(sep)

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):
    now=1
    a=0
    b=0
    c=0
    d=1
    N=L[i][0]
    A=L[i][1]
    B=L[i][2]
    C=L[i][3]
    D=L[i][4]
    s=0
    v=0
    m=0
    ans=0
    while now<N or s!=1:
        k=[4*A,2*B,C,4*now*D]
        if min(k)==4*A:
            if now*2>=N:
                s=1
                v=2
            else:
                a+=1
                now*=2
        elif min(k)==2*B:
            if now*3>=N:
                s=1
                v=3
            else:
                b+=1
                now*=3
        elif min(k)==C:
            if now*5>=N:
                s=1
                v=5
            else:
                c+=1
                now*=5
        else:
            d+=1
            now+=1
            
    ans=A*a+B*b+C*c+D*d
    if now==N:
        print(ans)
    elif v==2:
        print(min(D*(N-now),A+D*(now*2-N))+ans)
    elif v==5:
        print(ans+min(A+abs(N-2*now)*D,B+abs(N-3*now)*D,2*A+abs(N-4*now)*D,C+abs(N-5*now)*D))
    elif v==3:
        print(ans+min((3*now-N)*D+B,A+abs(N-2*now)*D,(N-now)*D))
    else:
        print("er")

Submission status: Time Limit Exceeded

Solution code:
from collections import abc
import math

t = int(input())
def power(p, q, r):
    return 2**p * 3**q * 5**r

def ans(n, a, b, c, d):
    dp = [[[2e18]*101]*101]*101
    dp[0][0][0] = d*(1 + abs(n - 1))
    for i in range(math.ceil(math.log(n, 2))):
        for j in range(math.ceil(math.log(n, 3))):
            for k in range(math.ceil(math.log(n, 5))):
                if i-1 >= 0:
                    choice1 = dp[i-1][j][k] + min(a, d*(power(i, j, k) - power(i-1, j, k))) + d*abs(abs(n - power(i, j, k)) - abs(n - power(i-1, j, k)))
                else:
                    choice1 = 2e18
                if j-1 >= 0:
                    choice2 = dp[i][j-1][k] + min(b, d*(power(i, j, k) - power(i, j-1, k))) + d*abs(abs(n - power(i, j, k)) - abs(n - power(i, j-1, k)))
                else:
                    choice2 = 2e18
                if k-1 >= 0:
                    choice3 = dp[i][j][k-1] + min(c, d*(power(i, j, k) - power(i, j, k-1))) + d*abs(abs(n - power(i, j, k)) - abs(n - power(i, j, k-1)))
                else:
                    choice3 = 2e18
                dp[i][j][k] = min(choice1, choice2, choice3)
    def flatten(l):
        for el in l:
            if isinstance(el, abc.Iterable) and not isinstance(el, (str, bytes)):
                yield from flatten(el)
            else:
                yield el
    return min(flatten(dp))

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

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 = [N]
        visited = defaultdict(defLarge)
        visited[N] = 0
        minValue = 10 ** 18

        def insertIf(S, value, index):
            if visited[index] > value:
                visited[index] = value
                S.append(index)

        while len(current) != 0:
            next = []
            for n in current:
                c = visited[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
    lbound = 0
    ubound = 2

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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1000000)
def ans(n,l,p,c):
    if p>n:
        return ((p-n)*l[3])+c
    elif p==n:
        return c
    elif n/p <= 2:
        return min([ans(n,l,p*2,c+l[0]),ans(n,l,p*3,c+l[1]),ans(n,l,p*5,c+l[2]),((n-p)*l[3])+c])
    else:
        return min([ans(n,l,p*2,c+l[0]),ans(n,l,p*3,c+l[1]),ans(n,l,p*5,c+l[2]),ans(n,l,p+1,c+l[3])])
for _ in range(int(input())):
    n,a,b,c,d = map(int, input().split())
    Ans = ans(n,[a,b,c,d],0+1,0+d)
    print(Ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import abc
import math

t = int(input())
def power(p, q, r):
    return 2**p * 3**q * 5**r

def ans(n, a, b, c, d):
    dp = [[[float('inf')]*101]*101]*101
    dp[0][0][0] = d*(1 + abs(n - 1))
    for i in range(math.ceil(math.log(n, 2))):
        for j in range(math.ceil(math.log(n, 3))):
            for k in range(math.ceil(math.log(n, 5))):
                if i-1 >= 0:
                    choice1 = dp[i-1][j][k] + min(a, d*(power(i, j, k) - power(i-1, j, k))) + d*abs(abs(n - power(i, j, k)) - abs(n - power(i-1, j, k)))
                else:
                    choice1 = float('inf')
                if j-1 >= 0:
                    choice2 = dp[i][j-1][k] + min(b, d*(power(i, j, k) - power(i, j-1, k))) + d*abs(abs(n - power(i, j, k)) - abs(n - power(i, j-1, k)))
                else:
                    choice2 = float('inf')
                if k-1 >= 0:
                    choice3 = dp[i][j][k-1] + min(c, d*(power(i, j, k) - power(i, j, k-1))) + d*abs(abs(n - power(i, j, k)) - abs(n - power(i, j, k-1)))
                else:
                    choice3 = float('inf')
                dp[i][j][k] = min(choice1, choice2, choice3)
    def flatten(l):
        for el in l:
            if isinstance(el, abc.Iterable) and not isinstance(el, (str, bytes)):
                yield from flatten(el)
            else:
                yield el
    return min(flatten(dp))

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