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: Wrong Answer

Solution code:
T=int(input())
import heapq
for _ in range(T):
    N,A,B,C,D=map(int,input().split())
    minn=min(A,B,C,D)
    que=[(N,0)]
    ans=N*D
    while que:
        num,used=heapq.heappop(que)
        if used+minn>=ans:
            continue
        if num==1:
            ans=min(ans,used+D)
            continue
        if num%2==0:
            heapq.heappush(que,(num//2,used+A)) 
        else:
            heapq.heappush(que,((num-1)//2,used+A+D))
        b=num%3 
        if num%3==0:
            heapq.heappush(que,(num//3,used+B))
        elif b==1:
            heapq.heappush(que,((num-1)//3,used+B+D))
        else:
            heapq.heappush(que,((num+1)//3,used+B+D))
        c=num%5
        if num%5==0:
            heapq.heappush(que,(num//5,used+C))
        elif c==1 or c==2:
            heapq.heappush(que,((num-c)//5,used+C+D*c))
        else:
            c=5-c
            heapq.heappush(que,((num+c)//5,used+C+D*c))
        print(num,used)
    print(ans)

Submission status: Wrong Answer

Solution code:
import copy,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
T = I()
for _ in range(T):
    N,A,B,C,D = LI()
    ans = N*D
    dp = {1:D}
    num2,num3,num5 = 2,3,5
    while num2<=10**19:
        dp[num2] = min(dp.get(num2,float('INF')),dp[num2//2]+A)
        if num2//2<=N<=num2*2:
            dp[N] = min(dp.get(N,float('INF')),dp[num2]+abs(N-num2)*D)
            break
        num2 *= 2
    copy_dp = copy.deepcopy(dp)
    for k,v in copy_dp.items():
        num3 = 3*k
        while num3<=10**19:
            dp[num3] = min(dp.get(num3,float('INF')),dp[num3//3]+B)
            if num3//3<=N<=3*num3:
                dp[N] = min(dp.get(N,float('INF')),dp[num3]+abs(N-num3)*D)
                dp[N] = min(dp.get(N,float('INF')),dp[num3//3]+B+abs(N-num3//3*2)*D)
                dp[N] = min(dp.get(N,float('INF')),dp[num3]+2*B+abs(N-num3*2)*D)
                break
            num3 *= 3
    for k,v in copy_dp.items():
        num5 = 5*k
        while num5<=10**19:
            dp[num5] = min(dp.get(num5,float('INF')),dp[num5//5]+C)
            if num5//5<=N<=5*num5:
                dp[N] = min(dp.get(N,float('INF')),dp[num5]+abs(N-num5)*D)
                dp[N] = min(dp.get(N,float('INF')),dp[num5//5]+B+abs(N-num5//5*2)*D)
                dp[N] = min(dp.get(N,float('INF')),dp[num5]+2*B+abs(N-num5*2)*D)
                dp[N] = min(dp.get(N,float('INF')),dp[num5]+3*B+abs(N-num5*3)*D)
                dp[N] = min(dp.get(N,float('INF')),dp[num5//5]+C+abs(N-num5//5*3)*D)
                dp[N] = min(dp.get(N,float('INF')),dp[num5]+2*C+abs(N-num5*2)*D)
                break
            num5 *= 5
    print(dp[N])

Submission status: Wrong Answer

Solution code:
t = int(input())
pre_2 = [1] * 70
pre_3 = [1] * 40
pre_5 = [1] * 40
for i in range(1, 70):
    if i < 40:
        pre_3[i] = pre_3[i - 1] * 3
        pre_5[i] = pre_5[i - 1] * 5

    pre_2[i] = pre_2[i - 1] * 2

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

    for t in range(70):
        for u in range(40):
            for v in range(40):
                temp_n = pre_2[t] * pre_3[u] * pre_5[v]
                abc = a*t + b*u + c*v
                s1 = n // temp_n
                s2 = s1 + 1
                temp_cost = abc + min((s1 + (n - s1*temp_n)) * d, (s2 + (s2*temp_n - n)) * d)
                if temp_cost < cost:cost = temp_cost
    print(cost)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
T = int(input())
for _ in range(T):
    ch = [[[0]*100 for _ in range(100)] for __ in range(100)]
    ch[0][0][0] = 1
    N,A,B,C,D = map(int,input().split())
    deq = deque([[N,0,0,0,0]])
    MIN = INF
    while len(deq) != 0:
        n,a,b,c,d = deq.popleft()
        am = n % 2
        n2 = n // 2
        MIN = min(MIN,a*A+b*B+c*C+D*(d+n-1))
        if n2 == 0:
            continue
        if n2 == 1:
            MIN = min(MIN,(a+1)*A+b*B+c*C+D*(d+am))
        else:
            if ch[a+1][b][c] == 0:
                ch[a+1][b][c] = 1
                deq.append([n2,a+1,b,c,d+am])
                deq.append([n2+1,a+1,b,c,d+1])
                if n2 >= 3 and am == 0:
                    deq.append([n2-1,a+1,b,c,d+1])
        bm = n % 3
        n3 = n // 3
        if n3 == 0:
            continue
        if n3 == 1:
            MIN = min(MIN,a*A+(b+1)*B+c*C+D*(d+bm))
        else:
            if ch[a][b+1][c] == 0:
                ch[a][b+1][c] = 1
                deq.append([n3,a,b+1,c,d+bm])
                deq.append([n3+1,a,b+1,c,d+1+bm%2])
                if n3 >= 3 and bm == 0:
                    deq.append([n3-1,a,b+1,c,d+1])
        cm = n % 5
        n5 = n // 5
        if n5 == 0:
            continue
        if n5 == 1:
            if cm == 4:
                cmm = 2
            else:
                cmm = cm
            MIN = min(MIN,a*A+b*B+(c+1)*C+D*(d+cmm))
        else:
            if ch[a][b][c+1] == 0:
                ch[a][b][c+1] = 1
                if cm <= 2:
                    deq.append([n5,a,b,c+1,d+cm])
                    deq.append([n5+1,a,b,c+1,d+cm+1])
                else:
                    deq.append([n5,a,b,c+1,d+6-cm])
                    deq.append([n5+1,a,b,c+1,d+5-cm])
                if n5 >= 3 and cm == 0:
                    deq.append([n5-1,a,b,c+1,d+1])
    print(MIN+D)

Submission status: Wrong Answer

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_A = 999999 if i%2 else memo[i//2] + A
		cost_B = 999999 if i%3 else memo[i//3] + B
		cost_C = 999999 if i%5 else memo[i//5] + C
		cost_D = memo[i-1] + D
		#memo[i] = cost
		cost = min(cost_A, cost_B, cost_C, cost_D)
		memo.append(cost)
		memo[i-1] = min([memo[i-1], cost + D])
		#print(str(i)+' >>> '+str(cost))
	print(memo[N])
print()

Submission status: Wrong Answer

Solution code:
t = int(input())
for i in range(t):
    n, a, b, c, d = input().split()
    n = int(n)
    a = int(a)  # *2
    b = int(b)  # *3
    c = int(c)  # *5
    d = int(d)  # +1/-1

    std = min(a//d, b//(2*d), c//(4*d))  # <=std
    dic = {n:0}


    def chai(x):
        if x < std:
            s = dic[x]+(x-1)*d
            if 1 in dic:
                if s < dic[1]:
                    dic[1] = s
            else:
                dic[1] = s
            return None

        x1 = x//2
        x2 = (x+1)//3
        x3 = (x+2)//5

        s1 = (x-x1*2)*d+a+dic[x]
        if x1 in dic:
            if s1 < dic[x1]:
                dic[x1] = s1
                chai(x1)
        else:
            dic[x1] = s1
            chai(x1)

        s2 = abs(x-x2*3)*d+b+dic[x]
        if x2 in dic:
            if s2 < dic[x2]:
                dic[x2] = s2
                chai(x2)
        else:
            dic[x2] = s2
            chai(x2)

        s3 = abs(x-x3*5)*d+c+dic[x]
        if x3 in dic:
            if s3 < dic[x3]:
                dic[x3] = s3
                chai(x3)
        else:
            dic[x3] = s3
            chai(x3)


    chai(n)
    print(dic[1]+d)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

t = ni()
import heapq

for _ in range(t):
    n,a,b,c,d = na()
    p2,p3,p5 = n*2,n*3,n*5
    ans = 1000000000000000000
    for i in range(61):
        ii = 2**i
        if ii > p2:
            break
        for j in range(39):
            jj = ii*(3**j)
            if jj > p3:
                break
            for k in range(27):
                kk = jj*(5**k)
                if kk > p5:
                    break
                x = a*i+b*j+c*k
                if x > ans:
                    break
                dif = abs(kk-n)
                h = d*dif
                if dif < x:
                    h = min(h,(dif//5)*d)
                w = a*i+b*j+c*k
                ans = min(ans, w+h)
    print(ans)

Submission status: Wrong Answer

Solution code:
def agc044_a():
    T = int(input())
    Case = [tuple(map(int, input().split())) for _ in range(T)]

    def solve(N, A, B, C, D):
        mincost = N * D
        for x in range(60):  # 2の乗数
            for y in range(38):  # 3の乗数
                for z in range(26):  # 5の乗数
                    f = (2**x) * (3**y) * (5**z)
                    a, b = divmod(N, f)
                    if a == 0:
                        b = min(b, f-N)
                    cost = A*x + B*y + C*z + D*(a+b)
                    mincost = min(mincost, cost)
        return mincost

    for cs in Case:
        ans = solve(*cs)
        print(ans)

agc044_a()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    t = int(input())

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

        if n == 1:
            print(d)
            continue

        que = deque([])
        ans = float("Inf")

        que.append([1, d])
        while que:
            p = que.pop()
            num, cost = p[0], p[1]
            if num > n:
                continue

            if num == n:
                ans = min(ans, cost)
                continue
            if 2 * (num - 1) == n:
                ans = min(ans, cost + d + a)
                continue
            if 3 * (num - 1) == n:
                ans = min(ans, cost + d + b)
                continue
            if 5 * (num - 1) == n:
                ans = min(ans, cost + d + c)
                continue

            que.append([2 * num, cost + a])
            que.append([3 * num, cost + b])
            que.append([5 * num, cost + c])

        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
t = int(input())

for l in range(t):
  n, a, b, c, d = map(int,input().split())
  coin = 100100100100100100
  for aa in range(60):
    caa = 2**aa
    if caa > n:
      break
    for bb in range(38):
      cbb = 3**bb
      if cbb > n:
        break
      for cc in range(25):
        ccc = 5**cc
        if ccc > n:
          break
        for dd in range(30):
          abc = dd * caa * cbb * ccc
          ddd = abs(n - abc)
          coin = min(coin , a*aa + b*bb + c*cc + d*(dd+ddd))
  print(coin)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
T=int(input())
def u(n,c):
    global d
    if n<=1:
        return 0
    if n%2:
        if n//2 not in d or d[n//2]>c+A+D:
            d[n//2]=c+A+D
            u(n//2,c+A+D)
    else:
        if n//2 not in d or d[n//2]>c+A:
            d[n//2]=c+A
            u(n//2,c+A)
    if n%3<=1:
        if n//3 not in d or d[n//3]>c+B+n%3*D:
            d[n//3]=c+B+n%3*D
            u(n//3,c+B+n%3*D)
    else:
        if n//3+1 not in d or d[n//3+1]>c+B+D:
            d[n//3+1]=c+B+D
            u(n//3+1,c+B+D)
    if n%5<=2:
        if n//5 not in d or d[n//5]>c+C+n%5*D:
            d[n//5]=c+C+n%5*D
            u(n//5,c+C+n%5*D)
    else:
        if n//5+1 not in d or d[n//5+1]>c+C+(5-n%5)*D:
            d[n//5+1]=c+C+(5-n%5)*D
            u(n//5+1,c+C+(5-n%5)*D)
for i in range(T):
    N,A,B,C,D=map(int,input().split())
    d={}
    d[N]=0
    u(N,0)
    a=10**30
    for j,n in d.items():
        if j<=0:
            continue
        t=D*j+n
        if t<a:
            a=t
    print(a)

Submission status: Wrong Answer

Solution code:
print("the answer is AC ...sorry")

Submission status: Wrong Answer

Solution code:
# 探索範囲の計算
def search_range(n):
	min_ls = []
	max_ls = []
	for e in [2,3,5]:
		i = 1
		while True:
			if e ** i > n:
				max_ls.append(i)
				min_ls.append(i-1)
				break
			i += 1
	return min_ls, max_ls

t = int(input())

for test_n in range(t):
	# 入力取得
	n,a,b,c,d = [int(e) for e in input().split(" ")[:5]]
	# 探索範囲の計算
	min_ls, max_ls = search_range(n)
	min_n = min(2**min_ls[0], 3**min_ls[1], 5**min_ls[2])
	max_n = max(2**max_ls[0], 3**max_ls[1], 5**max_ls[2])
	# 探索
	min_val = d*n
	for i in range(max_ls[0]):
		for j in range(max_ls[1]):
			for k in range(max_ls[2]):
				temp_n = (2**i)*(3**j)*(5**k)
				# print("%d/%d, %d/%d, %d/%d"%(i, max_ls[0], j, max_ls[1], k, max_ls[2]))
				if temp_n < min_n or temp_n > max_n: continue
				# print("■■■■■■■■%d■■■■■■■■"%temp_n)
				result = [i,j,k]
				# print(temp_n, result)
				# コインの枚数
				temp_val = result[0] * a + result[1] * b + result[2] * c
				if result[0] != 0:
					temp_val2 = result[0] * (a-1) + result[1] * b + result[2] * c + d
					if temp_val2 < temp_val: temp_val = temp_val2
				# print("temp_val = %d"%temp_val)
				# print("plus_val = %d"%(abs(temp_n - n)*d))
				coin_n = temp_val + (abs(temp_n - n)*d) + d
				# print("coin_n = %d"%coin_n)
				if coin_n < min_val: min_val = coin_n
	# 結果出力
	print(min_val)

Submission status: Wrong Answer

Solution code:
T=int(input())

def div_cnt(n,m):
    ret=0
    if n<=0:
        return -1
    while True:
        if n//m>=1:
            ret+=1
            n//=m
        else:
            break
    return ret

for _ in range(T):
    N,A,B,C,D=map(int,input().split())
    ans=D*N
    n=div_cnt(N,2)
    a=[D]*(n+2)
    for i in range(n+2):
        val0=2**i
        if i==0:
            tmp0=a[0]
        else:
            if (val0//2)*D<=A:
                a[i]=a[i-1]+(val0//2)*D
            else:
                a[i]=a[i-1]+A
            tmp0=a[i]
        ans=min(ans,tmp0+D*abs(N-val0))
        m=div_cnt(N-val0,3)
        b=[tmp0]*(m+2)
        for j in range(m+2):
            val1=val0*(3**j)
            if j==0:
                tmp1=b[0]
            else:
                if (val1//3)*2*D<=B:
                    b[j]=b[j-1]+(val1//3)*2*D
                else:
                    b[j]=b[j-1]+B
                tmp1=b[j]
            ans=min(ans,tmp1+D*abs(N-val1))
            l=div_cnt(N-val1,5)
            c=[tmp1]*(l+2)
            for k in range(l+2):
                val2=val1*(5**k)
                if k==0:
                    tmp2=c[0]
                else:
                    if (val2//5)*4*D<=C:
                        c[k]=c[k-1]+(val2//5)*4*D
                    else:
                        c[k]=c[k-1]+C
                    tmp2=c[k]
                tmp2+=D*abs(N-val2)
                ans=min(ans,tmp2)
    print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

from operator import itemgetter

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

    for _ in tc:
        n,a,b,c,d = _[0],_[1],_[2],_[3],_[4]
        temp = 0
        coin = 0
        #  優先順を決める　３０倍で考える
        # a 2 b 3 c 5 d +-1
        cost = [[i] for i in range(3)]
        cost[0].append(a * 15)
        cost[0].append(2)
        cost[0].append(a)

        cost[1].append(b * 10)
        cost[1].append(3)
        cost[1].append(b)

        cost[2].append(c * 5)
        cost[2].append(5)
        cost[2].append(c)
        cost.sort(key=itemgetter(1))

        while  n > temp:
            if temp == 0:
                temp += 1
                coin += d

            # cost[index,order,ope,cost]
            t1 = temp * cost[0][2]
            c1 = cost[0][3]
            t2 = temp * cost[1][2]
            c2 = cost[1][3]
            t3 = temp * cost[2][2]
            c3 = cost[2][3]

            if abs(t1 - temp) * d < c1:
                if n - temp >= 0:
                    temp += 1
                else:
                    temp -= 1
                coin += d
                continue
            if t1 >= n:
                if t2 >= n:
                    if t3 >= n:
                        temp += 1
                        coin += d
                    else:
                        temp = t3
                        coin += c3
                        continue
                else:
                    temp = t2
                    coin += c2
                    continue
            else:
                temp = t1
                coin += c1
                continue

        # if n == temp >= 0:
        #     temp += 1
        # print(coin)
        # else:
        #     temp -= 1
        # coin += d
        # continue


        # print(temp)

        #     # print('coin',coin,'ope',ope,'n',n,'ans',ans)
        # # if n != 0:
        # #     coin += n * d            

        # print(temp)
        # print(cost)
        # print(cost[0])
        print(coin)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# import numpy as np
import sys
from collections import defaultdict
import math
import itertools
import bisect
from copy import deepcopy
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10000)

def solve():
    q = deque([1])
    ans = defaultdict(int)
    ans[0] = 0
    ans[1] = D
    while q :
        n = q.popleft()
        now = set()

        if n*2 in ans :
            if ans[n*2] > ans[n] + min( A , n*D) :
                ans[n*2] = ans[n] + min( A , n*D)
                if n*2 != N:
                    if n*2 not in now :
                        q.append(n*2)
                        now.add(n*2)
        elif n*2 <= N + 2:
            ans[n*2] = ans[n] + min( A , n*D )
            if n*2 != N:
                q.append(n*2)
        
        if n*3 in ans :
            if ans[n*3] > ans[n] + min( B , n*2*D):
                ans[n*3] = ans[n] + min( B , n*2*D )
                if n*3 != N:
                    if n*3 not in now:
                        q.append(n*2)
                        now.add(n*3)
        elif n*3 <= N + 2:
            ans[n*3] = ans[n] + min( B , n*2*D )
            if n*3 != N:
                q.append(n*3)

        if n*5 in ans :
            if ans[n*5] > ans[n] + min(C , 4*n*D) :
                ans[n*5] = ans[n] + min(C , 4*n*D)
                if n*5 != N:
                    if n*5 not in now:
                        q.append(n*5)
                        now.add(n*5)
        elif n*5 <= N + 5:
            ans[n*5] = ans[n] + min( C , 4*n*D)
            if n*5 != N:
                q.append(n*5)
        
        if n+1 in ans and (N-100 <= n+1 and n+1 <= N) or (N // 2 -1 <= n and N // 2 + 5) :
            if ans[n+1] > ans[n] + D :
                ans[n+1] = ans[n] + D
                if n+1 != N:
                    if n+1 not in now:
                        q.append(n+1)
                        now.add(n+1)
        elif n+1 <= N and N-100 <= n+1:
            ans[n+1] = ans[n] + D
            if n+1 != N:
                q.append(n+1)

        if n-1 in ans  and N <= n-1 and n-1 <= N+4 :
            if ans[n-1] > ans[n] + D and n-1 < N+2:
                ans[n-1] = ans[n] + D
                if n-1 != N:
                    if n-1 not in now:
                        q.append(n-1)
                        now.add(n-1)
        elif N <= n-1 and n-1 <= N+4:
            ans[n-1] = ans[n] + D
            if n-1 != N:
                q.append(n-1)
        
        """
        if N // 3 - 2 <= n and n <= N // 3 + 2 :
            if ans[n+1] in ans and ans[n] + D < ans[n+1] :
                ans[n+1] = ans[n] +D 
                if n+1 not in now:
                    q.append(n+1)
                    now.add(n+1)
            else:
                ans[n+1] = ans[n] +D 
                if n+1 not in now:
                    q.append(n+1)
                    now.add(n+1)
            
            if ans[n+2] in ans and ans[n] + (2*D) < ans[n+2]:
                ans[n+2] = ans[n] + (2*D) 
                if n+2 not in now:
                    q.append(n+2)
                    now.add(n+2)
            else:
                ans[n+2] = ans[n] + (2*D) 
                if n+2 not in now:
                    q.append(n+2)
                    now.add(n+2)

            if ans[n-1] in ans and ans[n] + D < ans[n-1] and n-1 > 0:
                ans[n-1] = ans[n] +D 
                if n-1 not in now:
                    q.append(n-1)
                    now.add(n-1)
            elif n-1 > 0:
                ans[n-1] = ans[n] +D 
                if n-1 not in now:
                    q.append(n-1)
                    now.add(n-1)

            if ans[n-2] in ans and ans[n] + (2*D) < ans[n-2] and n-2 > 0:
                ans[n-2] = ans[n] + (2*D) 
                if n-2 not in now:
                    q.append(n-2)
                    now.add(n-2)
            elif n-2 > 0:
                ans[n-2] = ans[n] + (2*D) 
                if n-2 not in now:
                    q.append(n-2)
                    now.add(n-2)

        if N // 2 - 1 <= n and n <= N // 2 + 1 :
            if ans[n+1] in ans and ans[n] + D < ans[n+1]:
                ans[n+1] = ans[n] +D 
                if n+1 not in now:
                    q.append(n+1)
                    now.add(n+1)
            else:
                ans[n+1] = ans[n] +D 
                if n+1 not in now:
                    q.append(n+1)
                    now.add(n+1)
            
            if ans[n+2] in ans and ans[n] + (2*D) < ans[n+2]:
                ans[n+2] = ans[n] + (2*D) 
                if n+2 not in now:
                    q.append(n+2)
                    now.add(n+2)
            else:
                ans[n+2] = ans[n] + (2*D) 
                if n+2 not in now:
                    q.append(n+2)
                    now.add(n+2)

            if ans[n-1] in ans and ans[n] + D < ans[n-1] and n-1 > 0:
                ans[n-1] = ans[n] +D 
                if n-1 not in now:
                    q.append(n-1)
                    now.add(n-1)
            elif n-1 > 0:
                ans[n-1] = ans[n] +D 
                if n-1 not in now:
                    q.append(n-1)
                    now.add(n-1)

            if ans[n-2] in ans and ans[n] + (2*D) < ans[n-2] and n-2 > 0:
                ans[n-2] = ans[n] + (2*D) 
                if n-2 not in now:
                    q.append(n-2)
                    now.add(n-2)
            elif n-2 > 0:
                ans[n-2] = ans[n] + (2*D) 
                if n-2 not in now:
                    q.append(n-2)
                    now.add(n-2)

        if N // 5 - 3 <= n and n <= N // 5 + 3 :
            if ans[n+1] in ans and ans[n] + D < ans[n+1]:
                ans[n+1] = ans[n] +D 
                if n+1 not in now:
                    q.append(n+1)
                    now.add(n+1)
            else:
                ans[n+1] = ans[n] +D 
                if n+1 not in now:
                    q.append(n+1)
                    now.add(n+1)
            
            if ans[n+2] in ans and ans[n] + (2*D) < ans[n+2]:
                ans[n+2] = ans[n] + (2*D) 
                if n+2 not in now:
                    q.append(n+2)
                    now.add(n+2)
            else:
                ans[n+2] = ans[n] + (2*D) 
                if n+2 not in now:
                    q.append(n+2)
                    now.add(n+2)

            if ans[n-1] in ans and ans[n] + D < ans[n-1] and n-1 > 0:
                ans[n-1] = ans[n] +D 
                if n-1 not in now:
                    q.append(n-1)
                    now.add(n-1)
            elif n-1 > 0:
                ans[n-1] = ans[n] +D 
                if n-1 not in now:
                    q.append(n-1)
                    now.add(n-1)

            if ans[n-2] in ans and ans[n] + (2*D) < ans[n-2] and n-2 > 0:
                ans[n-2] = ans[n] + (2*D) 
                if n-2 not in now:
                    q.append(n-2)
                    now.add(n-2)
            elif n-2 > 0:
                ans[n-2] = ans[n] + (2*D) 
                if n-2 not in now:
                    q.append(n-2)
                    now.add(n-2)

            if ans[n-3] in ans and ans[n] + (3*D) < ans[n-3] and n-3 > 0:
                ans[n-3] = ans[n] + (3*D) 
                if n-3 not in now:
                    q.append(n-3)
                    now.add(n-3)
            elif n-3 > 0:
                ans[n-3] = ans[n] + (3*D) 
                if n-3 not in now:
                    q.append(n-3)
                    now.add(n-3)

            if ans[n+3] in ans and ans[n] + (3*D) < ans[n+3]:
                ans[n+3] = ans[n] + (3*D) 
                if n+3 not in now:
                    q.append(n+3)
                    now.add(n+3)
            else:
                ans[n+3] = ans[n] + (3*D) 
                if n+3 not in now:
                    q.append(n+3)
                    now.add(n+3)
            """

    print(ans[N])


T = int(readline())
for t in range(T):
    N , A , B , C ,D = map(int,readline().split())
    solve()

Submission status: Wrong Answer

Solution code:
t = int(input())
inp=[]
for i in range(int(t)):

  
    inp.append(input().split(" "))
    n = int(inp[i][0])
    a = int(inp[i][1])
    b = int(inp[i][2])
    c = int(inp[i][3])
    d = int(inp[i][4])
    ans = d
    l = 0
    n_try = n

    while True:
        l = l + 1
        n_try = n_try + l
        ans += d
        while n_try % 2 == 0:
            n_try = int(n_try / 2)
            ans += a
        while n_try % 3 == 0:
            n_try = int(n_try / 3)
            ans += b
        while n_try % 5 == 0:
            n_try = int(n_try / 5)
            ans += c
            
        if n_try == 1:
            ans_p = ans
            break
    
    l = 0
    n_try = n
    while True:
        l = l + 1
        n_try = n_try - l
        ans += d
        while n_try % 2 == 0:
            n_try = int(n_try / 2)
            ans += a
        while n_try % 3 == 0:
            n_try = int(n_try / 3)
            ans += b
        while n_try % 5 == 0:
            n_try = int(n_try / 5)
            ans += c
            
        if n_try == 1:
            ans_n = ans
            break
    
    final_ans = ans_p, ans_n
    final_ans_v = min(final_ans)
    print(final_ans_v)

Submission status: Wrong Answer

Solution code:
t=int(input())
for q in range (0,t):
    z=input()
    z0=z.split()
    n=int(z0[0])
    a=int(z0[1])
    b=int(z0[2])
    c=int(z0[3])
    d=int(z0[4])
    ai=0
    aj0=0
    bj0=0
    cj0=0
    y4=0
    while 2**ai<4*n/3:
        bi=0
        while 3**bi<4*n/3:
            ci=0
            while 5**ci<4*n/3:
                if abs((2**ai)*(3**bi)*(5**ci)-n)<2*n/3:
                    y=abs((2**ai)*(3**bi)*(5**ci)-n)
                    y1=ai*a+bi*b+ci*c+(abs((2**ai)*(3**bi)*(5**ci)-n)+1)*d
                    for i in range (0,y+1):
                        k=0
                        for l in range  (0,i+1) :  
                            for aj in range (0,ai):
                                for bj in range (0,bi):
                                    for cj in range (0,ci):
                                        k=k+(2*aj+3*bj*5*cj)
                        y2=ai*a+bi*b+ci*c+(abs((2**ai)*(3**bi)*(5**ci)+k-n)+1)*d
                        if y1>y2:
                            y1=y2
                    y3=y1
                    if y3<y4 or y4==0:
                        y4=y3
                ci=ci+1
            bi=bi+1
        ai=ai+1
    print(y4)

Submission status: Wrong Answer

Solution code:
t = int(input())
import heapq
def tr(pnt,m):
  try:
    if use[m] > pnt:
      heapq.heappush(now,[pnt,m])
      use[m] = pnt
  except:
    heapq.heappush(now,[pnt,m])
    use[m] = pnt
inf = 10**18
for _ in range(t):
  n,a,b,c,d = map(int,input().split())
  now = [[0,n],[d,n+1],[d,n-1],[2*d,n+2],[2*d,n-2]]
  use = {}
  x = min(a//d,b//(2*d),c//(4*d))
  mini = 10**18
  while True:
    sc,num = heapq.heappop(now)
    att = 0
    if num == 1:
      print(min(mini,sc+d))
      break
    if num == 2:
      tr(sc+d,1)
    if num <= x:
      mini = min(mini,sc+num*d)
    
    if num % 2 == 0:
      tr(sc+a,num//2)
    else:
      tr(sc+a+d,(num-1)//2)
      tr(sc+a+d,(num+1)//2)
    
    if num % 3 == 0:
      tr(sc+b,num//3)
    elif num % 3 == 1:
      tr(sc+b+d,(num-1)//3)
    else:
      tr(sc+b+d,(num+1)//3)
    
    if num % 5 == 0:
      tr(sc+c,num//5)
    elif num % 5 == 1:
      tr(sc+c+d,(num-1)//5)
    elif num % 5 == 2:
      tr(sc+2*c+d,(num-2)//5)
    elif num % 5 == 3:
      tr(sc+2*c+d,(num+2)//5)
    else:
      tr(sc+c+d,(num+1)//5)