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:
from math import ceil,floor,log
from decimal import *
from heapq import *
import sys
input=sys.stdin.readline
T=int(input())
cases=[list(map(int,input().split())) for _ in range(T)]
getcontext().prec=28
num=0
cnt=0
for i in cases:
    l2=[0]*3
    N,l2[0],l2[1],l2[2],D=i
    d = {}
    num=0
    cnt=0
    for j in range(60):         #2の累乗
        for k in range(38):     #3の累乗
            for l in range(26): #5の累乗
                div=pow(2,j)*pow(3,k)*pow(5,l)
                x=Decimal(N)/Decimal(div)
                c=x.to_integral_exact(rounding=ROUND_CEILING)
                f=x.to_integral_exact(rounding=ROUND_FLOOR)
                if d.get(c)==None:
                    d[c]=float("inf")
                if d.get(f)==None:
                    d[f]=float("inf")
    d[N]=0
    #print(d)
    q=[]
    q.append((0,N))
    heapify(q)
    print(d)
    while len(q)>0:
        dist,u=heappop(q)
        if d[u]<dist: continue
        for j in range(3):
            num=1+pow(2,j)
            cnt=l2[j]
            x = Decimal(u) / Decimal(num)
            v1 = x.to_integral_exact(rounding=ROUND_CEILING)
            v2 = x.to_integral_exact(rounding=ROUND_FLOOR)
            # v1=ceil(u/2)
            # v2=floor(u/2)
            alt1 = d[u] + min(cnt+((num-(u%num))%num)*D,(u-v1)*D)
            alt2 = d[u] + min(cnt+(u%num)*D,(u-v2)*D)
            if d[v1] > alt1:
                d[v1] = alt1
                heappush(q, (alt1, v1))
            if d[v2] > alt2:
                d[v2] = alt2
                heappush(q, (alt2, v2))
        #print(d)
        #input()
    print(d[0])
    #print(len(d))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
def run():
    T = int(input())
    for ii in range(T):
        N, A, B, C, D = map(int, input().split())
        stack = [(0, N)]
        min_num = float('inf')
        visited = {}
        while stack:
            money, current = heappop(stack)
            if current > N:continue
            if current in visited.keys():
                continue
            visited[current] = 0
            if current == 0:break

            for pro, cost in ((2, A), (3, B), (5, C)):
                tmp = current % pro
                next_num1 = (current - tmp)//pro
                next_num2 = (current + pro - tmp)//pro
                cond1 = N >= current + pro - tmp
                if pro == 2:
                    heappush(stack, (min(cost, D * next_num1) + tmp * D + money, next_num1))
                    if next_num2 != tmp:# and (not next_num2 % 3 or not next_num2 % 5):
                        heappush(stack, (min((2 - tmp) * D + cost + money, (next_num2 - tmp) * D + money), next_num2))
                elif pro == 3:
                    heappush(stack, (min(cost, D * (2 * next_num1))+ tmp * D + money, next_num1))
                    if 2 * next_num2 != tmp:# and (not next_num2 % 2 or not next_num2 % 5):
                        heappush(stack, (min((3 - tmp) * D + cost + money, (2 * next_num2 - tmp) * D + money), next_num2))
                else:
                    heappush(stack, (min(cost, D * (4 * next_num1))+ tmp * D + money, next_num1))
                    if 4 * next_num2 != tmp:# and (not next_num2 % 2 or not next_num2 % 3):
                        heappush(stack, (min((5 - tmp) * D + cost + money, (4 * next_num2 - tmp) * D + money), next_num2))

                #if next_num1 < min_num:
                #    heappush(stack, (min(cost, D * ((pro-1) * next_num1))+ tmp * D + money, next_num1))
                #if next_num2 < min_num and (pro - 1) * next_num2 != tmp and current < 5:
                #    heappush(stack, (min((pro - tmp) * D + cost + money, ((pro-1) * next_num2 - tmp) * D + money), next_num2))
        print(money)
if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
def run():
    T = int(input())
    for ii in range(T):
        N, A, B, C, D = map(int, input().split())
        stack = [(0, N)]
        min_num = float('inf')
        visited = {}
        while stack:
            money, current = heappop(stack)
            if current in visited.keys():
                continue
            visited[current] = 0
            if current == 0:break

            for pro, cost in ((2, A), (3, B), (5, C)):
                tmp = current % pro
                next_num1 = (current - tmp)//pro
                next_num2 = (current + pro - tmp)//pro
                if pro == 2:
                    heappush(stack, (min(cost, D * next_num1) + tmp * D + money, next_num1))
                    if next_num2 != tmp and (not next_num2 % 3 or not next_num2 % 5):
                        heappush(stack, (min((2 - tmp) * D + cost + money, (next_num2 - tmp) * D + money), next_num2))
                elif pro == 3:
                    heappush(stack, (min(cost, D * (2 * next_num1))+ tmp * D + money, next_num1))
                    if next_num2 != tmp and (not next_num2 % 2 or not next_num2 % 5):
                        heappush(stack, (min((3 - tmp) * D + cost + money, (2 * next_num2 - tmp) * D + money), next_num2))
                else:
                    heappush(stack, (min(cost, D * (4 * next_num1))+ tmp * D + money, next_num1))
                    if next_num2 != tmp and (not next_num2 % 2 or not next_num2 % 3):
                        heappush(stack, (min((5 - tmp) * D + cost + money, (4 * next_num2 - tmp) * D + money), next_num2))

                #if next_num1 < min_num:
                #    heappush(stack, (min(cost, D * ((pro-1) * next_num1))+ tmp * D + money, next_num1))
                #if next_num2 < min_num and (pro - 1) * next_num2 != tmp and current < 5:
                #    heappush(stack, (min((pro - tmp) * D + cost + money, ((pro-1) * next_num2 - tmp) * D + money), next_num2))
        print(money)
if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
def resolve():
    t=int(input())                
    for i in range(t):
        N,A,B,C,D=map(int,input().split())
        memo={}
        for a in range(61):
            for b in range(40):
                for c in range(30):
                    x=(2**a)*(3**b)*(5**c)
                    if x>N:
                        break
                    k=N//x
                    for i in range(2):
                        if k+i in memo.keys():
                            memo[k+i]=min(memo[k+i],a*A+b*B+c*C+abs(N-(k+i)*x)*D)
                            continue
                        else:
                            memo[k+i]=a*A+b*B+c*C+abs(N-(k+i)*x)*D
        memo[1]=min(memo[2]+min(D,A),memo[1])
        memo[0]=memo[1]+D
        print(memo[0])

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
def dist(n):
  if n==0:
    return 0
  if n==1:
    return d
  if n in memo:
    return memo[n]
  
  res=min(
    d*n,
    d*abs(n-n//5*5)+c+dist(n//5),
    d*abs(n-(n+4)//5*5)+c+dist(n//5),
    d*abs(n-n//3*3)+b+dist(n//3),
    d*abs(n-(n+2)//3*3)+b+dist(n//3),
    d*abs(n-n//2*2)+a+dist(n//2),
    d*abs(n-(n+1)//2*2)+a+dist(n//2)
  )
  memo[n]=res
  return res

T=int(input())
for i in range(T):
  n,a,b,c,d=map(int,input().split())
  memo={}
  print(dist(n))

Submission status: Wrong Answer

Solution code:
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:
      return memo[n]

    m2 = n % 2
    m3 = n % 3
    m5 = n % 5 
    ret = min(
      d * n,
      d * m2 + a + f((n - m2) // 2),
      d * m2 + a + f((n + m2) // 2),
      d * m3 + b + f((n - m3) // 3),
      d * (3 - m3) + b + f((n + 3 - m3) // 3),
      d * m5 + c + f((n - m5) // 5),
      d * (3 - m3) + c + f((n + 5 - m5) // 5),
    )
    memo[n] = ret
    return ret
  print(f(n))

Submission status: Wrong Answer

Solution code:
import sys
import math

ceil = math.ceil

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

def f(n, div, cnt):
    global A, B, C, D, dct
    fltmp = n//div
    cltmp = ceil(n/div)
    if fltmp in [0, 1] and cltmp == 1:
        cntfl = cnt + (fltmp==0)*n*D + (fltmp==1)*((div==2)*A + (div==3)*B + (div==5)*C + D)
        cntcl = cnt + abs(n-div*cltmp)*D + (div==2)*A + (div==3)*B + (div==5)*C + D
        if 0 not in dct or dct[0] > cntfl or dct[0] > cntcl:
            dct[0] = min(cntfl, cntcl)
        return
    cntfl = cnt + abs(n-div*fltmp)*D + (div==2)*A + (div==3)*B + (div==5)*C
    cntcl = cnt + abs(n-div*cltmp)*D + (div==2)*A + (div==3)*B + (div==5)*C
    cnt0fl = cntfl + fltmp*D
    cnt0cl = cntcl + cltmp*D
    if 0 not in dct or dct[0] > cnt0fl or dct[0] > cnt0cl:
        dct[0] = min(cnt0cl, cnt0fl)
    if fltmp not in dct or dct[fltmp] > cntfl:
        dct[fltmp] = cntfl
        for divtmp in [2, 3, 5]:
            f(fltmp, divtmp, cntfl)
    if cltmp not in dct or dct[cltmp] > cntcl:
        dct[cltmp] = cntcl
        for divtmp in [2, 3, 5]:
            f(cltmp, divtmp, cntcl)

def main():
    global A, B, C, D, dct
    T = int(input())
    for _ in range(T):
        N, A, B, C, D = map(int, readline().split())
        dct = {N:0}
        for divtmp in [2, 3, 5]:
            f(N, divtmp, 0)
        ans = min(N*D, dct[0])
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

from heapq import heappush, heappop

def calc(N, A, B, C, D):
    abc = [(2, A), (3, B), (5, C)]
    ans = N * D
    ans2 = min(2*D, D+A)

    dq = []

    heappush(dq, (0, N))
    seen = set()
    while dq:
        #print(dq, seen)
        cost, rest = heappop(dq)

        if rest <= 2:
            if rest == 1:
                cost += D
            elif rest == 2:
                cost += ans2
            else:
                cost += -rest * D
            ans = min(ans, cost)
            continue

        if rest in seen:
            continue
        else:
            seen.add(rest)

        if cost >= ans:
            #print(ans, cost, rest)
            continue

        for r, co1 in abc:
            a1, a2 = divmod(rest, r)

            if a2 == 0:
                heappush(dq, (cost+co1, a1))
                continue

            if a2 > r - a2:
                a1 += 1
                a2 = r - a2

            cd = a2 * D
            if (rest - a1) * D < co1 + cd:
                ans = min(ans, rest*D + cost)
            else:
                co2 = cost + co1
                heappush(dq, (co2 + cd, a1))


    return ans


def resolve():
    T = int(input())
    S = [list(iim()) for i in range(T)]


    ans = []
    for s in S:
        ans.append(calc(*s))

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

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
import math

ceil = math.ceil

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

def f(n, div, cnt):
    global A, B, C, D, dct
    fltmp = n//div
    cltmp = ceil(n/div)
    if fltmp in [0, 1] and cltmp == 1:
        cntfl = cnt + n*D
        cntcl = cnt + abs(n-div*cltmp)*D + (div==2)*A + (div==3)*B + (div==5)*C + D
        if 0 not in dct or dct[0] > cntfl or dct[0] > cntcl:
            dct[0] = min(cntfl, cntcl)
        return
    cntfl = cnt + abs(n-div*fltmp)*D + (div==2)*A + (div==3)*B + (div==5)*C
    cntcl = cnt + abs(n-div*cltmp)*D + (div==2)*A + (div==3)*B + (div==5)*C
    cnt0fl = cntfl + fltmp*D
    cnt0cl = cntcl + cltmp*D
    if 0 not in dct or dct[0] > cnt0fl or dct[0] > cnt0cl:
        dct[0] = min(cnt0cl, cnt0fl)
    if fltmp not in dct or dct[fltmp] > cntfl:
        dct[fltmp] = cntfl
        for divtmp in [2, 3, 5]:
            f(fltmp, divtmp, cntfl)
    if cltmp not in dct or dct[cltmp] > cntcl:
        dct[cltmp] = cntcl
        for divtmp in [2, 3, 5]:
            f(cltmp, divtmp, cntcl)

def main():
    global A, B, C, D, dct
    T = int(input())
    for _ in range(T):
        N, A, B, C, D = map(int, readline().split())
        dct = {N:0}
        for divtmp in [2, 3, 5]:
            f(N, divtmp, 0)
        ans = min(N*D, dct[0])
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
from functools import lru_cache
@lru_cache(None)
def dfs(N,A,B,C,D):
    if N == 0: return 0
    if N == 1: return D
    mini = D * N
    mini=min(dfs(math.ceil(N/2),A,B,C,D) + A + (math.ceil(N/2)*2-N) * D,mini)
    mini=min(dfs(math.floor(N/2),A,B,C,D) + A + (N-math.floor(N/2)*2) * D,mini)

    mini=min(dfs(math.ceil(N/3),A,B,C,D) + B + (math.ceil(N/3)*3-N) * D,mini)
    mini=min(dfs(math.floor(N/3),A,B,C,D) + B + (N-math.floor(N/3)*3) * D,mini)

    mini=min(dfs(math.ceil(N/5),A,B,C,D) + C + (math.ceil(N/5)*5-N) * D,mini)
    mini=min(dfs(math.floor(N/5),A,B,C,D) + C + (N-math.floor(N/5)*5) * D,mini)
    
    return mini
i = int(input())
for _ in range(i):
    X,A,B,C,D = map(int,input().split())
    global dic
    dic = {}
    print(dfs(X,A,B,C,D))

Submission status: Wrong Answer

Solution code:
import math
from functools import lru_cache
@lru_cache(None)
def dfs(N,A,B,C,D):
    if N == 0: return 0
    if N == 1: return D
    mini = D * N
    mini=min(dfs(math.ceil(N/2),A,B,C,D) + A + (N%2) * D,mini)
    mini=min(dfs(math.floor(N/2),A,B,C,D) + A + (N%2) * D,mini)

    mini=min(dfs(math.ceil(N/3),A,B,C,D) + B + (N%3) * D,mini)
    mini=min(dfs(math.floor(N/3),A,B,C,D) + B + (3-N%3) * D,mini)

    mini=min(dfs(math.ceil(N/5),A,B,C,D) + C + (N%5) * D,mini)
    mini=min(dfs(math.floor(N/5),A,B,C,D) + C + (5-N%5) * D,mini)
    
    return mini
i = int(input())
for _ in range(i):
    X,A,B,C,D = map(int,input().split())
    global dic
    dic = {}
    print(dfs(X,A,B,C,D))

Submission status: Wrong Answer

Solution code:
import math
from functools import lru_cache
@lru_cache(None)
def dfs(N,A,B,C,D):
    if N == 0: return 0
    if N == 1: return D
    mini = D * N
    mini=min(dfs(math.ceil(N/2),A,B,C,D) + A + (2-N%2) * D,mini)
    mini=min(dfs(math.floor(N/2),A,B,C,D) + A + (N%2) * D,mini)

    mini=min(dfs(math.ceil(N/3),A,B,C,D) + B + (3-N%3) * D,mini)
    mini=min(dfs(math.floor(N/3),A,B,C,D) + B + (N%3) * D,mini)

    mini=min(dfs(math.ceil(N/5),A,B,C,D) + C + (5-N%5) * D,mini)
    mini=min(dfs(math.floor(N/5),A,B,C,D) + C + (N%5) * D,mini)
    
    return mini
i = int(input())
for _ in range(i):
    X,A,B,C,D = map(int,input().split())
    global dic
    dic = {}
    print(dfs(X,A,B,C,D))

Submission status: Wrong Answer

Solution code:
import math
from functools import lru_cache
@lru_cache(None)
def dfs(N,A,B,C,D):
    if N in dic: return dic[N]
    if N == 0: return 0
    if N == 1: return D
    mini = D * N
    mini=min(dfs(math.ceil(N/2),A,B,C,D) + A + (2-N%2) * D,mini)
    mini=min(dfs(math.floor(N/2),A,B,C,D) + A + (N%2) * D,mini)

    mini=min(dfs(math.ceil(N/3),A,B,C,D) + B + (3-N%3) * D,mini)
    mini=min(dfs(math.floor(N/3),A,B,C,D) + B + (N%3) * D,mini)

    mini=min(dfs(math.ceil(N/5),A,B,C,D) + C + (5-N%5) * D,mini)
    mini=min(dfs(math.floor(N/5),A,B,C,D) + C + (N%5) * D,mini)
    
    if mini not in dic:
        dic[N] = mini
    return mini
i = int(input())
for _ in range(i):
    X,A,B,C,D = map(int,input().split())
    global dic
    dic = {}
    print(dfs(X,A,B,C,D))

Submission status: Wrong Answer

Solution code:
import math
from functools import lru_cache
@lru_cache(None)
def dfs(N,A,B,C,D):
    if N in dic: return dic[N]
    if N == 0: return 0
    if N == 1: return D
    (ret1,ret2,ret3,ret4,ret5,ret6,ret7,ret8,ret9)=[10**30 for _ in range(9)]
    if N % 2 == 0: ret1 = dfs(N//2,A,B,C,D) + A
    else:
        ret4 = dfs(math.ceil(N/2),A,B,C,D) + A + (2-N%2) * D
        ret5 = dfs(math.floor(N/2),A,B,C,D) + A + (N%2) * D

    if N % 3 == 0: ret2 = dfs(N//3,A,B,C,D) + B
    else:
        ret7 = dfs(math.ceil(N/3),A,B,C,D) + B + (3-N%3) * D
        ret6 = dfs(math.floor(N/3),A,B,C,D) + B + (N%3) * D

    if N % 5 == 0: ret3 = dfs(N//5,A,B,C,D) + C
    else:
        ret8 = dfs(math.ceil(N/5),A,B,C,D) + C + (5-N%5) * D
        ret9 = dfs(math.floor(N/5),A,B,C,D) + C + (N%5) * D

    ret = min(ret1,ret2,ret3,ret4,ret5,ret6,ret7,ret8,ret9,D*N)

    if ret not in dic:
        dic[N] = ret
    return ret
i = int(input())
for _ in range(i):
    X,A,B,C,D = map(int,input().split())
    global dic
    dic = {}
    print(dfs(X,A,B,C,D))

Submission status: Wrong Answer

Solution code:
import math
from functools import lru_cache
@lru_cache(None)
def dfs(N,A,B,C,D):
    if N in dic: return dic[N]
    if N == 0: return 0
    if N == 1: return D
    mini = D * N
    if N % 2 == 0: mini = min(mini,dfs(N//2,A,B,C,D) + A)
    else: 
        mini=min(dfs(math.ceil(N/2),A,B,C,D) + A + (2-N%2) * D,mini)
        mini=min(dfs(math.floor(N/2),A,B,C,D) + A + (N%2) * D,mini)

    if N % 3 == 0: mini = min(mini,dfs(N//3,A,B,C,D) + B)
    else:
        mini=min(dfs(math.ceil(N/3),A,B,C,D) + B + (3-N%3) * D,mini)
        mini=min(dfs(math.floor(N/3),A,B,C,D) + B + (N%3) * D,mini)

    if N % 5 == 0: mini = min(mini,dfs(N//5,A,B,C,D) + C)
    else:
        mini=min(dfs(math.ceil(N/5),A,B,C,D) + C + (5-N%5) * D,mini)
        mini=min(dfs(math.floor(N/5),A,B,C,D) + C + (N%5) * D,mini)
    
    if mini not in dic:
        dic[N] = mini
    return mini
i = int(input())
for _ in range(i):
    X,A,B,C,D = map(int,input().split())
    global dic
    dic = {}
    print(dfs(X,A,B,C,D))

Submission status: Wrong Answer

Solution code:
import math
from functools import lru_cache
@lru_cache(None)
def dfs(N):
    if N == 0: return 0
    if N == 1: return D
    mini = D * N
    if N % 2 == 0: mini = min(mini,dfs(N//2) + A)
    else: 
        mini=min(dfs(math.ceil(N/2)) + A + (2-N%2) * D,mini)
        mini=min(dfs(math.floor(N/2)) + A + (N%2) * D,mini)

    if N % 3 == 0: mini = min(mini,dfs(N//3) + B)
    else:
        mini=min(dfs(math.ceil(N/3)) + B + (3-N%3) * D,mini)
        mini=min(dfs(math.floor(N/3)) + B + (N%3) * D,mini)

    if N % 5 == 0: mini = min(mini,dfs(N//5) + C)
    else:
        mini=min(dfs(math.ceil(N/5)) + C + (5-N%5) * D,mini)
        mini=min(dfs(math.floor(N/5)) + C + (N%5) * D,mini)
    return mini
i = int(input())
for _ in range(i):
    global A,B,C,D
    X,A,B,C,D = map(int,input().split())
    global dic
    dic = {}
    print(dfs(X))

Submission status: Wrong Answer

Solution code:
def dfs(n):
    global b,check,d
    #ttfは235、chaはabc
    #2,3,5の場合それぞれ
    for ttf,cha in zip([2,3,5],b):
        #-1ずつしていく場合
        if check[0]>check[n]+n*d:
            check[0]=check[n]+n*d

        #最寄りまで-してく場合
        x1,x2=n//ttf,n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)
        if x2==0:
            return
        #最寄りまで+1してく場合
        x1,x2=n//ttf+1,ttf-n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
t=int(input())
@lru_cache(None)#メモ化再帰
def f(x):
	if x<=1:
		return D*x
	ret=D*x

	if x%2==0:
		ret=min(ret,f(x//2)+A)
	else:
		ret=min(ret,f(x//2)+A+D,f(x//2+1)+A+D)
	
	if x%3==0:
		ret=min(ret,f(x//3)+B)
	elif x%3==1:
		ret=min(ret,f(x//3)+B+D)
	else:
		ret=min(ret,f(x//3+1)+B+D)

	if x%5<=2:
		ret=min(ret,f(x//5)+C+D*(x%5))
	else:
		ret=min(ret,f(x//5+1)+C+D*(5-x%5))
	return ret
for _ in range(t):
	n,A,B,C,D=map(int,input().split())
	print(f(n))

Submission status: Wrong Answer

Solution code:
# heapq -> deque

def main():
    from collections import defaultdict, deque

    inf = 10 ** 27 + 1

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

        dq = deque()
        dq.append((0, N))  # cost,value
        checked = defaultdict(lambda: inf)
        checked[N] = 0

        ans = N * D + 1
        while dq:
            cost, x = dq.popleft()
            if cost >= ans: continue
            if cost > checked[x]: continue

            # 0まで1ずつ減らす
            ans = min(ans, cost + x * D)

            for d, c in ((2, A), (3, B), (5, C)):
                nx, r = divmod(x, d)
                if r <= d - r:
                    ncost = cost + r * D + c
                    if checked[nx] > ncost:
                        checked[nx] = ncost
                        dq.append((ncost, nx))
                else:
                    ncost = cost + (d - r) * D + c
                    if checked[nx + 1] > ncost:
                        checked[nx + 1] = ncost
                        dq.append((ncost, nx + 1))

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# heapq -> deque

def main():
    from collections import defaultdict, deque

    inf = 10 ** 27

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

        dq = deque()
        dq.append((0, N))  # cost,value
        checked = defaultdict(lambda: inf)
        checked[N] = 0

        ans = N * D + 1
        while dq:
            cost, x = dq.popleft()
            if cost >= ans: continue
            if cost > checked[x]: continue

            # 0まで1ずつ減らす
            ans = min(ans, cost + x * D)

            for d, c in ((2, A), (3, B), (5, C)):
                nx, r = divmod(x, d)
                if r <= d - r:
                    ncost = cost + r * D + c
                    if checked[nx] > ncost:
                        checked[nx] = ncost
                        dq.append((ncost, nx))
                else:
                    ncost = cost + (d - r) * D + c
                    if checked[nx + 1] > ncost:
                        checked[nx + 1] = ncost
                        dq.append((ncost, nx + 1))

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
memo=dict()
t=int(input())
def f(x):
	if x in memo:
		return memo[x]
	if x<=1:
		return D*x
	ret=D*x

	if x%2==0:
		ret=min(ret,f(x//2)+A)
	else:
		ret=min(ret,f(x//2)+A+D,f(x//2+1)+A+D)
	
	if x%3==0:
		ret=min(ret,f(x//3)+B)
	elif x%3==1:
		ret=min(ret,f(x//3)+B+D)
	else:
		ret=min(ret,f(x//3)+B+D)

	if x%5<=2:
		ret=min(ret,f(x//5)+C+D*(x%5))
	else:
		ret=min(ret,f(x//5)+C+D*(5-x%5))
	memo[x]=ret
	return ret
for _ in range(t):
	memo=dict()
	n,A,B,C,D=map(int,input().split())
	print(f(n))

Submission status: Wrong Answer

Solution code:
# heapq -> deque

def main():
    from collections import defaultdict, deque

    inf = 10 ** 27

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

        dq = deque()
        dq.append((0, N))  # cost,value
        checked = defaultdict(lambda: inf)

        ans = N * D + 1
        while dq:
            cost, x = dq.popleft()
            if cost >= ans: continue
            if cost > checked[x]: continue
            checked[x] = cost

            # 0まで1ずつ減らす
            ans = min(ans, cost + x * D)

            for d, c in ((2, A), (3, B), (5, C)):
                nx, r = divmod(x, d)
                if r <= d - r:
                    ncost = cost + r * D + c
                    if checked[nx] > ncost:
                        checked[nx] = ncost
                        dq.append((ncost, nx))
                else:
                    ncost = cost + (d - r) * D + c
                    if checked[nx + 1] > ncost:
                        checked[nx + 1] = ncost
                        dq.append((ncost, nx + 1))

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# heapq -> deque

def main():
    from collections import defaultdict, deque

    inf = 10 ** 27

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

        dq = deque()
        dq.append((0, N))  # cost,value
        checked = defaultdict(lambda: inf)

        ans = N * D + 1
        while dq:
            cost, x = dq.popleft()
            if cost >= ans: continue
            if cost >= checked[x]: continue
            checked[x] = cost

            # 0まで1ずつ減らす
            ans = min(ans, cost + x * D)

            for d, c in ((2, A), (3, B), (5, C)):
                nx, r = divmod(x, d)
                if r <= d - r:
                    ncost = cost + r * D + c
                    if checked[nx] > ncost:
                        dq.append((ncost, nx))
                else:
                    ncost = cost + (d - r) * D + c
                    if checked[nx + 1] > ncost:
                        dq.append((ncost, nx + 1))

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
check=dict()
#ttfは235、chaはabc

def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if x1 in check:
        if check[x1]>check[n]+x2*d+cha:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)
    else:
        check[x1]=check[n]+x2*d+cha
        dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Submission status: Wrong Answer

Solution code:
def solve(N, A, B, C, D):
    d = {0:0, 1:D}
    s = set()
    return dfs(N, A, B, C, D, d, s)

def dfs(n, A, B, C, D, d, s):
    if n in d:
        return d[n]
    if n in s:
        return float('inf')
    
    s.add(n)
    ans = float('inf')
    
    p = n % 2
    if p == 0:
        ans = min(ans, dfs(n // 2, A, B, C, D, d, s) + A)
    else:
        ans = min(ans, dfs((n - p) // 2, A, B, C, D, d, s) + A + D * p)
        ans = min(ans, dfs((n + (2 - p)) // 2, A, B, C, D, d, s) + A + D * (2 - p))

    q = n % 3
    if q == 0:
        ans = min(ans, dfs(n // 3, A, B, C, D, d, s) + B)
    else:
        ans = min(ans, dfs((n - q) // 3, A, B, C, D, d, s) + B + D * q)
        ans = min(ans, dfs(n + (3 - q), A, B, C, D, d, s) + B + D * (3 - q))
    
    r = n % 5
    if r == 0:
        ans = min(ans, dfs(n // 5, A, B, C, D, d, s) + C)
    else:
        ans = min(ans, dfs((n - r) // 5, A, B, C, D, d, s) + C + D * r)
        ans = min(ans, dfs((n + (5 - r)) // 5, A, B, C, D, d, s) + C + D * (5 - r))
    
    ans = min(ans, D * n)
    
    d[n] = ans
    return ans

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

Submission status: Wrong Answer

Solution code:
import math
import sys
sys.setrecursionlimit(10**9)
T = int(input())

def solve():
    N, A, B, C, D = map(int, input().split())
    memo = {}
    def find(x):
        if x in memo:
            return memo[x]
        if x == 1:
            return D
        if x == 0:
            return 0
        res = D * x
        for y, cost in zip([2, 3, 5], [A, B, C]):
            res = min(res, find(math.floor(x/y))+(abs(x-(math.floor(x/y)*y))*D)+cost)
            res = min(res, find(math.ceil(x/y))+(abs(x-(math.ceil(x/y)*y))*D)+cost)
        memo[x] = res
        return res
    print(find(N))

for t in range(T):
    solve()

Submission status: Wrong Answer

Solution code:
check=dict()
N,z,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    #-1ずつしていく場合
    check[0]=min(check[n]+n*d,check[0])

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

    #最寄りまで+1してく場合
    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global z
    for i,j in z:
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    z=list(zip([2,3,5],b))
    dfs(N)
    print(check[0])