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
from functools import lru_cache
from bisect import bisect_left as lb, bisect_right as ub
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from math import gcd, ceil, sqrt
rd = lambda: int(sys.stdin.readline())
rds = lambda: map(int, sys.stdin.readline().split())
rdl = lambda: list(map(int, sys.stdin.readline().split()))
inf = 2 * 10 ** 18
sys.setrecursionlimit(10 ** 7)
rg = range
pr = print


T = rd()
for i in rg(T):
  n, a, b, c, d = rds()

  @lru_cache(maxsize=10 ** 7)
  def f(m):
    # print(m)
    if m == 0:
      return 0
    if m == 1:
      return d
    ret = inf
    # 2
    q, r = m // 2, m % 2
    ret = min(ret, f(q) + d * r + a)
    if r:
      ret = min(ret, f(q + 1) + d * (2 - r) + a)

    q, r = m // 3, m % 3
    ret = min(ret, f(q) + d * r + b)
    if r:
      ret = min(ret, f(q + 1) + d * (3 - r) + b)

    q, r = m // 5, m % 5
    ret = min(ret, f(q) + d * r + c)
    if r:
      ret = min(ret, f(q + 1) + d * (5 - r) + c)
    return ret

  pr(f(n))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**5)

T=int(input())

def saiki(n):
    if n==0:
        return 0
    elif n==1:
        return D
    else:
        value=min(
            D*n,
            saiki(n//2)+A+D*abs(n - n//2*2),
            saiki((n+1)//2)+A+D * abs(n - (n+4)//5*5),
            saiki(n//3)+B+D*abs(n - n//3*3),
            saiki((n+2)//3)+B+D * abs(n - (n+2)//3*3),
            saiki(n//5)+C+D*abs(n - n//5*5),
            saiki((n+4)//5)+C+D * abs(n - (n+4)//5*5)
            )
    return value

for _ in range(T):
    ans=[]
    N,A,B,C,D=map(int,input().split())
    print(saiki(N))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

def main(A):
    return 0

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8[:])')(main)
    cc.compile()

if sys.argv[-1] == 'ONLINE_JUDGE':
    cc_export()
    exit(0)
if sys.argv[-1] != 'LOCAL':
    from my_module import main

A = np.ones(10, dtype=np.int64)
ans = main(A)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect

sys.setrecursionlimit(10**6)
t=int(input())
def cost(n):
    if n in memo:
        return memo[n]
    res=min(d*n,d*(n-math.floor(n/5)*5)+c+cost(math.floor(n/5)),d*(math.ceil(n/3)*3-n)+b+cost(math.ceil(n/3)),d*(n-math.floor(n/2)*2)+a+cost(math.floor(n/2)),d*(n-math.floor(n/2)*2)+a+cost(math.floor(n/2)))
    memo[n]=res
    return res

for i in range(t):
    ans=0
    n,a,b,c,d=map(int,input().split())
    memo={0:0,1:d}
    print(cost(n))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def main():
    n, a, b, c, d = map(int, input().split())
    memo = {}
    def dfs(x):
        if x == 0:
            return 0
        elif x == 1:
            return d
        elif x in memo:
            return memo[x]
        else:
            ret = min(
                d * x,
                d * (x - x//2*2) + a + dfs(x//2),
                d * ((x+1)//2*2-x) + a + dfs((x+1)//2),
                d * (x - x//3*2) + b + dfs(x//3),
                d * ((x+2)//3*3 - x) + b + dfs((x+2)//3),
                d * (x - x//5*5) + c + dfs(x//5),
                d * ((x+4)//5*5 - x) + c + dfs((x+4)//5)
            )
            memo[x] = ret
            return ret
    print(dfs(n))

t = int(input())
for i in range(t):
    main()

Submission status: Wrong Answer

Solution code:
import heapq
T = int(input())
for _ in range(T):
    N, A, B ,C, D = map(int, input().split())
    ans = D*N
    for i in range(27):
        I = 5**i
        for j in range(39):
            J = 3**j
            for k in range(61):
                ans = min(ans, C*i + B*j + A*k + D*abs(N-I*J*2**k) + D)
    print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
T = int(input())
for _ in range(T):
    N, A, B ,C, D = map(int, input().split())
    ans = D*N
    for i in range(27):
        I = 5**i
        for j in range(39):
            J = 3**j
            if I*J > 10**20:
                break
            for k in range(61):
                if I*J > 10**20:
                    break
                ans = min(ans, C*i + B*j + A*k + D*abs(N-I*J*2**k) + D)
    print(ans)

Submission status: Wrong Answer

Solution code:
import math
T = int(input())
for t in range(T):
    N, A, B, C, D = map(int, input().split())
    memo = {}

    def dist(n):
        if n == 0:
            return 0
        elif n == 1:
            return D
        elif n in memo:
            return memo[n]

        ret = min(
            D * n,
            D * abs(n - n//5*5) + C + dist(n//5),
            D * abs(n - math.ceil(n/5)*5) + C + dist(math.ceil(n/5)),
            D * abs(n - n//3*3) + B + dist(n//3),
            D * abs(n - math.ceil(n/3)*3) + B + dist(math.ceil(n/3)),
            D * abs(n - n//2*2) + A + dist(n//2),
            D * abs(n - math.ceil(n/2)*2) + A + dist(math.ceil(n/2))
        )

        memo[n] = ret
        return ret
    print(dist(N))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
enum = enumerate
inf = 1001001002002002002

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().rstrip().split()))

def vinput(rep=1, ty=int, cvt=list):
	return cvt(ty(input().rstrip()) for _ in "*"*rep)

def gcd(a: int, b: int):
	while b: a, b = b, a%b
	return a

def lcm(a: int, b: int):
	return a * b // gcd(a, b)

def bye(res):
	sT = "No Yes".split()
	print(sT[res])
	#exit(0)

def sol(N,A,B,C,D):
	res = inf
	at,bt,ct,dt = [0,]*4
	an,bn,cn,dn = [0,]*4
	cn = N
	for c in range(32):
		bn = cn
		for b in range(42):
			an = bn
			for a in range(63):
				dt = at+bt+ct+ an
				r = a*A+b*B+c*C+dt*D
				res = min(res, r)
				if not an: break
				at += an%2
				an = an//2
			at = 0
			bt += 0<bn%3
			bn = bn//3 + (bn%3==2)
		bt = 0
		cMod5 = cn%5
		ct += min(5-cMod5, cMod5)
		cn = cn//5 + (cMod5>2)
	
	print(res)

def main():
	T, = linput()
	for _ in "*"*T:
		sol(*linput())

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
enum = enumerate
inf = 1001001002002002002

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().rstrip().split()))

def vinput(rep=1, ty=int, cvt=list):
	return cvt(ty(input().rstrip()) for _ in "*"*rep)

def gcd(a: int, b: int):
	while b: a, b = b, a%b
	return a

def lcm(a: int, b: int):
	return a * b // gcd(a, b)

def bye(res):
	sT = "No Yes".split()
	print(sT[res])
	#exit(0)

def sol(N,A,B,C,D):
	res = inf
	at,bt,ct,dt = [0,]*4
	an,bn,cn,dn = [0,]*4
	cn = N
	for c in range(30):
		bn = cn
		for b in range(42):
			an = bn
			for a in range(63):
				dt = at+bt+ct+ an
				r = a*A+b*B+c*C+dt*D
				res = min(res, r)
				#if not an: break
				at += an%2
				an = an//2
			at = 0
			bt += 0<bn%3
			bn = bn//3 + (bn%3==2)
		bt = 0
		cMod5 = cn%5
		ct += min(5-cMod5, cMod5)
		cn = cn//5 + (cMod5>2)
	
	print(res)

def main():
	T, = linput()
	for _ in "*"*T:
		sol(*linput())

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
from functools import lru_cache

@lru_cache(maxsize=None)
def solve(n, a, b, c, d):
    if n == 0:
        return 0
    if n == 1:
        return d
    res = 10**18
    res = min(res, d * n)
    res = min(res, d * (n - n // 2 * 2) + a + solve(n // 2, a, b, c, d))
    res = min(res, d * (n - n // 3 * 3) + b + solve(n // 3, a, b, c, d))
    res = min(res, d * (n - n // 5 * 5) + c + solve(n // 5, a, b, c, d))
    res = min(res, d * (n - (n + 2 - 1) // 2 * 2 + a + solve((n + 2 - 1) // 2, a, b, c, d)))
    res = min(res, d * (n - (n + 3 - 1) // 3 * 3 + b + solve((n + 3 - 1) // 3, a, b, c, d)))
    res = min(res, d * (n - (n + 5 - 1) // 5 * 5 + c + solve((n + 5 - 1) // 5, a, b, c, d)))
    return res

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

Submission status: Wrong Answer

Solution code:
20
19
26
3821859835
23441258666

Submission status: Wrong Answer

Solution code:
# 解説PDF読んで解説放送見てAC

# 逆から操作を考える（終点のNから考える）
# スカスカDP。なので配列を作らずに辞書で管理する必要がある

import math

def calc_cost(n, ans_dict):

    min_cost = n * d

    inc_2 = int(math.ceil(n / 2))
    if inc_2 not in ans_dict:
        ans_dict[inc_2] = calc_cost(inc_2, ans_dict)
    min_cost = min(min_cost, d * (inc_2 * 2 - n) + a + ans_dict[inc_2])

    dec_2 = int(math.floor(n / 2))
    if dec_2 not in ans_dict:
        ans_dict[dec_2] = calc_cost(dec_2, ans_dict)
    min_cost = min(min_cost, d * (- dec_2 * 2 + n) + a + ans_dict[dec_2])

    inc_3 = int(math.ceil(n / 3))
    if inc_3 not in ans_dict:
        ans_dict[inc_3] = calc_cost(inc_3, ans_dict)
    min_cost = min(min_cost, d * (inc_3 * 3 - n) + b + ans_dict[inc_3])

    dec_3 = int(math.floor(n / 3))
    if dec_3 not in ans_dict:
        ans_dict[dec_3] = calc_cost(dec_3, ans_dict)
    min_cost = min(min_cost, d * (- dec_3 * 3 + n) + b + ans_dict[dec_3])

    inc_5 = int(math.ceil(n / 5))
    if inc_5 not in ans_dict:
        ans_dict[inc_5] = calc_cost(inc_5, ans_dict)
    min_cost = min(min_cost, d * (inc_5 * 5 - n) + c + ans_dict[inc_5])

    dec_5 = int(math.floor(n / 5))
    if dec_5 not in ans_dict:
        ans_dict[dec_5] = calc_cost(dec_5, ans_dict)
    min_cost = min(min_cost, d * (- dec_5 * 5 + n) + c + ans_dict[dec_5])

    ans_dict[n] = min_cost
    return min_cost

n_testcase = int(input())
for i in range(n_testcase):
    n, a, b, c, d = list(map(int, input().split()))

    # テストケースごとに辞書はリセットしないとダメですね
    ans_dict = {}

    ans_dict[0] = 0
    ans_dict[1] = d  # 1減らすのが常に最善

    ans = calc_cost(n, ans_dict)
    print(ans)
    # print(ans_dict)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)
t=int(input())

def dfs(i):
	if i==0:
		return 0
	if i in memo:
		return memo[i]
	ret=i*d
	if i%2==0:
		ret=min(ret,dfs(i//2)+a)
	else:
		ret=min(ret,dfs((i-1)//2)+a+d)
	if i%3==0:
		ret=min(ret,dfs(i//3)+b)
	elif i%3==1:
		ret=min(ret,dfs((i-1)//3)+b+d)
	else:
		ret=min(ret,dfs((i+1)//3)+b+d)
	if i%5==0:
		ret=min(ret,dfs(i//5)+c)
	elif i%5==1:
		ret=min(ret,dfs((i-1)//5)+c+d)
	elif i%5==2:
		ret=min(ret,dfs((i-2)//5)+c+2*d)
	elif i%5==3:
		ret=min(ret,dfs((i+2)//5)+c+2*d)
	else:
		ret=min(ret,dfs((i+1)//5)+c+d)
	memo[i]=ret
	return ret

ans=[]
for _ in range(t):
	n,a,b,c,d=map(int,input().split())
	memo={}
	ans.append(dfs(n))
print("\n".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
T = int(input())
for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    ans = float("inf")
    for a in range(61):
        for b in range(61):
            for c in range(61):
                X = pow(2, a)*pow(3, b)*pow(5, c)
                d = abs(N-X)
                v = A*a+B*b+C*c+D*d+D
                ans = min(ans, v)
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    T = int(input())
    for _ in range(T):
        N, A, B, C, D = map(int, input().split())
        key = 1
        ans = D
        while True:
            a = abs(2 * key - N) * A
            b = abs(3 * key - N) * B
            c = abs(5 * key - N) * C
            d1 = abs((key + 1) - N) * D
            d2 = abs((key - 1) - N) * D
            li = [a, b, c, d1, d2]
            m = min(li)
            if m == a:
                key *= 2
                ans += A
            elif m == b:
                key *= 3
                ans += B
            elif m == c:
                key *= 5
                ans += C
            elif m == d1:
                key += 1
                ans += D
            else:
                key -= 1
                ans += D
            if key == N:
                break
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    T = int(input())
    for _ in range(T):
        N, A, B, C, D = map(int, input().split())
        key = 1
        ans = D
        while True:
            a = abs(2 * key - N) * A
            b = abs(3 * key - N) * B
            c = abs(5 * key - N) * C
            d1 = abs((key + 1) - N) * D
            d2 = abs((key - 1) - N) * D
            li = [a, b, c, d1, d2]
            m = min(li)
            if m == a:
                key *= 2
                ans += A
            elif m == b:
                key *= 3
                ans += B
            elif m == c:
                key *= 5
                ans += C
            elif m == a:
                key += 1
                ans += D
            else:
                key -= 1
                ans += D
            if key == N:
                break
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    T = int(input())
    for _ in range(T):
        N, A, B, C, D = map(int, input().split())
        key = 1
        ans = D
        while True:
            a = abs(2 * key - N)
            b = abs(3 * key - N)
            c = abs(5 * key - N)
            d1 = abs((key + 1) - N)
            d2 = abs((key - 1) - N)
            li = [a, b, c, d1, d2]
            if min(li) == a:
                key *= 2
                ans += A
            elif min(li) == b:
                key *= 3
                ans += B
            elif min(li) == c:
                key *= 5
                ans += C
            elif min(li) == a:
                key += 1
                ans += D
            else:
                key -= 1
                ans += D
            if key == N:
                break
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
from collections import deque

T = int(input())
for t in range(T):
    N,A,B,C,D = map(int,input().split())
    q = [(0,N)]
    heapq.heapify(q)
    seen = set()
    while q:
        cost, n = heapq.heappop(q)
        if n in seen:
            continue
        seen.add(n)
        if n == 0:
            print(cost)
            break

        heapq.heappush(q, (cost + N * D, 0))
        if n % 2 ==0:
            heapq.heappush(q, (cost + A, n // 2))
        else: # odd number
            heapq.heappush(q, (cost + D + A, (n + 1) // 2))
            heapq.heappush(q, (cost + D + A, (n - 1) // 2))
        if n % 3 ==0:
            heapq.heappush(q, (cost + B, n // 3))
        else:
            rest = n % 3
            heapq.heappush(q, (cost + rest * D + B, (n - rest) // 3))
            heapq.heappush(q, (cost + (3-rest) * D + B, (n - rest + 3) // 3))

        if n % 5 ==0:
            heapq.heappush(q, (cost + C, n // 5))
        else:
            rest = n % 5
            heapq.heappush(q, (cost + rest * D + C, (n - rest) // 5))
            heapq.heappush(q, (cost + (5-rest) * D + C, (n - rest + 5) // 5))

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)

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

 
for i in range(t):
    N = l[i][0]
    A = l[i][1]
    B = l[i][2]
    C = l[i][3]
    D = l[i][4]
    @lru_cache(maxsize=10**18)
    def min_coin(n):
        if(n == 0):
            return 0
        elif(n == 1):
            return D
        else:
            if(n%2 == 0):
                a = min_coin(n/2)
            else:
                a = min(min_coin(n//2)+D,min_coin(n//2+1)+D)
            if(n%3 == 0):
                b = min_coin(n/3)
            elif(n%3 == 1):
                b = min(min_coin(n//3)+D,min_coin(n//3+1)+D*2)
            else:
                b = min(min_coin(n//3)+D*2,min_coin(n//3+1)+D)
            if(n%5 == 0):
                c = min_coin(n/5)
            else:
                re = n%5
                c = min(min_coin(n//5)+D*re,min_coin(n//5+1)+D*(5-re))
            return min(a+A,b+B,c+C,D*n)   
    print(int(min_coin(N)))

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(100000)

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

 
for i in range(t):
    N = l[i][0]
    A = l[i][1]
    B = l[i][2]
    C = l[i][3]
    D = l[i][4]
    @lru_cache(maxsize=10**18)
    def min_coin(n):
        if(n == 0):
            return 0
        elif(n == 1):
            return D
        else:
            if(n%2 == 0):
                a = min_coin(n/2)
            else:
                a = min(min_coin(n//2)+D,min_coin(n//2+1)+D)
            if(n%3 == 0):
                b = min_coin(n/3)
            elif(n%3 == 1):
                b = min(min_coin(n//3)+D,min_coin(n//3+1)+D*2)
            else:
                b = min(min_coin(n//3)+D*2,min_coin(n//3+1)+D)
            if(n%5 == 0):
                c = min_coin(n/5)
            else:
                re = n%5
                c = min(min_coin(n//5)+D*re,min_coin(n//5+1)+D*(5-re))
            return min(a+A,b+B,c+C,D*n)   
    print(int(min_coin(N)))

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10000)

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

 
for i in range(t):
    N = l[i][0]
    A = l[i][1]
    B = l[i][2]
    C = l[i][3]
    D = l[i][4]
    @lru_cache(maxsize=10**18)
    def min_coin(n):
        if(n == 0):
            return 0
        elif(n == 1):
            return D
        else:
            if(n%2 == 0):
                a = min_coin(n/2)
            else:
                a = min(min_coin(n//2)+D,min_coin(n//2+1)+D)
            if(n%3 == 0):
                b = min_coin(n/3)
            elif(n%3 == 1):
                b = min(min_coin(n//3)+D,min_coin(n//3+1)+D*2)
            else:
                b = min(min_coin(n//3)+D*2,min_coin(n//3+1)+D)
            if(n%5 == 0):
                c = min_coin(n/5)
            else:
                re = n%5
                c = min(min_coin(n//5)+D*re,min_coin(n//5+1)+D*(5-re))
            return min(a+A,b+B,c+C,D*n)   
    print(int(min_coin(N)))

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10000)

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

 
for i in range(t):
    N = l[i][0]
    A = l[i][1]
    B = l[i][2]
    C = l[i][3]
    D = l[i][4]
    @lru_cache(maxsize=10**18)
    def min_coin(n):
        if(n == 0):
            return 0
        elif(n == 1):
            return D
        else:
            if(n%2 == 0):
                a = min_coin(n/2)
            else:
                a = min(min_coin(n//2)+D,min_coin(n//2+1)+D)
            if(n%3 == 0):
                b = min_coin(n/3)
            elif(n%3 == 1):
                b = min(min_coin(n//3)+D,min_coin(n//3+1)+D*2)
            else:
                b = min(min_coin(n//3)+D*2,min_coin(n//3+1)+D)
            if(n%5 == 0):
                c = min_coin(n/5)
            elif(n%5 == 1):
                c = min(min_coin(n//5)+D,min_coin(n//5+1)+D*4)
            elif(n%5 == 2):
                c = min(min_coin(n//5)+D*2,min_coin(n//5+1)+D*3)
            elif(n%5 == 3):
                c = min(min_coin(n//5)+D*3,min_coin(n//5+1)+D*2)
            else:
                c = min(min_coin(n//5)+D*4,min_coin(n//5+1)+D)
            return min(a+A,b+B,c+C,D*n)   
    print(int(min_coin(N)))

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10000)

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

@lru_cache(maxsize=10**18)
def min_coin(n,i):
    if(n == 0):
        return 0
    if(n == 1):
        return l[i][4]
    else:
        if(n%2 == 0):
            a = min_coin(n/2,i)
        else:
            a = min(min_coin(n//2,i)+l[i][4],min_coin(n//2+1,i)+l[i][4])
        if(n%3 == 0):
            b = min_coin(n/3,i)
        elif(n%3 == 1):
            b = min(min_coin(n//3,i)+l[i][4],min_coin(n//3+1,i)+l[i][4]*2)
        else:
            b = min(min_coin(n//3,i)+l[i][4]*2,min_coin(n//3+1,i)+l[i][4])
        if(n%5 == 0):
            c = min_coin(n/5,i)
        elif(n%5 == 1):
            c = min(min_coin(n//5,i)+l[i][4],min_coin(n//5+1,i)+l[i][4]*4)
        elif(n%5 == 2):
            c = min(min_coin(n//5,i)+l[i][4]*2,min_coin(n//5+1,i)+l[i][4]*3)
        elif(n%5 == 3):
            c = min(min_coin(n//5,i)+l[i][4]*3,min_coin(n//5+1,i)+l[i][4]*2)
        else:
            c = min(min_coin(n//5,i)+l[i][4]*4,min_coin(n//5+1,i)+l[i][4])
        return min(a+l[i][1],b+l[i][2],c+l[i][3],l[i][4]*n)    
for i in range(t):
    print(int(min_coin(l[i][0],i)))

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10000)

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

@lru_cache(maxsize=10**18)
def min_coin(n,i):
    if(n == 1):
        return l[i][4]
    else:
        if(n%2 == 0):
            a = min_coin(n/2,i)
        else:
            a = min(min_coin(n//2,i)+l[i][4],min_coin(n//2+1,i)+l[i][4])
        if(n%3 == 0):
            b = min_coin(n/3,i)
        elif(n == 2):
            b = min_coin(1,i)+l[i][4]
        elif(n%3 == 1):
            b = min(min_coin(n//3,i)+l[i][4],min_coin(n//3+1,i)+l[i][4]*2)
        else:
            b = min(min_coin(n//3,i)+l[i][4]*2,min_coin(n//3+1,i)+l[i][4])
        if(n%5 == 0):
            c = min_coin(n/5,i)
        elif(n == 2):
            c = l[i][4]*2
        elif(n == 3):
            c = l[i][4]*3
        elif(n == 4):
            c = min_coin(1,i)+l[i][4]
        elif(n%5 == 1):
            c = min(min_coin(n//5,i)+l[i][4],min_coin(n//5+1,i)+l[i][4]*4)
        elif(n%5 == 2):
            c = min(min_coin(n//5,i)+l[i][4]*2,min_coin(n//5+1,i)+l[i][4]*3)
        elif(n%5 == 3):
            c = min(min_coin(n//5,i)+l[i][4]*3,min_coin(n//5+1,i)+l[i][4]*2)
        else:
            c = min(min_coin(n//5,i)+l[i][4]*4,min_coin(n//5+1,i)+l[i][4])
        return min(a+l[i][1],b+l[i][2],c+l[i][3],l[i][4]*n)    
for i in range(t):
    print(int(min_coin(l[i][0],i)))

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10000)

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

@lru_cache(maxsize=10**18)
def min_coin(n,i):
    if(n == 1):
        return l[i][4]
    else:
        if(n%2 == 0):
            a = min_coin(n//2,i)
        else:
            a = min(min_coin(n//2,i)+l[i][4],min_coin(n//2+1,i)+l[i][4])
        if(n%3 == 0):
            b = min_coin(n/3,i)
        elif(n == 2):
            b = min_coin(1,i)+l[i][4]
        elif(n%3 == 1):
            b = min(min_coin(n//3,i)+l[i][4],min_coin(n//3+1,i)+l[i][4]*2)
        else:
            b = min(min_coin(n//3,i)+l[i][4]*2,min_coin(n//3+1,i)+l[i][4])
        if(n%5 == 0):
            c = min_coin(n/5,i)
        elif(n == 2):
            c = l[i][4]*2
        elif(n == 3):
            c = l[i][4]*3
        elif(n == 4):
            c = min_coin(1,i)+l[i][4]
        elif(n%5 == 1):
            c = min(min_coin(n//5,i)+l[i][4],min_coin(n//5+1,i)+l[i][4]*4)
        elif(n%5 == 2):
            c = min(min_coin(n//5,i)+l[i][4]*2,min_coin(n//5+1,i)+l[i][4]*3)
        elif(n%5 == 3):
            c = min(min_coin(n//5,i)+l[i][4]*3,min_coin(n//5+1,i)+l[i][4]*2)
        else:
            c = min(min_coin(n//5,i)+l[i][4]*4,min_coin(n//5+1,i)+l[i][4])
        return min(a+l[i][1],b+l[i][2],c+l[i][3],l[i][4]*n)    
for i in range(t):
    print(int(min_coin(l[i][0],i)))

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10000)

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

@lru_cache(maxsize=10**18)
def min_coin(n,i):
    if(n == 1):
        return l[i][4]
    else:
        if(n%2 == 0):
            a = min_coin(n//2,i)
        else:
            a = min(min_coin(n//2,i)+l[i][4],min_coin(n//2+1,i)+l[i][4])
        if(n%3 == 0):
            b = min_coin(n/3,i)
        elif(n == 2):
            b = min_coin(1,i)+l[i][4]
        elif(n%3 == 1):
            b = min(min_coin(n//3,i)+l[i][4],min_coin(n//3+1,i)+l[i][4]*2)
        else:
            b = min(min_coin(n//3,i)+l[i][4]*2,min_coin(n//3+1,i)+l[i][4])
        if(n%5 == 0):
            c = min_coin(n/5,i)
        elif(n == 2):
            c = min_coin(1,i)+l[i][4]*3
        elif(n == 3):
            c = min_coin(1,i)+l[i][4]*2
        elif(n == 4):
            c = min_coin(1,i)+l[i][4]
        elif(n%5 == 1):
            c = min(min_coin(n//5,i)+l[i][4],min_coin(n//5+1,i)+l[i][4]*4)
        elif(n%5 == 2):
            c = min(min_coin(n//5,i)+l[i][4]*2,min_coin(n//5+1,i)+l[i][4]*3)
        elif(n%5 == 3):
            c = min(min_coin(n//5,i)+l[i][4]*3,min_coin(n//5+1,i)+l[i][4]*2)
        else:
            c = min(min_coin(n//5,i)+l[i][4]*4,min_coin(n//5+1,i)+l[i][4])
        return min(a+l[i][1],b+l[i][2],c+l[i][3],l[i][4]*n)    
for i in range(t):
    print(int(min_coin(l[i][0],i)))

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10000)

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

@lru_cache(maxsize=10**18)
def min_coin(n,i):
    if(n == 1):
        return l[i][4]
    else:
        if(n%2 == 0):
            a = min_coin(n//2,i)
        else:
            a = min(min_coin(n//2,i)+l[i][4],min_coin(n//2+1,i)+l[i][4])
        if(n%3 == 0):
            b = min_coin(n/3,i)
        elif(n == 2):
            b = min_coin(1,i)+l[i][4]
        elif(n%3 == 1):
            b = min(min_coin(n//3,i)+l[i][4],min_coin(n//3+1,i)+l[i][4]*2)
        else:
            b = min(min_coin(n//3,i)+l[i][4]*2,min_coin(n//3+1,i)+l[i][4])
        if(n%5 == 0):
            c = min_coin(n/5,i)
        elif(n == 2):
            c = min_coin(1,i)+l[i][4]*3
        elif(n == 3):
            c = min_coin(1,i)+l[i][4]*2
        elif(n == 4):
            c = min_coin(1,i)+l[i][4]
        elif(n%5 == 1):
            c = min(min_coin(n//5,i)+l[i][4],min_coin(n//5+1,i)+l[i][4]*4)
        elif(n%5 == 2):
            c = min(min_coin(n//5,i)+l[i][4]*2,min_coin(n//5+1,i)+l[i][4]*3)
        elif(n%5 == 3):
            c = min(min_coin(n//5,i)+l[i][4]*3,min_coin(n//5+1,i)+l[i][4]*2)
        else:
            c = min(min_coin(n//5,i)+l[i][4]*4,min_coin(n//5+1,i)+l[i][4])
        return min(a+l[i][1],b+l[i][2],c+l[i][3],l[i][4]*n)    
for i in range(t):
    print(min_coin(l[i][0],i))

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)

@lru_cache(maxsize=10000)
def search(n, a, b, c, d, k, result):
    if(k == 0):
        return result
    elif(k == 1):
        return result + d
    elif(k == 2):
        return min(result +2*d, result + a +d)
    else:
        if(k % 2 == 0):
            m1 = 0
        else:
            m1 = 1
        m2 = m1
        if(k % 3 == 0):
            m3 = 0
            m4 = 0
        else:
            m3 = 3 - (k%3)
            m4 = 3 - m3
        if(k % 5 == 0):
            m5 = 0
            m6 = 0
        else:
            m5 = 5 - (k%5)
            m6 = 5 - m5
        return min(search(n, a, b, c, d, (k + m1)/2, result + d * m1 + a),
                    search(n, a, b, c, d, (k - m2)/2, result + d * m2 + a),
                    search(n, a, b, c, d, (k + m3)/3, result + d * m3 + b),
                    search(n, a, b, c, d, (k - m4)/3, result + d * m4 + b),
                    search(n, a, b, c, d, (k + m5)/5, result + d * m5 + c),
                    search(n, a, b, c, d, (k - m6)/5, result + d * m6 + c))

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