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:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def _sub(n,A,B,C,D,a,b,c, cost=0):
    v = n
    total = 2**a * 3**b * 5**c
    if total > v:
        return (total-v)*D + a*A + b*B + c*C + cost
    if v==1:
        return a*A + b*B + c*C + cost
    while True:
        if a==0 and b==0 and c==0:
            return D*(v-1)+cost
        
        if a>0 and v%2==0:
            cost += A
            v = v//2
            a -= 1
        elif b>0 and v%3==0:
            cost += B
            v = v//3
            b -= 1
        elif c>0 and v%5==0:
            cost += C
            v = v//5
            c -= 1
        else:
            best = 10**30
            if c>0:
                if True:
#                 if v%5<=2:
                    m = _sub(v//5,A,B,C,D,a,b,c-1, cost=cost+D*(v%5)+C)
                    best = min(m, best)
                else:
                    m = _sub(v//5+1,A,B,C,D,a,b,c-1, cost=cost+D*(5-(v%5))+C)
                    best = min(m, best)
            elif b>0:
                if True:
#                 if v%3==1:
                    m = _sub((v-1)//3,A,B,C,D,a,b-1,c, cost=cost+D+B)
                    best = min(m, best)
                else:
                    m = _sub((v+1)//3,A,B,C,D,a,b-1,c, cost=cost+D+B)
                    best = min(m, best)
            
            elif a>0:
                m = _sub((v-1)//2,A,B,C,D,a-1,b,c, cost=cost+D+A)
                best = min(m, best)
            
            return best
    
def sub(n,A,B,C,D):
    q = [(0,0,0)]
    allq = set()
    while q:
        u = q.pop()
        if 2**u[0]*3**u[1]*5**u[2]>=n:
            continue
        for item in [(u[0]+1, u[1], u[2]), (u[0], u[1]+1, u[2]), (u[0], u[1], u[2]+1)]:
            if item not in allq:
                q.append(item)
                allq.add(item)
    best = 10**30
    for a, b, c in allq:
        best = min(best, _sub(n,A,B,C,D,a,b,c))
    print(D+best)

t = int(input())
for i in range(t):
    n, A,B,C,D = map(int, input().split())
    sub(n,A,B,C,D)

Submission status: Wrong Answer

Solution code:

# A x2, B 3x, C x5, D +-1
# 1 < N

T = int(input())
for i in range(T):
    N, A, B, C, D = map(int,input().split(" "))
    dp = [[0 for j in range(2)] for i in range(N*100)]
    dp[0][0] = 1
    dp[0][1] = D
    for n in range(N):
        if dp[n][0] * 5 <= N:
            dp[n+1][0] = dp[n][0] * 5
            dp[n+1][1] = dp[n][1] + C
        if dp[n][0] * 3 <= N:
            dp[n+1][0] = max(dp[n][0] * 3, dp[n+1][0])
            if dp[n+1][0] == dp[n][0]*3:
                dp[n+1][1] = min(dp[n][1] + B, dp[n+1][1])
        if dp[n][0] * 2 <= N:
            dp[n+1][0] = max(dp[n][0] * 2, dp[n+1][0])
            if dp[n+1][0] == dp[n][0]*2:
                dp[n+1][1] = min(dp[n][1] + A, dp[n+1][1])
        if dp[n][0] + 1 <= N:
            dp[n+1][0] = max(dp[n][0] + 1, dp[n+1][0])
            if dp[n+1][0] == dp[n][0]+1:
                dp[n+1][1] = min(dp[n][1] + D, dp[n+1][1])

        if dp[n][0] > N:
            dp[n+1][0] = dp[n][0] -1
            dp[n+1][1] = dp[n][1] + D

    print(dp[N][1])
    break

Submission status: Wrong Answer

Solution code:
import numpy as np

def decomposition_x(n):
    t = [0] * 6
    while n > 0:
        if n % 2 == 0:
            n /= 2
            t[2] += 1
        elif n % 3 == 0:
            n /= 3
            t[3] += 1
        elif n % 5 == 0:
            n /= 5
            t[5] += 1
        else:
            n -= 1
            t[1] += 1

    return t

def calc(n,a,b,c,d):
    count = decomposition_x(n)

    p = 0
    #print(c2,c3,c5)
    p += a * count[2]
    p += b * count[3]
    p += c * count[5]
    p += d * count[1]
    #print(p)
    return p

T = int(input())

N = np.zeros((T),dtype=np.int64)
A = np.zeros((T),dtype=np.int64)
B = np.zeros((T),dtype=np.int64)
C = np.zeros((T),dtype=np.int64)
D = np.zeros((T),dtype=np.int64)

for t in range(T):
    n, a, b, c, d = map(int, input().split())
    N[t] = n
    A[t] = a
    B[t] = b
    C[t] = c
    D[t] = d

for t in range(T):
    #print(t)
    #p = [0] * (n+2)
    #print(t,N[t],A[t],B[t],C[t],D[t])

    p0 = calc(N[t]-1,A[t],B[t],C[t],D[t]) + D[t]

    p1 = calc(N[t],A[t],B[t],C[t],D[t])

    p2 = calc(N[t]+1,A[t],B[t],C[t],D[t]) + D[t]

    #print(p0,p1,p2)
    print(min(min(p0, p1),p2 ))

Submission status: Wrong Answer

Solution code:
t = int(input())    
for _ in range(t):
    n,a,b,c,d = map(int, input().split()) 
    s = [0 for i in range(n*5+1)]
    s[1] = d
    s[2] = min(2*d,a+d)
    s[3] = min(3*d, b+d, a+2*d)
    s[4] = min(4*d,2*a+d,a+2*d,b+2*d, c+2*d)
    s[5] = min(5*d,a+3*d, c+2*d, 2*a+2*d,b+3*d, a+b+2*d)
    for i in range(6,n*5+1):
      temp = [s[i-1]+d]
      if i%2 == 0:
        temp.append(s[i//2]+a)
      if i%3 == 0:
        temp.append(s[i//3]+b)
      if i%5 == 0:
        temp.append(s[i//5]+c) 
      if (i+1)%2 == 0:
        temp.append(s[(i+1)//2]+a+d)
      if (i+1)%3 == 0:
        temp.append(s[(i+1)//3]+b+d)
      if (i+1)%5 == 0:
        temp.append(s[(i+1)//5]+c+d) 
      if (i-1)%2 == 0:
        temp.append(s[(i-1)//2]+a+d)
      if (i-1)%3 == 0:
        temp.append(s[(i-1)//3]+b+d)
      if (i-1)%5 == 0:
        temp.append(s[(i-1)//5]+c+d) 
      s[i] = min(temp)
    
    print(s[n])

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def _sub(n,A,B,C,D,a,b,c, cost=0):
    v = n
    total = 2**a * 3**b * 5**c
    if total > v:
        return (total-v)*D + a*A + b*B + c*C + cost
    if v==1:
        return a*A + b*B + c*C + cost
    while True:
        if a==0 and b==0 and c==0:
            return D*(v-1)+cost
        
        if a>0 and v%2==0:
            cost += A
            v = v//2
            a -= 1
        elif b>0 and v%3==0:
            cost += B
            v = v//3
            b -= 1
        elif c>0 and v%5==0:
            cost += C
            v = v//5
            c -= 1
        else:
            best = 10**30
            if c>0:
                if v%5<=2:
                    m = _sub(v//5,A,B,C,D,a,b,c-1, cost=cost+D*(v%5)+C)
                    best = min(m, best)
                else:
                    m = _sub(v//5+1,A,B,C,D,a,b,c-1, cost=cost+D*(5-(v%5))+C)
                    best = min(m, best)
            elif b>0:
                if v%3==1:
                    m = _sub((v-1)//3,A,B,C,D,a,b-1,c, cost=cost+D+B)
                    best = min(m, best)
                else:
                    m = _sub((v+1)//3,A,B,C,D,a,b-1,c, cost=cost+D+B)
                    best = min(m, best)
            
            elif a>0:
                m = _sub((v-1)//2,A,B,C,D,a-1,b,c, cost=cost+D+A)
                best = min(m, best)
            
            return best
    
def sub(n,A,B,C,D):
    q = [(0,0,0)]
    allq = set()
    while q:
        u = q.pop()
        if 2**u[0]*3**u[1]*5**u[2]>=n:
            continue
        for item in [(u[0]+1, u[1], u[2]), (u[0], u[1]+1, u[2]), (u[0], u[1], u[2]+1)]:
            if item not in allq:
                q.append(item)
                allq.add(item)
    best = 10**30
    for a, b, c in allq:
        best = min(best, _sub(n,A,B,C,D,a,b,c))
    print(D+best)

t = int(input())
for i in range(t):
    n, A,B,C,D = map(int, input().split())
    sub(n,A,B,C,D)

Submission status: Wrong Answer

Solution code:
t=int(input())
for _ in range(t):
    n,a,b,c,d=map(int,input().split())
    num=1
    l=[]
    cost=d
    coscosmin=min(a,b/2,c/4)
    k1=coscosmin//d
    if n<=k1+1:
        print(n*d)
    else:
        num=k1+1
        if coscosmin==a:
            while num<n/5:
                num*=2
                cost+=a
        elif coscosmin==b/2:
            while num<n/5:
                num*=3
                cost+=b
        else:
            while num<n/5:
                num*=5
                cost+=c
       
        cost+=min((n-num)*d,a+abs(n-2*num)*d,2*a+abs(n-4*num)*d,b+abs(n-3*num)*d,c+abs(n-5*num)*d,a+b+(6*num-n)*d)
        print(int(cost))

Submission status: Wrong Answer

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):
				ans = (2**i) * (3**j) * (5**k)
				cost = (a*i) + (b*j) + (c*k)
				cost += (abs(ans-n)*d)
				mn=min(mn,cost)
	print(mn+d)

Submission status: Wrong Answer

Solution code:
t=int(input())
for i in range(t):
    ans=0
    n,a,b,c,d=map(int,input().split())
    while n!=1:
        num1=(a+(n%2)*d)*15
        num2=(b-((n%3)//-3)*d)*10
        if n%5==0:
            num3=c*6
        elif n%5==1 or n%5==4:
            num3=(c+d)*6
        else:
            num3=(c+2*d)*6
        num4=min(num1,num2,num3)
        if num1==num4:
            ans+=num1//15
            n//2
        elif num2==num4:
            ans+=num2//10
            n=(n+1)//3
        else:
            ans+=num3//6
            n=(n+2)//5
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
    
def tempmin(cos, waru2, waru3, waru5, hiku1):
    count = [0, 0, 0, 0]
    start = cos
    while(start != 0):
        if start % 2 == 0:
            start = start // 2
            count[0] += waru2
        else:
            start -= 1
            count[0] += hiku1
    start = cos
    while(start != 0):
        if start % 3 == 0:
            start = start // 3
            count[1] += waru3
        else:
            start -= 1
            count[1] += hiku1
    start = cos
    while(start != 0):
        if start % 5 == 0:
            start = start // 5
            count[2] += waru5
        else:
            start -= 1
            count[2] += hiku1
    count[3] = cos * hiku1
    return min(count)
n = (int)(input())
a=[list(map(int, input().split(" "))) for i in range(n)]
 
for i in range(n):
    first = True
    queue = deque([[a[i][0], 0]])
    mini = tempmin(a[i][0], a[i][1], a[i][2], a[i][3], a[i][4])
    passed = [a[i][0]]
    while(len(queue) > 0):
        node = queue.popleft()
        if node[1] > mini:
            continue
        if node[0] == 0:
            if node[1] < mini and first:
                mini = node[1]
                first = False
            continue
        if node[0] not in passed:
            if node[0] % 5 == 0 and node[1] + a[i][3]< mini:
                queue.append([node[0] // 5, node[1] + a[i][3]])
                passed.append(node[0] // 5)
            if node[0] % 3 == 0 and node[1] + a[i][2]< mini:
                queue.append([node[0] // 3, node[1] + a[i][2]])
                passed.append(node[0] // 3)
            if node[0] % 2 == 0 and node[1] + a[i][1]< mini:
                queue.append([node[0] // 2, node[1] + a[i][1]])
                passed.append(node[0] // 2)
            if node[1] + a[i][4] < mini:
                queue.append([node[0] + 1, node[1] + a[i][4]])
                queue.append([node[0] - 1, node[1] + a[i][4]])
                passed.append(node[0] + 1)
                passed.append(node[0] - 1)
    print(mini)

Submission status: Wrong Answer

Solution code:
t=int(input())
for _ in range(t):
    n,a,b,c,d=map(int,input().split())
    num=1
    l=[]
    cost=d
    coscosmin=min(a,b/2,c/4)
    k1=coscosmin//d
    if n<=k1+1:
        print(n*d)
    else:
        num=k1+1
        if coscosmin==a:
            while num<n/5:
                num*=2
                cost+=a
                print(cost,num)
        elif coscosmin==b/2:
            while num<n/5:
                num*=3
                cost+=b
                print(cost,num)
        else:
            while num<n/5:
                num*=5
                cost+=c
                print(num,cost)
       
        cost+=min((n-num)*d,a+abs(n-2*num)*d,2*a+abs(n-4*num)*d,b+abs(n-3*num)*d,c+abs(n-5*num)*d,a+b+(6*num-n)*d)
        print(int(cost))

Submission status: Wrong Answer

Solution code:
t = int(input())


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

Submission status: Wrong Answer

Solution code:
def dp(n):
    if n==0:return 0
    if n==1:return D
    if n==2:
        return min(dp(1)+D,dp(1)+A)
    if n in memo:
        return memo[n]
    if n%2==0:
        memo[n] = dp(n//2)+A
    else:
        memo[n] = min(dp((n+1)//2),dp((n-1)//2))+A+D
    if n%3==0:
        memo[n] = min(memo[n],dp(n//3)+B)
    elif n%3==1:
        memo[n] = min(memo[n],dp((n-1)//3)+B+D,dp((n+2)//3)+B+2*D)
    elif n%3==2:
        memo[n] = min(memo[n],dp((n+1)//3)+B+D,dp((n-2)//3)+B+2*D)
    if n%5==0:
        memo[n] = min(memo[n],dp(n//5)+C)
    elif n%5==1:
        memo[n] = min(memo[n],dp((n-1)//5)+C+D,dp((n+4)//5)+C+4*D)
    elif n%5==2:
        memo[n] = min(memo[n],dp((n-2)//5)+C+2*D,dp((n+3)//5)+C+3*D)
    elif n%5==3:
        memo[n] = min(memo[n],dp((n+2)//5)+C+2*D,dp((n-3)//5)+C+3*D)
    elif n%5==4:
        memo[n] = min(memo[n],dp((n+1)//5)+C+D,dp((n-4)//5)+C+4*D)
    return memo[n]
T = int(input())
for _ in range(T):
    memo = {}
    N,A,B,C,D = map(int,input().split())
    print(dp(N))

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, end = "")
				# コインの枚数
				temp_val = result[0] * a + result[1] * b + result[2] * c
				# 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("result = ", end = "")
	print(min_val)

Submission status: Wrong Answer

Solution code:
import sys

a = 0
b = 0
c = 0
d = 0
pw = dict()

def minCost(n):
	if n == 1:
		return d
	if n == 2:
		return d + a
	if n == 3:
		return d + b
	if n == 5:
		return d + c

	if n in pw:
		return pw[n]
	else:
		ns = dict()
		ns[n - (n % 2)] = 1
		ns[n + (2 - (n % 2))] = 1
		ns[n - (n % 3)] = 1
		ns[n + (3 - (n % 3))] = 1
		ns[n - (n % 5)] = 1
		ns[n + (5 - (n % 5))] = 1
		_min = n * d
		for key in ns:
			if key > 0:
				if key % 2 == 0:
					_min = min(_min, a + int(minCost(key / 2)) + d * abs(n - key))
				if key % 3 == 0:
					_min = min(_min, b + int(minCost(key / 3)) + d * abs(n - key))
				if key % 5 == 0:
					_min = min(_min, c + int(minCost(key / 5)) + d * abs(n - key))
		pw[n] = _min
		return pw[n]

t = int(sys.stdin.readline())
for i in range(0, t):
	line = sys.stdin.readline().split()
	n = int(line[0])
	a = int(line[1])
	b = int(line[2])
	c = int(line[3])
	d = int(line[4])
	pw = dict()
	print(int(minCost(n)))

Submission status: Wrong Answer

Solution code:
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())
   # N,A,B,C,D=10**18-2,10**9+1,10**9+100,10**9+10000,10**9+1000000
    d={}
    u(N,0)
    a=10**30
    d[N]=0
    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:
s = [input() for i in range(1)]
s0 = int(s[0])
t = [input() for j in range(s0)]
li = {}
for k in range(s0):
    li[k] = list(map(int, t[k].split()))
    x = 1
    for a in range(li[k][0]):
        x = x * 5
        if x > li[k][0]:
            x = x / 5
            break
    for b in range(li[k][0]):
        x = x * 3
        if x > li[k][0]:
            x = x / 3
            break
    for c in range(li[k][0]):
        x = x * 2
        if x > li[k][0]:
            x1 = x - li[k][0]
            x2 = li[k][0] - (x / 2)
            if x1 > x2:
                n1 = li[k][1]*c + li[k][2]*b + li[k][3]*a + li[k][4]*(x2)+li[k][4]
                break
            if x2 > x1:
                n1 = li[k][1]*(c+1) + li[k][2]*b + li[k][3]*a + li[k][4]*(x1)+li[k][4]
                break
    print(n1)

Submission status: Wrong Answer

Solution code:
N = int(input())
T = str(input())
import numpy as np
a = [i for i in range(3**N)]
b = [0 for i in range(3**N)]
for i in range(N):
    n = [3**i for _ in range(3**N)]
    m = ([0]*int(3**i) + [2]*int(3**i) + [1]*int(3**i))*int(3**(N-(i+1)))
    b = [o + p*q for o,p,q in zip(b,n,m)]
b = b
for t in T:
  if t == 'S':
    a = [b[ai] for ai in a]
  else:
    a = [(ai + 1)%3**N for ai in a]
ans = ''
for ai in a:
    ans += 'ai' + ' '
print(ans)

Submission status: Wrong Answer

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

def coin(n,a,b,c,d):
    ans=[]
    hako=[[a,2],[b,3],[c,5]]
    kari=d
    genzai=1
    jikkou=1
    cospa=1/d
    cost=0
    while genzai<=n:
        for i in range(3):
            cospa=max(cospa,genzai*hako[i][1]/hako[i][0])
            if cospa==genzai*hako[i][1]/hako[i][0]:
                jikkou=hako[i][1]
                cost=hako[i][0]
        else:
            if cospa==1/d:
                cost+=d
                genzai+=1
            else:
                genzai*=jikkou
                kari+=cost
    ans.append(cost+abs(n-genzai)*d)


    print(min(ans))
for i in case:
    coin(*i)

Submission status: Wrong Answer

Solution code:
import math
import os
import sys


def input():
    return sys.stdin.readline()[:-1]


def min_coin(N, A, B, C, D):
    max_a = math.ceil(math.log(N, 2))
    max_b = math.ceil(math.log(N, 3))
    max_c = math.ceil(math.log(N, 5))
    answers = []

    for a in range(0, max_a+3):
        for b in range(0, max_b+3):
            for c in range(0, max_c+3):
                answers.append([a, b, c])

    points = [None]*len(answers)
    for i, answer in enumerate(answers):
        points[i] = D + A*answer[0] + B*answer[1] + C*answer[2] + \
                    D*abs(N-(2**answer[0] * 3**answer[1] * 5**answer[2]))
    return min(points)


def resolve():
    T = int(input())
    VALUES = [list(map(int, input().split())) for i in range(T)]
    for VALUE in VALUES:
        N, A, B, C, D = VALUE
        print(min_coin(N, A, B, C, D))

resolve()

Submission status: Wrong Answer

Solution code:
t = int(input())
import sys
sys.setrecursionlimit(10**6)

seen = set()
dp = dict()
def Find(value, isFirst = False):
    seen.add(value)

    if value == 1:
        return d
    elif value == 2:
        return min(Find(1) + d, Find(1) + a)
    elif value == 3:
        return min(Find(2) + d, Find(1) + b)
    elif value == 4:
        return min(Find(3) + d, Find(2) + a)
    elif value == 5:
        return min(Find(4) + d, Find(1) + c)
    elif value == 6:
        return min(Find(5) + d, Find(2) + b, Find(3) + a)
    else:
        if value in dp:
            return dp[value]

        candidate = []

        if isFirst:
            candidate.append(Find(value + 1) + d)
        if value % 2 == 0:
            candidate.append(Find(value//2) + a)
        if value % 3 == 0:
            candidate.append(Find(value//3) + b)
        if value % 5 == 0:
            candidate.append(Find(value//5) + c)
        if value % 6 == 0:
            candidate.append(Find(value // 2) + a)
            candidate.append(Find(value // 3) + b)
            candidate.append(value*d - 2)
        else:
            candidate.append(Find(value - 1) + d)


        if len(candidate) == 0:
            raise 1
        min1 = min(candidate)
        dp[value] = min1
        return min1

for _ in range(t):
    n, a, b, c, d =map(int, input().split())
    seen.clear()
    dp.clear()
    v = Find(n, True)
    print(v)

Submission status: Wrong Answer

Solution code:
s = [input() for i in range(1)]
s0 = int(s[0])
t = [input() for j in range(s0)]
li = {}
for k in range(s0):
    li[k] = list(map(int, t[k].split()))
    x = 1
    for a in range(li[k][0]):
        x = x * 5
        if x > li[k][0]:
            x = x / 5
            break
    for b in range(li[k][0]):
        x = x * 3
        if x > li[k][0]:
            x = x / 3
            break
    for c in range(li[k][0]):
        x = x * 2
        if x > li[k][0]:
            x1 = x - li[k][0]
            x2 = li[k][0] - (x / 2)
            if x1 > x2:
                n1 = li[k][1]*c + li[k][2]*b + li[k][3]*a + li[k][4]*(x2)+li[k][4]
                break
            if x2 > x1:
                n1 = li[k][1]*(c+1) + li[k][2]*b + li[k][3]*a + li[k][4]*(x1)+li[k][4]
                break
    print("n1:",n1)

Submission status: Wrong Answer

Solution code:
T = int(input())
N,A,B,C,D = map(int, input().split())

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
print("a")

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



def _sub(n,A,B,C,D,a,b,c, cost=0):
    v = n
    total = 2**a * 3**b * 5**c
    if total > v:
        return (total-v)*D + a*A + b*B + c*C + cost
    if v==1:
        return a*A + b*B + c*C + cost
    while True:
        if a==0 and b==0 and c==0:
            return D*(v-1)+cost
        
        if a>0 and v%2==0:
            cost += A
            v = v//2
            a -= 1
        elif b>0 and v%3==0:
            cost += B
            v = v//3
            b -= 1
        elif c>0 and v%5==0:
            cost += C
            v = v//5
            c -= 1
        else:
            best = 10**30
            if a>0:
                m = _sub((v-1)//2,A,B,C,D,a-1,b,c, cost=cost+D+A)
                best = min(m, best)
            elif b>0:
                if v%3==1:
                    m = _sub((v-1)//3,A,B,C,D,a,b-1,c, cost=cost+D+B)
                    best = min(m, best)
                else:
                    m = _sub((v+1)//3,A,B,C,D,a,b-1,c, cost=cost+D+B)
                    best = min(m, best)
            elif c>0:
                if v%5<=2:
                    m = _sub(v//5,A,B,C,D,a,b,c-1, cost=cost+D*(v%5)+C)
                    best = min(m, best)
                else:
                    m = _sub(v//5+1,A,B,C,D,a,b,c-1, cost=cost+D*(5-(v%5))+C)
                    best = min(m, best)
            return best
    
def sub(n,A,B,C,D):
    q = [(0,0,0)]
    allq = set()
    while q:
        u = q.pop()
        if 2**u[0]*3**u[1]*5**u[2]>=n:
            continue
        for item in [(u[0]+1, u[1], u[2]), (u[0], u[1]+1, u[2]), (u[0], u[1], u[2]+1)]:
            if item not in allq:
                q.append(item)
                allq.add(item)
    best = 10**30
    for a, b, c in allq:
        best = min(best, _sub(n,A,B,C,D,a,b,c))
    print(D+best)

t = int(input())
for i in range(t):
    n, A,B,C,D = map(int, input().split())
    sub(n,A,B,C,D)

Submission status: Wrong Answer

Solution code:
input()

Submission status: Wrong Answer

Solution code:
import math

def calc(n,a,b,c,d):
    # 手持ちの数
    x = 1
    # 必要なコイン
    coin = n*d

    # ケース１　必要なコインが(n*d)枚
    # ケース２　掛け算の組み合わせ
    # ケース3　掛け算と引き算の組み合わせ

    return coin



t = int(input())
ans = [0]*t

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

# 出力
for j in range(t):
    print(ans[j])

Submission status: Wrong Answer

Solution code:
x=1
y=3
while x < y:
  x=x+1

Submission status: Wrong Answer

Solution code:
T = int(input())
A,ABCD = [],[]#[12,6],[[7,5,3,1,8],[7,5]]

N = [4 for _ in range(T+1)]#[5,2]
while True:
    try:
        listA=list(map(int,input().split()))
        A.append(listA[0])
        ABCD.append(listA[1:5])    
    except:
        break

INF = 10**29

# dp table
dp = [[ INF for _ in range(max(A)+1)] for _ in range(max(N)+1)]
#print(dp)
dp[0][0] = 0

for k in range(T):
    for i in range(N[k]):
        for j in range(A[k]):#12,6
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if(j >= ABCD[k][i]):
                dp[i+1][j] = min(dp[i+1][j], dp[i][j-ABCD[k][i]] + 1)
            
    if (dp[N[k]][A[k]] < INF):
        print(dp[N[k]][A[k]])
    else:
        print(dp[N[k]][A[k]])
    dp = [[ INF for _ in range(max(A)+1)] for _ in range(max(N)+1)]
    dp[0][0] = 0
#print(N)

Submission status: Wrong Answer

Solution code:
def sort(list):
    j = 1
    k = 1
    while j < len(list):
        while j > 0:
            if list[j] < list[j - 1]:
                x = list[j]
                list[j] = list[j - 1]
                list[j - 1] = x
            j -= 1
        k += 1
        j = k

T = int(input())
number = list()
for i in range(T):
    N, A, B, C, D = map(int, input().split())
    for i in range(T):
        num = 0
        while N != 0:
            alp = [A, B, C, D]
            sort(alp)
            for m in range(4):    
                if alp[m] == A and N % 2 == 0:
                    N = N / 2
                    num += A
                elif alp[m] == B and N % 3 == 0:
                    N = N / 3
                    num += B
                elif alp[m] == C and N % 5 == 0:
                    N = N / 5
                    num += C
                elif alp[m] == D and N > 0:
                    N = N - 1
                    num += D
        number.append(num)
for n in range(T + 1):
    if n % 2 == 0:
        print(number[n])

Submission status: Wrong Answer

Solution code:
T = int(input())
grid = []
for i in range(T):
    ls = list(map(int, input().split()))
    grid.append(ls)


anls = []
for iteml in grid:
    ans = float('inf')
    n = iteml[0]
    a = iteml[1]
    b = iteml[2]
    c = iteml[3]
    d = iteml[4]
    for ai in range(61):
        for bi in range(61-ai):
            for ci in range(61-ai-bi):
                num = (2**ai)*(3**bi)*(5**ci)
                pulus = abs(num - n)
                cost = a*ai + b*bi + c*ci + pulus*d + d
                ans = min(cost,ans)
    anls.append(ans)
for item2 in anls:
    print(item2)

Submission status: Wrong Answer

Solution code:
from math import ceil
T = int(input())
NABCD = [list(map(int,input().split())) for _ in range(T)]
for i in range(T):
    N,A,B,C,D = NABCD[i]
    memo = {0:0,1:D}
    def f(n):
        if n in memo:
            return memo[n]
        else:
            res = D*n
            r2 = n%2
            r3 = n%3
            r5 = n%5
            res = min(res,f(n//2)+A+r2*D,f(n//3)+B+r3*D,f(n//5)+C+r5*D)
            if n != 2 and n%2==0:
                res = min(res,f(n//2-1)+A+2*D)
            if n != 3 and n%3==0:
                res = min(res,f(n//3-1)+B+3*D)
            if n != 5 and n%5==0:
                res = min(res,f(n//5-1)+C+5*D)
            res = min(res,f(ceil(n/2))+A+(2-r2)*D,f(ceil(n/3))+B+(3-r3)*D,f(ceil(n/5))+C+(5-r5)*D)
            if n < 100:
                res = min(res,f(n-1)+D)
            memo[n] = res
            return res
    print(f(N))

Submission status: Wrong Answer

Solution code:
t = int(input())
import sys
sys.setrecursionlimit(10**6)

seen = set()
dp = dict()
def Find(value, isFirst = False):
    seen.add(value)

    if value == 1:
        return d
    elif value == 2:
        return min(Find(1) + d, Find(1) + a)
    elif value == 3:
        return min(Find(2) + d, Find(1) + b)
    elif value == 4:
        return min(Find(3) + d, Find(2) + a)
    elif value == 5:
        return min(Find(4) + d, Find(1) + c)
    elif value == 6:
        return min(Find(5) + d, Find(2) + b, Find(3) + a)
    else:
        if value in dp:
            return dp[value]

        candidate = []

        if isFirst:
            candidate.append(Find(value + 1) + d)
        if value % 2 == 0:
            candidate.append(Find(value//2) + a)
        if value % 3 == 0:
            candidate.append(Find(value//3) + b)
        if value % 5 == 0:
            candidate.append(Find(value//5) + c)
        if value % 6 == 0:
            candidate.append(Find(value // 2) + a)
            candidate.append(Find(value // 3) + b)
            candidate.append((value-2)*d)
        else:
            candidate.append(Find(value - 1) + d)


        if len(candidate) == 0:
            raise 1
        min1 = min(candidate)
        dp[value] = min1
        return min1

for _ in range(t):
    n, a, b, c, d =map(int, input().split())
    seen.clear()
    dp.clear()
    v = Find(n, True)
    print(v)