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,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def __str__(self):
        return  str(self.edges)
 
    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)

show_flg=False
show_flg=True
ans=0


T=I()
for _ in range(T):
    n,a,b,c,d=LI()
    dc=defaultdict(int)
    dc[0]=inf
    q=[(n,0)]
    while q:
        cur,p=q.pop()
        if cur%5>2:
            if 1+cur//5 not in dc:
                q.append((1+cur//5,p+c+d*(5-cur%5)))
                dc[1+cur//5]=p+c+d*(5-cur%5)
            else:
                if dc[1+cur//5]>p+c+d*(5-cur%5):
                    q.append((1+cur//5,p+c+d*(5-cur%5)))
        else:
            if cur//5 not in dc:
                q.append((cur//5,p+c+d*(cur%5)))
                dc[cur//5]=p+c+d*(cur%5)
        
        if cur%3>1:
            if 1+cur//3 not in dc:
                q.append((1+cur//3,p+b+d*(3-cur%3)))
                dc[1+cur//3]=p+b+d*(3-cur%3)
        else:
            if cur//3 not in dc:
                q.append((cur//3,p+b+d*(cur%3)))
                dc[cur//3]=p+b+d*(cur%3)
        

        if 1+cur//2 not in dc:
            q.append((1+cur//2,p+a+d*(cur%2)))  
            dc[1+cur//2]=p+a+d*(2-cur%2)

        if cur//2 not in dc:
            q.append((cur//2,p+a+d*(cur%2)))
            dc[cur//2]=p+a+d*(cur%2)
        
        
        
        dc[0]=min(dc[0],p+d*cur)
        
    print(dc[0])

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
import math


def solve(N, A, B, C, D):

    @lru_cache(None)
    def dfs(n):  # n -> 0 になるまでのコスト
        if n == 0:
            return 0
        if n == 1:
            return D

        cost = n * D

        for div, c in zip((2, 3, 5), (A, B, C)):
            m = n % div
            if m == 0:
                cost = min(cost, dfs(n // div) + c)
            else:
                cost = min(cost, dfs(math.floor(n / div)) + c + D * m)
                cost = min(cost, dfs(math.ceil(n / div)) + c + D * (div - m))

        return cost

    return dfs(N)


def main():
    T = int(input())

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
@lru_cache(None)
def f(k):
    if k==1:return d
    if k==0:return 0
    return min(k*d,f(k//2)+a+k%2*d,f((k+1)//2)+a+-k%2*d,f(k//3)+b+k%3*d,f((k+2)//3)+b+-k%3*d,f(k//5)+c+k%5*d,f((k+4)//5)+c+-k%5*d)
for _ in range(int(input())):
    n,a,b,c,d=map(int,input().split())
    print(f(n))

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
from math import floor,ceil

@lru_cache(maxsize=10**18)
def f(n,A,B,C,D):
    if n==0:
        return 0
    elif n==1:
        return D
    else:
        M=[]
        M.append(g(n,2,A,A,B,C,D))
        M.append(h(n,2,A,A,B,C,D))
        M.append(g(n,3,B,A,B,C,D))
        M.append(h(n,3,B,A,B,C,D))
        M.append(g(n,5,C,A,B,C,D))
        M.append(h(n,5,C,A,B,C,D))
        return min(M)

def g(x,p,K,A,B,C,D):
    u=ceil(x/p)
    return f(u,A,B,C,D)+K+abs(x-u*p)*D

def h(x,p,K,A,B,C,D):
    u=floor(x/p)
    return f(u,A,B,C,D)+K+abs(x-u*p)*D

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

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
from math import floor, ceil


def solve(N, A, B, C, D):

    @lru_cache(None)
    def dfs(n):  # n -> 0 になるまでのコスト
        if n == 0:
            return 0
        if n == 1:
            return D

        cost = n * D

        for div, c in zip((2, 3, 5), (A, B, C)):
            m = n % div
            if m == 0:
                cost = min(cost, dfs(n // div) + c)
            else:
                cost = min(cost, dfs(floor(n / div)) + c + D * m)
                cost = min(cost, dfs(ceil(n / div)) + c + D * (div - m))

        return cost

    return dfs(N)


def main():
    T = int(input())

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
t=int(input())
INF=10**19
def dfs(k):
    if k==1:return d
    if k==0:return 0
    if k in dic:return dic[k]
    ans=INF
    ans=min(ans,dfs(k//2)+a+k%2*d,dfs((k+1)//2)+a+-k%2*d,dfs(k//3)+b+k%3*d,dfs((k+2)//3)+b+-k%3*d,dfs(k//5)+c+k%5*d,dfs((k+4)//5)+c+-k%5*d)
    dic[k]=ans
    return ans
for _ in range(t):
    dic={}
    n,a,b,c,d=map(int,input().split())
    print(dfs(n))

Submission status: Wrong Answer

Solution code:
def helper(N):
    if dic.get(N) != None: return dic[N]
    res = min(float("inf"), N*D)
    for i in range(-1,2):
        if (N+i) % 2 == 0:
            res = min(res, helper((N+i)/2)+A+D*abs(i))

    for i in range(-2,3):
        if (N+i) % 3 == 0:
            res = min(res, helper((N+i)/3)+B+D*abs(i))

    for i in range(-4,5):
        if (N+i) % 5 == 0:
            res = min(res, helper((N+i)/5)+C+D*abs(i))
    dic[N] = res
    return res

T = int(input())
while T > 0:
   N, A, B, C, D = map(int,input().split())
   dic = {1:D, 0:0}
   print(helper(N))
   T -= 1

Submission status: Wrong Answer

Solution code:
def helper(N:int):
    if dic.get(N) != None: return dic[N]
    res = min(float("inf"), N*D)
    for i in range(-1,2):
        if (N+i) % 2 == 0:
            res = min(res, helper((N+i)/2)+A+D*abs(i))

    for i in range(-2,3):
        if (N+i) % 3 == 0:
            res = min(res, helper((N+i)/3)+B+D*abs(i))

    for i in range(-4,5):
        if (N+i) % 5 == 0:
            res = min(res, helper((N+i)/5)+C+D*abs(i))
    dic[N] = res
    return res

T = int(input())
while T > 0:
   N, A, B, C, D = map(int,input().split())
   dic = {1:D, 0:0}
   print(helper(N))
   T -= 1

Submission status: Wrong Answer

Solution code:
T=int(input())
from functools import lru_cache
@lru_cache(maxsize=None)  
def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D,solve((N+1)//2)+A+D)
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    else:
        b=N%3 
        tmp=min(tmp,solve((N+(3-b))//3)+B+(3-b)*D,solve((N-b)//3)+B+b*D)
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    else:
        c=N%5
        tmp=min(tmp,solve((N-c)//5)+C+D*c,solve((N+(5-c))//5)+C+D*(5-c))
    return tmp

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

Submission status: Wrong Answer

Solution code:
def helper(N:int):
    if dic.get(N) != None: return dic[N]
    res = min(float("inf"), N*D)
    for i in range(-1,2):
        if (N+i) % 2 == 0:
            res = min(res, helper((N+i)/2)+A+(D*abs(i) if i != 0 else 0))

    for i in range(-1,2):
        if (N+i) % 3 == 0:
            res = min(res, helper((N+i)/3)+B+(D*abs(i) if i != 0 else 0))

    for i in range(-2,3):
        if (N+i) % 5 == 0:
            res = min(res, helper((N+i)/5)+C+(D*abs(i) if i != 0 else 0))
    dic[N] = res
    return res

T = int(input())
while T > 0:
   N, A, B, C, D = map(int,input().split())
   dic = {1:D, 0:0}
   print(helper(N))
   T -= 1

Submission status: Wrong Answer

Solution code:
def helper(N:int):
    if dic.get(N) != None: return dic[N]
    res = float("inf")
    if N == 1: res = D
    for i in range(-1,2):
        if (N+i) % 2 == 0:
            res = min(res, helper((N+i)/2)+A+(D*abs(i) if i != 0 else 0))

    for i in range(-1,2):
        if (N+i) % 3 == 0:
            res = min(res, helper((N+i)/3)+B+(D*abs(i) if i != 0 else 0))

    for i in range(-2,3):
        if (N+i) % 5 == 0:
            res = min(res, helper((N+i)/5)+C+(D*abs(i) if i != 0 else 0))
    dic[N] = res
    return res

T = int(input())
while T > 0:
   N, A, B, C, D = map(int,input().split())
   dic = {1:D, 0:0}
   print(helper(N))
   T -= 1

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
T=int(input())
from functools import lru_cache
@lru_cache(maxsize=None)  
def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D,solve((N+1)//2)+A+D)
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    else:
        b=N%3 
        tmp=min(tmp,solve((N+(3-b))//3)+B+(3-b)*D,solve((N-b)//3)+B+b*D)
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    else:
        c=N%5
        tmp=min(tmp,solve((N-c)//5)+C+D*c,solve((N+(5-c))//5)+C+D*(5-c))
    return tmp

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

Submission status: Wrong Answer

Solution code:
def helper(N:int):
    if dic.get(N) != None: return dic[N]
    res = float("inf")
    if N == 1: res = D
    for i in range(-1,2):
        if (N+i) % 2 == 0:
            res = min(res, helper((N+i)/2)+A+(D*abs(i) if i != 0 else 0))

    for i in range(-2,3):
        if (N+i) % 3 == 0:
            res = min(res, helper((N+i)/3)+B+(D*abs(i) if i != 0 else 0))

    for i in range(-4,5):
        if (N+i) % 5 == 0:
            res = min(res, helper((N+i)/5)+C+(D*abs(i) if i != 0 else 0))
    dic[N] = res
    return res

T = int(input())
while T > 0:
   N, A, B, C, D = map(int,input().split())
   dic = {1:D, 0:0}
   print(helper(N))
   T -= 1

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
T=int(input())
import functools
@functools.lru_cache(maxsize=None)  
def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D,solve((N+1)//2)+A+D)
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    else:
        b=N%3 
        tmp=min(tmp,solve((N+(3-b))//3)+B+(3-b)*D,solve((N-b)//3)+B+b*D)
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    else:
        c=N%5
        tmp=min(tmp,solve((N-c)//5)+C+D*c,solve((N+(5-c))//5)+C+D*(5-c))
    return tmp

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
import functools
T=int(input())
@functools.lru_cache(maxsize=None)
def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D,solve((N+1)//2)+A+D)
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    else:
        b=N%3 
        tmp=min(tmp,solve((N+(3-b))//3)+B+(3-b)*D,solve((N-b)//3)+B+b*D)
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    else:
        c=N%5
        tmp=min(tmp,solve((N-c)//5)+C+D*c,solve((N+(5-c))//5)+C+D*(5-c))
    return tmp

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

Submission status: Wrong Answer

Solution code:
def helper(N:int, A:int, B:int, C:int, D:int, cost:int):
    if N <= 0: return
    for j in range(-4, 5):
        for i in range(3):
            if j >= table[i]: break
            if N + j == 0: 
                global ans
                ans = min(ans, cost+D*abs(j))
                return
            if (N+j) % table[i] == 0:
                helper((N+j)/table[i], A, B, C, D, cost+cost_v[i]+(D*abs(j) if j != 0 else 0))
            
table = [2, 3, 5]
cost_v = [1, 2, 4]
T = int(input())
while T > 0:
   N, A, B, C, D = map(int,input().split())
   cost_v[0], cost_v[1], cost_v[2] = A, B, C
   ans = float("inf")
   helper(N,A,B,C,D,0)
   print(ans)
   T -= 1

Submission status: Wrong Answer

Solution code:
def helper(N:int, A:int, B:int, C:int, D:int, cost:int):
    if N <= 0: return
    for j in range(-4, 5):
        for i in range(3):
            if j >= table[i]: break
            if (N+j) % table[i] == 0:
                helper((N+j)/table[i], A, B, C, D, cost+cost_v[i]+(D*abs(j) if j != 0 else 0))
            if N + j == 0: 
                global ans
                ans = min(ans, cost+D*abs(j))
                return
table = [2, 3, 5]
cost_v = [1, 2, 4]
T = int(input())
while T > 0:
   N, A, B, C, D = map(int,input().split())
   cost_v[0], cost_v[1], cost_v[2] = A, B, C
   ans = float("inf")
   helper(N,A,B,C,D,0)
   print(ans)
   T -= 1

Submission status: Wrong Answer

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)


memo = {}

def solve():
    N,A,B,C,D = map(int,input().split())
    return process(N,N,A,B,C,D)


def process(M,N,A,B,C,D):
    if M == 1:
        return D
    elif M == 0:
        return 0
    elif M < 0:
        return D * N
    global memo
    if M in memo:
        return memo[M]
    res = process((M-M%2)//2,N,A,B,C,D) + A + (M%2) * D
    res = min(res,process((M+M%2)//2,N,A,B,C,D) + A + (M%2) * D)
    res = min(res,process((M-M%3)//3,N,A,B,C,D) + B + (M%3) * D)
    res = min(res,process((M+3-M%3)//3,N,A,B,C,D) + B + (3-M%3) * D)
    res = min(res,process((M-M%5)//5,N,A,B,C,D) + C + (M%5) * D)
    res = min(res,process((M+5-M%5)//5,N,A,B,C,D) + C + (5-M%5) * D)
    memo[M] = res
    return res


def main():
    T = int(input())

    for i in range(T):
        global memo
        memo = {}
        res = solve()
        print(res)



main()

Submission status: Wrong Answer

Solution code:
t=int(input())
for _ in range(t):
    n,a,b,c,d=map(int,input().split())
    l=[n*d]
    for i in range(61):
        for j in range(40):
            for k in range(30):
                
                aa=n/(2**i*3**j*5**k)
                if aa!=0 and aa%1!=0:
                    a1=aa//1+1
                    a2=aa//1
                    b1=a1*2**i*3**j*5**k
                    b2=a2*2**i*3**j*5**k
                    l.append(min((b1-n)*d+a*i+b*j+c*k+a1*d,(n-b2)*d+a*i+b*j+c*k+a2*d))
                elif aa!=0 and aa%1==0:
                    
                    a1=aa+1
                    a2=aa-1
                    a3=aa
                    b1=a1*2**i*3**j*5**k
                    b2=a2*2**i*3**j*5**k
                    b3=a3*2**i*3**j*5**k
                    l.append(min((b1-n)*d+a*i+b*j+c*k+a1*d,(n-b2)*d+a*i+b*j+c*k+a2*d,a*i+b*j+c*k+a3*d))
                    

    
    print(int(min(l)))

Submission status: Wrong Answer

Solution code:
def helper(N:int, A:int, B:int, C:int, D:int, cost:int):
    if N <= 0: return
    for j in range(-4, 5):
        for i in range(3):
            if (N+j) % table[i] == 0:
                helper((N+j)/table[i], A, B, C, D, cost+cost_v[i]+(D*abs(j) if j != 0 else 0))
            if N + j == 0: 
                global ans
                ans = min(ans, cost+D*abs(j))
                return
table = [2, 3, 5]
cost_v = [1, 2, 4]
T = int(input())
while T > 0:
   N, A, B, C, D = map(int,input().split())
   cost_v[0], cost_v[1], cost_v[2] = A, B, C
   ans = float("inf")
   helper(N,A,B,C,D,0)
   print(ans)
   T -= 1

Submission status: Wrong Answer

Solution code:
T = int(input())

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

from math import ceil
from functools import lru_cache

@lru_cache(maxsize=None)
def f(n,a,b,c,d):
    if n == 0:
        return 0
    if n == 1:
        return d
    else:
        return min((n-5*(n//5)) * d + c + f(n//5,a,b,c,d),(n-3*(n//3)) * d + b + f(n//3,a,b,c,d),(n-2*(n//2)) * d + a + f(n//2,a,b,c,d),
                   (5*ceil(n/5)-n) * d + c + f(ceil(n/5),a,b,c,d),(3*ceil(n/3)-n) * d + b + f(ceil(n/3),a,b,c,d),(2*ceil(n/2)-n) * d + a + f(ceil(n/2),a,b,c,d),n*d)

for n,a,b,c,d in testcase:
    print(f(n,a,b,c,d))

Submission status: Wrong Answer

Solution code:
def helper(N:int, A:int, B:int, C:int, D:int, cost:int):
    if N <= 0: return
    for j in range(-1, 2):
        for i in range(3):
            if N + j == 0: 
                global ans
                ans = min(ans, cost+D)
                return
            if (N+j) % table[i] == 0:
                helper((N+j)/table[i], A, B, C, D, cost+cost_v[i]+(D if j != 0 else 0))

table = [2, 3, 5]
cost_v = [1, 2, 4]
T = int(input())
while T > 0:
   N, A, B, C, D = map(int,input().split())
   cost_v[0], cost_v[1], cost_v[2] = A, B, C
   ans = float("inf")
   helper(11,1,2,4,8,0)
   print(ans)
   T -= 1

Submission status: Wrong Answer

Solution code:
inf = 2 << 63
import math
def ans(N,A,B,C,D):
    log2 = math.ceil(math.log(N,2))
    log3 = math.ceil(math.log(N,3))
    log5 = math.ceil(math.log(N,5))
    res = inf
    cost = inf
    for c2 in range(log2):
        for c3 in range(log3):
            for c5 in range(log5):
                temp = 2 ** c2 * 3 **c3 * 5 ** c5
                cost2 = abs(temp -N) * D +c2 *A + c3 *B + c5 * C
                if cost > cost2:
                    cost = cost2
    print(cost + D)
def main():
    T = int(input())
    NABCD = [list(map(int,input().split()))for _ in range(T)]
    for data in NABCD:
        ans(*data)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    if N in dic:
        return dic[N]
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D,solve((N+1)//2)+A+D)
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    else:
        b=N%3 
        tmp=min(tmp,solve((N+(3-b))//3)+B+D,solve((N-b)//3)+B+(N-b)*D)
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    else:
        c=N%5
        tmp=min(tmp,solve((N-c)//5)+C+D*c,solve((N+(5-c))//5)+C+D*(5-c))
    dic[N]=tmp
    return tmp

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

Submission status: Wrong Answer

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

def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    if N in dic:
        return dic[N]
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D,solve((N+1)//2)+A+D)
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    else:
        b=N%3 
        tmp=min(tmp,solve((N+(3-b))//3)+B+D,solve((N-b)//3)+B+2*D)
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    else:
        c=N%5
        tmp=min(tmp,solve((N-c)//5)+C+D*c,solve((N+(5-c))//5)+C+D*(5-c))
    dic[N]=tmp
    return tmp

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from typing import Callable, NoReturn


def bfs(n: int, a: int, b: int, c: int, d: int) -> int:
  queue = deque([(1,d)])
  
  while queue:
    num, coins = queue.popleft()  # type: int, int
    
    if n == num:
      return coins
    
    queue.append((num * 2, coins + a))
    queue.append((num * 3, coins + b))
    queue.append((num * 5, coins + c))
    
    
def main() -> NoReturn:
  readline: Callable[[], str] = sys.stdin.readline
  
  t = int(readline().rstrip())
  
  for _ in range(t):
    n, a, b, c, d = map(int, readline().rstrip().split())  # type: int,...
    print(bfs(n, a, b, c, d))
    
    
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    if N in dic:
        return dic[N]
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D)
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    else:
        b=N%3 
        tmp=min(tmp,solve((N+(3-b))//3)+B+D,solve((N-b)//3)+B+2*D)
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    else:
        c=N%5
        tmp=min(tmp,solve((N-c)//5)+C+D*c,solve((N+(5-c))//5)+C+D*(5-c))
    dic[N]=tmp
    return tmp

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

Submission status: Wrong Answer

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

def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    if N in dic:
        return dic[N]
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D)
    b=N%3 
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    else:
        tmp=min(tmp,solve((N+(3-b))//3)+B+D,solve((N-b)//3)+B+2*D)
    c=N%5
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    else:
        tmp=min(tmp,solve((N-c)//5)+C+D*c,solve((N+(5-c))//5)+C+D*(5-c))
    dic[N]=tmp
    return tmp

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

Submission status: Wrong Answer

Solution code:
N = int(input())
BorG = input()
S = ""

if BorG == "B" and N >= 2000:
  S = "un"

elif BorG == "G" and N < 2000:
  S = "un"

print(S + "rated")

Submission status: Wrong Answer

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

def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    if N in dic:
        return dic[N]
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D)
    b=N%3 
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    elif b==1:
        tmp=min(tmp,solve((N-1)//3)+B+D)
    else:
        tmp=min(tmp,solve((N+1)//3)+B+D)
    c=N%5
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    elif c==1 or c==2:
        tmp=min(tmp,solve((N-c)//5)+C+D*c)
    else:
        c=5-c
        tmp=min(tmp,solve((N+c)//5)+C+D*c)
    dic[N]=tmp
    return tmp

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

Submission status: Wrong Answer

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

def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    if N in dic:
        return dic[N]
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D)
    b=N%3 
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    elif b==1:
        tmp=min(tmp,solve((N-1)//3)+B+D)
    else:
        tmp=min(tmp,solve((N+1)//3)+B+D)
    c=N%5
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    elif c==1 or c==2:
        tmp=min(tmp,solve((N-c)//5)+C+D*c)
    else:
        c=5-c
        tmp=min(tmp,solve((N+c)//5)+C+D*c)
    dic[N]=tmp
    return tmp

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