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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    t = I()
    aa = [LI() for _ in range(t)]

    rr = []
    for n,a,b,c,dd in aa:
        e = {2: a, 3: b, 5: c}
        def search(s, t):
            d = collections.defaultdict(lambda: inf)
            d[s] = 0
            q = []
            heapq.heappush(q, (0, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if u == t:
                    return k
                if v[u]:
                    continue
                v[u] = True

                if d[t] > k + dd * (u-t):
                    d[t] = k + dd * (u-t)
                for ek, ev in e.items():
                    m = u % ek
                    if m == 0:
                        if d[u//ek] > k + ev:
                            d[u//ek] = k + ev
                            heapq.heappush(q, (k+ev, u//ek))
                    else:
                        if d[u//ek + 1] > k + ev + (ek - m) * dd:
                            d[u//ek + 1] = k + ev + (ek - m) * dd
                            heapq.heappush(q, (k + ev + (ek - m) * dd, u//ek + 1))
                        if d[u//ek] > k + ev + m * dd:
                            d[u//ek] = k + ev + m * dd
                            heapq.heappush(q, (k + ev + m * dd, u//ek))

            return d[t]

        rr.append(search(n, 1) + dd)

    return JA(rr, "\n")

print(main())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math
import heapq

T = int(input())
test_cases = [list(map(int,input().split())) for _ in range(T)]


for test_num in range(T):
    hq = []
    kake_patterns = [2,3,5]
    cost_patterns = [test_cases[test_num][1],test_cases[test_num][2],test_cases[test_num][3]]
    plmi_cost = test_cases[test_num][4]
    heapq.heappush(hq,-test_cases[test_num][0])
    memo = defaultdict(int)
    memo[test_cases[test_num][0]] = 0
    memo[0] = plmi_cost*test_cases[test_num][0]
    
    while len(hq)>0:
        checking = heapq.heappop(hq)
        checking = -checking
        cost = memo[checking]
        
        if checking in [0,1]:
            continue
        for i,kake in enumerate(kake_patterns):
            devided1 = math.floor(checking/kake)
            devided2 = math.ceil(checking/kake)
            
            added_cost1 = cost + abs(math.floor(checking/kake)*kake-checking)*plmi_cost + cost_patterns[i]
            added_cost2 = cost + abs(math.ceil(checking/kake)*kake - checking)*plmi_cost + cost_patterns[i]
            
            if devided1 in memo:
                if added_cost1 < memo[devided1]:
                    memo[devided1] = added_cost1
            else:
                memo[devided1] = added_cost1
                heapq.heappush(hq,-devided1)
            
            if devided2 in memo:
                if added_cost2 < memo[devided2]:
                    memo[devided2] = added_cost2
            else:
                memo[devided2] = added_cost2
                heapq.heappush(hq,-devided2)
            
            if added_cost1 + devided1*plmi_cost < memo[0]:
                memo[0] = added_cost1 + devided1*plmi_cost
            if added_cost2 + devided2*plmi_cost < memo[0]:
                memo[0] = added_cost2 + devided2*plmi_cost
            
    print(memo[0])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math
import heapq


T = int(input())
test_cases = [list(map(int,input().split())) for _ in range(T)]


for test_num in range(T):
    hq = []
    kake_patterns = [2,3,5]
    cost_patterns = [test_cases[test_num][1],test_cases[test_num][2],test_cases[test_num][3]]
    plmi_cost = test_cases[test_num][4]
    heapq.heappush(hq,-test_cases[test_num][0])
    memo = defaultdict(int)
    memo[test_cases[test_num][0]] = 0
    memo[0] = plmi_cost*test_cases[test_num][0]
    
    while len(hq)>0:
        checking = heapq.heappop(hq)
        checking = -checking
        cost = memo[checking]
        
        if checking in [0,1]:
            continue
        for i,kake in enumerate(kake_patterns):
            devided1 = math.floor(checking/kake)
            devided2 = math.ceil(checking/kake)
            
            added_cost1 = cost + abs(math.floor(checking/kake)*kake-checking)*plmi_cost + cost_patterns[i]
            added_cost2 = cost + abs(math.ceil(checking/kake)*kake - checking)*plmi_cost + cost_patterns[i]
            
            if devided1 in memo:
                if added_cost1 < memo[devided1]:
                    memo[devided1] = added_cost1
            else:
                memo[devided1] = added_cost1
                heapq.heappush(hq,-devided1)
            
            if devided2 in memo:
                if added_cost2 < memo[devided2]:
                    memo[devided2] = added_cost2
            else:
                memo[devided2] = added_cost2
                heapq.heappush(hq,-devided2)
            
            if added_cost1 + devided1*plmi_cost < memo[0]:
                memo[0] = added_cost1 + devided1*plmi_cost
            if added_cost2 + devided2*plmi_cost < memo[0]:
                memo[0] = added_cost2 + devided2*plmi_cost
            
    min_cost_multiple = min(memo[0], memo[1] + plmi_cost)
    
    print(min_cost_multiple)

Submission status: Wrong Answer

Solution code:
#Grand 044 - C
import sys


def P_change(N, P):
    #Salsa
    for i in range(N):
        start = 3 ** i
        stop = 3 ** N
        step = 3 ** (i + 1)
        dp = 3 ** i
        for j in range(start, stop, step):
            P[j:j + dp], P[j + dp:j + dp * 2] = P[j + dp:j + dp * 2], P[j:j + dp]

    return P


def P_slide(P):
    #Rumba
    temp = P[-1]
    P[1:] = P[:-1]
    P[0] = temp

    return P


def dance(N, D, P):
    for Dn in D:
        if Dn:
            #Salsa
            P = P_change(N, P)
        else:
            #Rumba
            P = P_slide(P)

    N3 = 3 ** N
    R = [0] * N3
    for i in range(N3):
        R[P[i]] = i

    return  R
    

N = int(input())
T = input()

N3 = 3 ** N
P = list(range(N3))
#サルサの２回連続は元に戻る
T = T.replace('SS', '')
D = [1 if Ti == 'S' else 0 for Ti in T]

R = dance(N, D, P)

print(*R)

sys.exit()

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 sys
import heapq
from collections import deque
readline = sys.stdin.readline
T=int(readline())
for t in range(T):
    N,A,B,C,D= map(int,readline().split())
    q = [(0,N)]
    #リストを優先度付きのキューに変換
    heapq.heapify(q)
    #空のセットを生成(set([]))
    seen=set()
    while q:
        cost,n = heapq.heappop(q)
        if n in seen:
            continue
        #setに要素を追加 set([n])
        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:
            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+C,n//3))
        else:
            rest=n % 3
            heapq.heappush(q,(cost+rest*D+B,(n-rest+3)//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
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)
    #空のセットを生成(set([]))
    seen=set()
    while q:
        cost,n = heapq.heappop(q)
        if n in seen:
            continue
        #setに要素を追加 set([n])
        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:
            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+C,n//3))
        else:
            rest=n % 3
            heapq.heappush(q,(cost+rest*D+B,(n-rest+3)//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 heapq
class DFS:
    def __init__(self,n,a,b,c,d):
        self.N = n
        self.A = a
        self.B = b
        self.C = c
        self.D = d
        self.ans = self.N * self.D
        self.Q = [[0,n]]
    def dfs(self):
        while self.Q:
#             from IPython.core.debugger import Pdb; Pdb().set_trace()
            cost,num = heapq.heappop(self.Q)
            if num == 0:
                return cost
            elif num == 1:
                heapq.heappush(self.Q,[cost+self.D,0])
            else:
                # 5の倍数に上げて5で割った場合
                temp_num = num//5 + 1
                temp_cost = cost + ((num//5 + 1) * 5 - num) * self.D + self.C
                heapq.heappush(self.Q,[temp_cost,temp_num])

                # 5の倍数に下げて5で割った場合
                temp_num = num//5
                temp_cost = cost + (num - (num//5)*5) * self.D + self.C
                heapq.heappush(self.Q,[temp_cost,temp_num])

                # 3の倍数に上げて3で割った場合
                temp_num = num//3 + 1
                temp_cost = cost + ((num//3 + 1) * 3 - num) * self.D + self.B
                heapq.heappush(self.Q,[temp_cost,temp_num])

                # 3の倍数に下げて3で割った場合
                temp_num = num//3
                temp_cost = cost + (num - (num//3)*3) * self.D + self.B
                heapq.heappush(self.Q,[temp_cost,temp_num])

                # 2の倍数に上げて2で割った場合
                temp_num = num//2 + 1
                temp_cost = cost + ((num//2 + 1) * 2 - num) * self.D + self.A
                heapq.heappush(self.Q,[temp_cost,temp_num])

                # 2の倍数に下げて2で割った場合
                temp_num = num//2
                temp_cost = cost + (num - (num//2)*2) * self.D + self.A
                heapq.heappush(self.Q,[temp_cost,temp_num])

                # 全て引いた場合
                heapq.heappush(self.Q,[temp_cost,temp_num])
                
        return self.ans
T = int(input())
for _ in range(T):
    N,A,B,C,D = map(int,input().split())
    case = DFS(N,A,B,C,D)
    print(case.dfs())

Submission status: Wrong Answer

Solution code:
import math

T = int(input())

def select_abcd(v, r, N, A, B, C, D, min_v):
  if r == N:
    return v
  if r > N:
    return min(v + D * (r - N), min_v)
  if v == 0:
    return select_abcd(v + D, r + 1, N, A, B, C, D, min_v)
  else:
    tmp = (N - r) * D
    if min_v > v + D:
      if tmp < A + abs(r * 2 - N) * D and tmp < B + abs(r * 3 - N) * D and tmp < C + abs(r * 5 - N) * D:
        return min(min_v, v + tmp)
      if A > D and B > D and C > D:
        min_v = min(min_v, select_abcd(v + D, r + 1, N, A, B, C, D, min_v))
    if min_v > v + A and tmp > A + abs(r * 2 - N) * D:
      min_v = min(min_v, select_abcd(v + A, r * 2, N, A, B, C, D, min_v))
    if A + A + abs(r * 4 - N) * D > B + abs(r * 3 - N) * D and min_v > v + B and tmp > B + abs(r * 3 - N) * D:
      min_v = min(min_v, select_abcd(v + B, r * 3, N, A, B, C, D, min_v))
    if A + B + abs(r * 6 - N) * D > C + abs(r * 5 - N) * D and min_v > v + C and tmp > C + abs(r * 5 - N) * D:
      min_v = min(min_v, select_abcd(v + C, r * 5, N, A, B, C, D, min_v))
    return min_v


for _ in range(T):
  N, A, B, C, D = [int(s) for s in input().split(" ")]
  v = select_abcd(0, 0, N, A, B, C, D, math.inf)
  print(v)

Submission status: Wrong Answer

Solution code:
import heapq
class DFS:
    def __init__(self,n,a,b,c,d):
        self.N = n
        self.A = a
        self.B = b
        self.C = c
        self.D = d
        self.Q = [[0,n]]
    def dfs(self):
        while self.Q:
#             from IPython.core.debugger import Pdb; Pdb().set_trace()
            cost,num = heapq.heappop(self.Q)
            if num == 0:
                return cost
            elif num == 1:
                return cost + self.D * num
            else:
                # 5の倍数に下げて5で割った場合
                temp_num = num//5
                temp_cost = cost + (num - (num//5)*5) * self.D + self.C
                heapq.heappush(self.Q,[temp_cost,temp_num])
                
                # 3の倍数に下げて3で割った場合
                temp_num = num//3
                temp_cost = cost + (num - (num//3)*3) * self.D + self.B
                heapq.heappush(self.Q,[temp_cost,temp_num])
                
                # 2の倍数に下げて2で割った場合
                temp_num = num//2
                temp_cost = cost + (num - (num//2)*2) * self.D + self.A
                heapq.heappush(self.Q,[temp_cost,temp_num])
                
                # 全て引いた場合
                heapq.heappush(self.Q,[temp_cost,temp_num])
T = int(input())
for _ in range(T):
    N,A,B,C,D = map(int,input().split())
    case = DFS(N,A,B,C,D)
    print(case.dfs())

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
input = sys.stdin.readline
for _ in range(int(input())):
  N, A, B, C, D = map(int, input().split())
  h = [(N, 0)]
  d = dd(lambda: float("inf"))
  d[N] = 0
  while len(h):
    x, c = hpop(h)
    if x == 0: continue
    elif x == 1:
      d[0] = min(d[0], c + D)
      continue
    if d[0] <= c: continue
    if d[x // 2] > c + A + (x % 2) * D:
      hpush(h, (x // 2, c + A + (x % 2) * D))
      d[x // 2] = c + A + (x % 2) * D
    if d[-(-x // 2)] > c + A + (x % 2) * D:
      hpush(h, (-(-x // 2), c + A + (-x % 2) * D))
      d[-(-x // 2)] = c + A + (-x % 2) * D

    if d[x // 3] > c + B + (x % 3) * D:
      hpush(h, (x // 3, c + B + (x % 3) * D))
      d[x // 3] = c + B + (x % 3) * D
    if d[-(x // 3)] > c + B + (-x % 3) * D:
      hpush(h, (-(-x // 3), c + B + (-x % 3) * D))
      d[-(-x // 3)] = c + B + (-x % 3) * D

    if d[x // 5] > c + C + (x % 5) * D:
      hpush(h, (x // 5, c + C + (x % 5) * D))
      d[x // 5] = c + C + (x % 5) * D
    if d[x // 5] > c + C + (-x % 5) * D:
      hpush(h, (-(-x // 5), c + C + (-x % 5) * D))
      d[-(-x // 5)] = c + C + (-x % 5) * D
  print(d[0])

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
input = sys.stdin.readline
#S,L,R = map(int, input().split())

def solve(N,A,B,C,D):
    
    dp = {}
    INF = 1<<61
    
    def dfs(n):
        if n in dp:
            return dp[n]
        if n<=0:
            return 0
        if n==1:
            return D
        
        R = INF
        if n<INF/D:
            R = n*D;
        
        #2 floor
        R = min(R,A+D*(n%2)+dfs(math.floor(n/2)))
        
        #2 ceil
        if n%2 != 0:
            R = min(R,A+D*(2-n%2)+dfs(math.ceil(n/2)))
        
        
        #3 floor
        R = min(R,B+D*(n%3)+dfs(math.floor(n/3)))
        
        #3 ceil
        if n%3 != 0:
            R = min(R,B+D*(3-n%3)+dfs(math.ceil(n/3)))
        
        
        #5 floor
        R = min(R,C+D*(n%5)+dfs(math.floor(n/5)))
        
        #5 ceil
        if n%5 != 0:
            R = min(R,C+D*(5-n%5)+dfs(math.ceil(n/5)))
        
        
        dp[n]=R
        return R
    
    return dfs(N)
    

T = int(input());
for i 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:
import sys
import math
from collections import deque
input = sys.stdin.readline
#S,L,R = map(int, input().split())

def solve(N,A,B,C,D):
    
    INF = float('inf')
    dp = {}
    
    def dfs(n):
        if n in dp:
            return dp[n]
        if n<=0:
            return 0
        if n==1:
            return D
        
        R = n*D
        
        #2 floor
        R = min(R,A+D*(n%2)+dfs(math.floor(n/2)))
        
        #2 ceil
        if n%2 != 0:
            R = min(R,A+D*(2-n%2)+dfs(math.ceil(n/2)))
        
        
        #3 floor
        R = min(R,B+D*(n%3)+dfs(math.floor(n/3)))
        
        #3 ceil
        if n%3 != 0:
            R = min(R,B+D*(3-n%3)+dfs(math.ceil(n/3)))
        
        
        #5 floor
        R = min(R,C+D*(n%5)+dfs(math.floor(n/5)))
        
        #5 ceil
        if n%5 != 0:
            R = min(R,C+D*(5-n%5)+dfs(math.ceil(n/5)))
        
        
        dp[n]=R
        return R
    
    return dfs(N)
    

T = int(input());
for i 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:
import sys
import heapq
from collections import defaultdict
read = sys.stdin.buffer.read

N, *r = map(int, read().split())
r=iter(r)
Querys=zip(r,r,r,r,r)

cost=defaultdict(lambda :10**27)
que=0
def push(n,c):
    if n not in cost:
        heapq.heappush(que,(c,n))
    cost[n]=min(cost[n],c)
    
for n,a,b,c,d in Querys:
    cost.clear()
    cost[n]=0
    que=[(0,n)]#number

    #1になるのに最小のものを見つける
    while que:
        C,n=heapq.heappop(que)
        C=cost[n]
        if n==1 or cost[n]<C:
            continue
        # 2で割る
        if n%2==0:
            push(n//2,C+a)
        else:
            push(n//2,C+a+d)
            push(n//2+1,C+a+d)
        # 3
        if n<3:
            continue
        if n%3==0:
            push(n//3,C+b)
        if n%3==1:
            push(n//3,C+b+d)
        if n%3==2:
            push(n//3+1,C+b+d)
        # 5
        if n<5:
            continue
        if n%5==0:
            push(n//5,C+c)
        if n%5==1:
            push(n//5,C+c+d)
        if n%5==2:
            push(n//5,C+c+2*d)
        if n%5==3:
            push(n//5+1,C+c+2*d)
        if n%5==4:
            push(n//5+1,C+c+d)
    print(cost[1]+d)

Submission status: Wrong Answer

Solution code:
def solve(n,a,b,c,d):
  if n == 1:
    return d
  tmp = (n-1) * d
  if n % 2 == 0:
    return min(a + solve(int(n/2),a,b,c,d), tmp)
  if n % 3 == 0:
    return min(b + solve(int(n/3),a,b,c,d), tmp)
  if n % 5 == 0:
    return min(c + solve(int(n/5),a,b,c,d), tmp)
  else:
    return min(d + solve(n+1,a,b,c,d), d + solve(n-1,a,b,c,d), tmp)

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:
class Paytowin:
    def __init__(self, a: int, b: int, c: int, d: int, n: int):
        self.a = a
        self.b = b
        self.c = c
        self.d = d
        self.n = n
        self.coin = n*d
        self.memo = {0: 0, 1: self.d}

    def printnum(self):
        print(self.n)
        print(self.a)
        print(self.b)
        print(self.c)
        print(self.d)

    def solution(self, n: int):
        if n in self.memo:
            return self.memo[n]
        l2 = (n//2)*2
        r2 = ((n+1)//2)*2
        l3 = (n//3)*3
        r3 = ((n+2)//3)*3
        l5 = (n//5)*5
        r5 = ((n+4)//5)*5

        self.coin = min(self.coin, (n - l2) * self.d + self.a + self.solution(l2 // 2))
        self.coin = min(self.coin, (r2 - n) * self.d + self.a + self.solution(r2 // 2))
        self.coin = min(self.coin, (n - l3) * self.d + self.b + self.solution(l3 // 3))
        self.coin = min(self.coin, (r3 - n) * self.d + self.b + self.solution(r3 // 3))
        self.coin = min(self.coin, (n - l5) * self.d + self.c + self.solution(l5 // 5))
        self.coin = min(self.coin, (r5 - n) * self.d + self.c + self.solution(r5 // 5))

        self.memo[n] = self.coin

        return self.coin


T = int(input())
answer = []
for i in range(0, T):
    num = input()
    numlist = num.split()
    pay = Paytowin(n=int(numlist[0]), a=int(numlist[1]), b=int(numlist[2]), c=int(numlist[3]), d=int(numlist[4]))
    pay.solution(n=int(numlist[0]))
    print(pay.coin)

Submission status: Wrong Answer

Solution code:
class Paytowin:
    def __init__(self, a: int, b: int, c: int, d: int, n: int):
        self.a = a
        self.b = b
        self.c = c
        self.d = d
        self.n = n
        self.coin = n*d
        self.memo = {0: 0, 1: self.d}

    def printnum(self):
        print(self.n)
        print(self.a)
        print(self.b)
        print(self.c)
        print(self.d)

    def solution(self, n: int):
        if n in self.memo:
            return self.memo[n]
        l2 = (n//2)*2
        r2 = ((n+1)//2)*2
        l3 = (n//3)*3
        r3 = ((n+2)//3)*3
        l5 = (n//5)*5
        r5 = ((n+4)//5)*5

        self.coin = min(self.coin, (n - l2) * self.d + self.a + self.solution(l2 // 2))
        self.coin = min(self.coin, (r2 - n) * self.d + self.a + self.solution(r2 // 2))
        self.coin = min(self.coin, (n - l3) * self.d + self.b + self.solution(l3 // 3))
        self.coin = min(self.coin, (r3 - n) * self.d + self.b + self.solution(r3 // 3))
        self.coin = min(self.coin, (n - l5) * self.d + self.c + self.solution(l5 // 5))
        self.coin = min(self.coin, (r5 - n) * self.d + self.c + self.solution(r5 // 5))

        self.memo[n] = self.coin

        return self.coin


T = int(input())
answer = []
for i in range(0, T):
    num = input()
    numlist = num.split()
    print(numlist)
    pay = Paytowin(n=int(numlist[0]), a=int(numlist[1]), b=int(numlist[2]), c=int(numlist[3]), d=int(numlist[4]))
    pay.solution(n=int(numlist[0]))
    #print(pay.coin)
    answer.append(pay.coin)
for i in range(0, T):
    print(answer[i])

Submission status: Wrong Answer

Solution code:
class Paytowin:
    def __init__(self, a: int, b: int, c: int, d: int, n: int):
        self.a = a
        self.b = b
        self.c = c
        self.d = d
        self.n = n
        self.coin = n*d
        self.memo = {0: 0, 1: self.d}

    def solution(self, n: int):
        if n in self.memo:
            return self.memo[n]
        l2 = (n//2)*2
        r2 = ((n+1)//2)*2
        l3 = (n//3)*3
        r3 = ((n+2)//3)*3
        l5 = (n//5)*5
        r5 = ((n+4)//5)*5

        self.coin = min(self.coin, (n - l2) * self.d + self.a + self.solution(l2 // 2))
        self.coin = min(self.coin, (r2 - n) * self.d + self.a + self.solution(r2 // 2))
        self.coin = min(self.coin, (n - l3) * self.d + self.b + self.solution(l3 // 3))
        self.coin = min(self.coin, (r3 - n) * self.d + self.b + self.solution(r3 // 3))
        self.coin = min(self.coin, (n - l5) * self.d + self.c + self.solution(l5 // 5))
        self.coin = min(self.coin, (r5 - n) * self.d + self.c + self.solution(r5 // 5))

        self.memo[n] = self.coin

        return self.coin




T = int(input())
for i in range(0, T):
    num = input()
    numlist = num.split()
    print(numlist)
    pay = Paytowin(n=int(numlist[0]), a=int(numlist[1]), b=int(numlist[2]), c=int(numlist[3]), d=int(numlist[4]))
    pay.solution(n=int(numlist[0]))
    print(pay.coin)

Submission status: Wrong Answer

Solution code:
t = int(input())

import sys
import math
sys.setrecursionlimit(10**8)

def solve(x):
    if x == 0 :
        return 0
    if x == 1:
        return d
    if x in mem:
        return mem[x]

    temp = min([ solve(math.ceil(x/2)) + (abs(x - (2*math.ceil(x/2)))*d) + a,
                 solve(math.floor(x/2)) + (abs(x - (2*math.floor(x/2)))*d)+a,
                 solve(math.ceil(x/3)) + (abs(x - (3*math.ceil(x/3)))*d) + b,
                 solve(math.floor(x/3)) + (abs(x - (3*math.floor(x/3)))*d)+b,
                 solve(math.ceil(x/5)) + (abs(x - (5*math.ceil(x/5)))*d) + c,
                 solve(math.floor(x/5)) + (abs(x - (5*math.floor(x/5)))*d)+c,
                 x*d ])
                 

    mem[x] = temp
    return temp
    
for i in range(0,t):
    line = [int(x) for x in input().split()]

    n = line[0]
    a = line[1]
    b = line[2]
    c = line[3]
    d = line[4]

    total  = 0

    mem = {}
    
    print(solve(n))

Submission status: Wrong Answer

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

T = int(input())


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


    def f(n):
        if n == 0:
            return 0
        if n == 1:
            return D
        if n in memo.keys():
            return memo[n]

        ret = 1 << 100
        ret = min(ret, f(n // 2) + (n - n // 2 * 2) * D + A, f(n // 2) + (n - n // 2) * D)
        ret = min(ret, f(n // 3) + (n - n // 3 * 3) * D + B, f(n // 3) + (n - n // 3) * D)
        ret = min(ret, f(n // 5) + (n - n // 5 * 5) * D + C, f(n // 5) + (n - n // 5) * D)
        ret = min(ret, f(n // 2) + ((n + 1) // 2 * 2 - n) * D + A, f((n + 1) // 2) + (n - (n + 1) // 2) * D)
        ret = min(ret, f(n // 3) + ((n + 2) // 3 * 3 - n) * D + B, f((n + 2) // 3) + (n - (n + 2) // 3) * D)
        ret = min(ret, f(n // 5) + ((n + 4) // 5 * 5 - n) * D + C, f((n + 4) // 5) + (n - (n + 4) // 5) * D)
        memo[n] = ret
        return ret

    print(f(N))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    memo = {i: -1 for i in range(n+1)}
    def f(x):
        if memo[x] != -1:
            return memo[x]
        if x == 0:
            return 0
        if abs(x) == 1:
            return d

        ans = []
        if x % 2 == 0:
            ans.append(f(x // 2) + a)
        else:
            ans.append(f((x+1) // 2) + a + d)
            ans.append(f((x-1) // 2) + a + d)

        if x % 3 == 0:
            ans.append(f(x // 3) + b)
        elif x % 3 == 1:
            ans.append(f((x-1) // 3) + b + d)
        elif x % 3 == 2:
            ans.append(f((x+1) // 3) + b + d)

        if x % 5 == 0:
            ans.append(f(x // 5) + c)
        elif x % 5 == 1:
            ans.append(f((x-1) // 5) + c + d)
        elif x % 5 == 2:
            ans.append(f((x-2) // 5) + c + 2 * d)
        elif x % 5 == 3:
            ans.append(f((x+2) // 5) + c + 2 * d)
        elif x % 5 == 4:
            ans.append(f((x+1) // 5) + c + d)

        memo[x] = min(ans)
        return memo[x]

    print(f(n))

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import defaultdict
import math
t = int(input())
def solve(n):
    if dist[n] != float('inf'):
        return dist[n]
    if n == 0:
        return 0
    if n == 1:
        return d
    ans = float('inf')
    for x,cost in ([5,c],[3,b],[2,a]):
        e = 0
        if n%x:
            e = 1 #余りでるフラグ
        y = n%x
        ans = min(ans,solve(n//x) + cost + (e*d*y))

        if e ==1:
            ans = min(ans,solve(n//x+1) + cost + ((x-y)*d))
    dist[n] = ans   
    return ans

for i in range(t):
    n,a,b,c,d, = list(map(int,input().split()))
    dist = defaultdict(lambda: float('inf'))
    print(solve(n))