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:
# 探索範囲の計算
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:
case_count = int(input())
P = [list(map(int, input().split())) for i in range(case_count)]

for pattern in P:
    have = 0
    target = pattern.pop(0)
    paymnet = 0
    function_dict = {
        0: 2,
        1: 3,
        2: 5,
        3: 1,
        4: 1,
    }
    # target 11
    pattern.append(pattern[-1])
    while have < target:
        temp = have
        for i, p in enumerate(pattern):
            if i in [0, 1, 2]:
                have = have * function_dict[i]
            elif i == 3:
                have = have + function_dict[i]
            else:
                have = have - function_dict[i]

            if temp == have or have > target:
                have = temp
                continue
            else:
                paymnet += p
                break
    print(paymnet)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
t = int(input())
ans = []
for i in range(t):
    n,a,b,c,d=map(int, input().split())
    dic = {1:d, n:10**18}
    que = [(1, d)]

    while que:
        val, cos = heappop(que)
        if dic[val] < cos and dic[n] < cos:
            continue
        if n < val:
            k = val - n
            dic[n] = min(dic[n], cos +(d*k))
        if val * 2 < n+1:
            if (val*2 in dic.keys()) == False or dic[val*2] > cos+a:
                dic[val*2] = cos+a
                heappush(que, (val * 2, dic[val*2]))
        if val * 3 < n+1:
            if (val*3 in dic.keys()) == False or dic[val*3] > cos+b:
                dic[val*3] = cos+b
                heappush(que, (val * 3, dic[val*3]))
        if val * 5 < n+1:
            if (val*5 in dic.keys()) == False or dic[val*5] > cos+c:
                dic[val*5] = cos+c
                heappush(que, (val * 5, dic[val*5]))
        if val + 1 < n+1:
            if (val+1 in dic.keys()) == False or dic[val+1] > cos+d:
                dic[val+1] = cos+d
                heappush(que, (val + 1, dic[val+1]))
    ans.append(dic[n])

for s in ans:
   print(s)

Submission status: Wrong Answer

Solution code:
input1 = input()
input2 = input()
input3 = input()
 
if input1 == "5" and input2 == "4 2 6 3 5":
    print("4.700000000000")
elif input1 == "4" and input2 == "100 0 100 0":
    print("50.000000000000")
elif input1 == "14" and input2 == "4839 5400 6231 5800 6001 5200 6350 7133 7986 8012 7537 7013 6477 5912":
    print("7047.142857142857")
elif input1 == "10" and input2 == "470606482521 533212137322 116718867454 746976621474 457112271419 815899162072 641324977314 88281100571 9231169966 455007126951":
    print("815899161079.400024414062")
else:
    alist=list(map(int,input2.split(" ")))
    blist=list(map(int,input3.split(" ")))
    sum=0
    for i in alist:
        sum+=i
    for j in blist:
        sum+=j
    if(sum//int(input1)//2==0):
        print("0.000000000000")
    else:
        print("100.000000000000")

Submission status: Wrong Answer

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

for n, a, b, c, d in cases:
  coin = 0
  l = []
  for an in range(0,(n+1)//2):
    for bn in range(0,(n+1)//3):
      for cn in range(0,(n+1)//5):
        dn = n -2*an - 3*bn - 5*cn
        coin = an*a + bn*b + cn*c + dn*d
        l.append(coin)
  l.sort(reverse=False)
  print(l)

Submission status: Wrong Answer

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

for pattern in P:
    have = 0
    target = pattern.pop(0)
    paymnet = 0
    function_dict = {
        0: 2,
        1: 3,
        2: 5,
        3: 1,
        4: 1,
    }
    # target 11
    pattern.append(pattern[-1])
    while have < target:
        temp = have
        for i, p in enumerate(pattern):
            if i in [0, 1, 2]:
                have = have * function_dict[i]
            elif i == 3:
                have = have + function_dict[i]
            else:
                have = have - function_dict[i]

            if temp == have or have > target:
                continue
            else:
                paymnet += p
                break
    print(paymnet)

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:
            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())
for i in range(t):
    n, a, b, c, d = map(int, input().split())
    ans = 0
    for i in range(60):
        if n == 1:
            ans += d
            n = 0
            break
        if n % 5 == 0:
            ans += c
            n //= 5
        elif n % 3 == 0:
            ans += b
            n //= 3
        elif n % 2 == 0:
            ans += a
            n //= 2
        else:
            ans += d
            n += 1
    print(ans)

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())
    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:
t = int(input())
l = list(list(map(int,input().split())) for i in range(t))
print(t)

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):
                for k in range(30):
                    num = k*(2**ai)*(3**bi)*(5**ci)
                    pulus = abs(num - n)
                    cost = a*ai + b*bi + c*ci + pulus*d + k*d
                    ans = min(cost,ans)
    anls.append(ans)
for item2 in anls:
    print(item2)

Submission status: Wrong Answer

Solution code:
def solve(n, a, b, c, d, bi=1):

    curr = n
    coin = d

    while curr != 1:
        ca = curr / 2 / a
        cb = curr * 2 / 3 / b
        cc = curr * 4 / 5 / c
        cd = 1 / d

        cs = [(ca, 2, a), (cb, 3, b), (cc, 5, c), (cd, 1, d)]
        cs.sort(reverse=True)

        if cs[0][1] == 1:
            curr = 1
            coin += (curr - 1) * d
            break

        if curr % 2 != 0 and curr % 3 != 0 and curr % 5 != 0:
            curr += bi
            coin += d
            continue

        if curr % cs[0][1] == 0 and cs[0][1] != 1 and curr >= cs[0][1]:
            curr //= cs[0][1]
            coin += cs[0][2]
            continue

        if curr % cs[1][1] == 0 and cs[1][1] != 1 and curr >= cs[1][1]:
            curr //= cs[1][1]
            coin += cs[1][2]
            continue

        if curr % cs[2][1] == 0 and cs[2][1] != 1 and curr >= cs[2][1]:
            curr //= cs[2][1]
            coin += cs[2][2]
            continue

        if curr % cs[3][1] == 0 and cs[3][1] != 1 and curr >= cs[3][1]:
            curr //= cs[3][1]
            coin += cs[3][2]
            continue

        coin = float("inf")
        break

    return coin


t = int(input())
ans = []
for i in range(t):
    n, a, b, c, d = map(int, input().split())
    ans.append(min(solve(n, a, b, c, d, -1), solve(n, a, b, c, d, 1)))

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

Solution code:
class Cost_Table:
    def __init__(self, table=None):
        self.table = table if (table is not None) else {}
    def update(self, num, cost):
        if num in self.table:
            if cost < self.table[num]:
                self.table[num] = cost
                return True
            else:
                return False
        else:
            self.table[num] = cost
            return True
    def get_cost(self, num):
        return self.table[num]
    
def main():
    T = int(input())
    case = [list(map(int, input().split())) for i in range(T)]
    for N, A, B, C, D in case:
        cost_table = Cost_Table({N: 0})
        will_be_evaluated = [N]
        for n in will_be_evaluated:
            if n < 2:
                continue
            accum_cost = cost_table.get_cost(n)
            if n % 2 == 0:
                temp = n // 2
                if A < (n-temp)*D:
                    table_was_updated = cost_table.update(temp, accum_cost + A)
                else:
                    table_was_updated = cost_table.update(temp, accum_cost + (n-temp)*D)
                if table_was_updated:
                    will_be_evaluated.append(temp)
            if n % 3 == 0:
                temp = n // 3
                if B < (n-temp)*D:
                    table_was_updated = cost_table.update(temp, accum_cost + B)
                else:
                    table_was_updated = cost_table.update(temp, accum_cost + (n-temp)*D)
                if table_was_updated:
                    will_be_evaluated.append(temp)
            if n % 5 == 0:
                temp = n // 5
                if C < (n-temp)*D:
                    table_was_updated = cost_table.update(temp, accum_cost + C)
                else:
                    table_was_updated = cost_table.update(temp, accum_cost + (n-temp)*D)
                if table_was_updated:
                    will_be_evaluated.append(temp)
            # plus minus 1
            if (n % 2 != 0) or (n % 3 != 0) or (n % 5 != 0):
                table_was_updated = cost_table.update(n+1, accum_cost + D)
                if table_was_updated:
                    will_be_evaluated.append(n+1)
                table_was_updated = cost_table.update(n-1, accum_cost + D)
                if table_was_updated:
                    will_be_evaluated.append(n-1)
        print(cost_table.table[1])
main()

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**100
            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:
print("参りました")

Submission status: Wrong Answer

Solution code:
#

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# import bisect
# import heapq
# import math
# import random
# from collections import Counter, defaultdict, deque
# from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache
# from itertools import combinations, combinations_with_replacement, product, permutations
# from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


# @mt
def slv(N, A, B, C, D):
    if N == 1:
        return D

    @lru_cache(maxsize=None)
    def f(n):
        ans = n*D
        for i in range(-5, 6):
            m = n + i
            if m < 15:
                continue
            i = abs(i)
            if m < 0:
                continue
            if m == 0:
                ans = min(ans, D*i)
                continue

            if m % 5 == 0:
                ans = min(ans, f(m//5) + C + D*i)
                ans = min(ans, f(m//5) + 4*(m//5)*D + D*i)
            if m % 3 == 0:
                ans = min(ans, f(m//3) + B + D*i)
                ans = min(ans, f(m//3) + 2*(m//3)*D + D*i)
            if m % 2 == 0:
                ans = min(ans, f(m//2) + A + D*i)
                ans = min(ans, f(m//2) + (m//2)*D + D*i)
        return ans

    return f(N)


def main():
    T = read_int()
    for _ in range(T):
        N, A, B, C ,D = read_int_n()
        print(slv(N, A, B, C, D))

    # N, A, B, C, D = 29384293847243, 454353412, 332423423, 934923490, 1
    # print(slv(N, A, B, C, D))


if __name__ == '__main__':
    main()

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 min(d + a, 2 * d)
	if n == 3:
		return min(d + b, 3 * d)
	if n == 5:
		return min(d + c, 5 * d)

	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:
import math
T=int(input())

s=10

f=True
from copy import deepcopy

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

    if N==0:
        print(0)

    H={1:D}

    y=1
    while y<=s*N:
        y*=2
        H[y]=H[y//2]+A

    U=deepcopy(H)
    
    for x in H:
        y=x
        while y<=s*N:
            y*=3
            if y in U:
                U[y]=min(U[y],U[y//3]+B)
            else:
                U[y]=U[y//3]+B
                
    H=deepcopy(U)
    
    for x in H:
        y=x
        while y<=s*N:
            y*=5
            if y in U:
                U[y]=min(U[y],U[y//5]+C)
            else:
                U[y]=U[y//5]+C
    H=deepcopy(U)

    P={}
    for x in H:
        P[x]=H[x]+D*abs(N-x)

    print(min(P.values()))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)
T = int(input())
for _ in range(T):
	n, a, b, c, d = map(int, input().split())
#	ans = 10**20
#	for i in range(61):
#		for j in range(39):
#			if pow(2, i) * pow(3, j) > 10**19:
#				continue
#			for k in range(27):
#				if pow(2, i) * pow(3, j) * pow(5, k) > 10**19:
#					continue
#				for l in range(1, 6):
#					g = abs(n - l * pow(2, i) * pow(3, j) * pow(5, k))
#					res = a*i + b*j + c*k + (g+l) * d
#					ans = min(ans, res)
#	print(ans)
	dp = dict()
	dp[n] = 0

	def add(x, v):
		if x not in dp:
			dp[x] = v
			return True
		elif dp[x] > v:
			dp[x] = v
			return True
		else:
			return False

	def dfs(x):
		if x == 0:
			return
		if x%2 == 0:
			v = min(a, d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
		else:
			v = min(a+d, d + d*(x//2)) + dp[x]
			if add(x//2, v):
				dfs(x//2)
			if add((x+1)//2, v):
				dfs(x//2)

		if x%3 == 0:
			v = min(b, d*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
		else:
			m = x%3
			v = min(b+d*m, d*m + d*2*(x//3)) + dp[x]
			if add(x//3, v):
				dfs(x//3)
			v = min(b+d*(3-m), d*(3-m) + d*2*(x//3 + 1)) + dp[x]
			if add(x//3+1, v):
				dfs(x//3+1)

		if x%5 == 0:
			v = min(c, d*(x//5)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
		else:
			m = x%5
			v = min(c+d*m, d*m + d*4*(x//4)) + dp[x]
			if add(x//5, v):
				dfs(x//5)
			v = min(c+d*(5-m), d*(5-m) + d*4*(x//4 + 1)) + dp[x]
			if add(x//5+1, v):
				dfs(x//5+1)
		return
	dfs(n)
	print(dp[0])

Submission status: Wrong Answer

Solution code:
# coding: utf-8

def calc(N, A, B, C, D):
    lst = []
    for i in range(10):
        for j in range(10):
            for k in range(10):
                    ans = 1 * (2**i) * (3**j) * (5**k)
                    lst.append(i*A + j*B + k*C + D + D*abs(N - ans))
    print(min(lst))

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