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: Runtime Error

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 RA():return map(int,open(0).read().split())
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)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
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.st=SegTree(self.size*2-1,self.ETdepth,function=min,ide=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

def solve(n,a,b,c,d):
    q=[(0,n)]
    dc=dict()
    used=dict()
    used[n]=1
    while q:
        dist,cr=heappop(q)
        nbs=[(a+d*(cr%2),cr//2),(a+d*(cr%2),1+cr//2),(d*cr,0)]
        r=c%3
        if r*d+b<r*(3-d)+b:
            nbs+=[(r*d+b,cr//3)]
        else:
            nbs+=[(r*(3-d)+b,1+cr//3)]
        r=c%5
        if r*d+c<r*(5-d)+c:
            nbs+=[(r*d+c,cr//5)]
        else:
            nbs+=[(r*(5-d)+c,1+cr//5)]
        
        for nd,nb in nbs:
            if nb in used:
                continue
            if nb not in dc:
                heappush(q,(nd+dist,nb))
            elif dc[nb]>nd+dist:
                heappush(q,(nd+dist,nb))
                dc[nb]=nd+dist
                used[nb]=1
            if nb==0:
                break
        show(q,used)
    return dc[0]

t,*x=map(int,open(0).read().split());N=1<<21;a=[0]*N;b=0
for i in range(t):
    ans=solve(*x[i*5:i*5+5])
    print(ans)



show(x)

Submission status: Runtime Error

Solution code:
t = int(input())
a, b, c, d = [0, 0, 0, 0]
flag = False
mn = 0
memo = []

def solve(n):
    global a,b,c,d
    global flag
    global mn
    global memo
    if n == 0: mn = min(mn, n)
    if n in memo: return
    memo.append(n)
    if n % 2 == 0: solve(n // 2 + a)
    if n % 3 == 0: solve(n // 3 + b)
    if n % 5 == 0: solve(n // 5 + c)
    solve(n + d - 1)
    solve(n + d + 1)


for i in range(t):
    mn = 10 ** 18
    n,a,b,c,d = [int(i) for i in input().split()]
    memo = []
    solve(n)
    print(mn)

Submission status: Runtime Error

Solution code:
from collections import deque,defaultdict
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 = deque([[n,0]])
        self.memory = defaultdict(int) # 実績を記録、すでにその値より低いコストでやっていたら除外する
    def dfs(self):
        while self.Q:
            # from IPython.core.debugger import Pdb; Pdb().set_trace()
            num,cost = self.Q.popleft()
            # 小さいコストのキューが積まれていた場合は処理しない（後ろのキューで処理をする）
            if memory[num] <= cost:
                pass
            else:
                if num == 0:
                    self.ans = min(self.ans, cost)
                elif num == 1:
                    self.ans = min(self.ans, cost + self.D * num)
                else:
                    # 5の倍数に上げて5で割った場合
                    temp_num = num//5 + 1
                    temp_cost = cost + ((num//5 + 1) * 5 - num) * self.D + self.C
                    if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                        self.memory[temp_num] = temp_cost
                        self.Q.appendleft([temp_num,temp_cost])

                    # 5の倍数に下げて5で割った場合
                    temp_num = num//5
                    temp_cost = cost + (num - (num//5)*5) * self.D + self.C
                    if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                        self.memory[temp_num] = temp_cost
                        self.Q.appendleft([temp_num,temp_cost])

                    # 3の倍数に上げて3で割った場合
                    temp_num = num//3 + 1
                    temp_cost = cost + ((num//3 + 1) * 3 - num) * self.D + self.B
                    if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                        self.memory[temp_num] = temp_cost
                        self.Q.appendleft([temp_num,temp_cost])

                    # 3の倍数に下げて3で割った場合
                    temp_num = num//3
                    temp_cost = cost + (num - (num//3)*3) * self.D + self.B
                    if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                        self.memory[temp_num] = temp_cost
                        self.Q.appendleft([temp_num,temp_cost])

                    # 2の倍数に上げて2で割った場合
                    temp_num = num//2 + 1
                    temp_cost = cost + ((num//2 + 1) * 2 - num) * self.D + self.A
                    if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                        self.memory[temp_num] = temp_cost
                        self.Q.appendleft([temp_num,temp_cost])

                    # 2の倍数に下げて2で割った場合
                    temp_num = num//2
                    temp_cost = cost + (num - (num//2)*2) * self.D + self.A
                    if self.memory[temp_num] == 0 or self.memory[temp_num] > cost:
                        self.memory[temp_num] = temp_cost
                        self.Q.appendleft([temp_num,temp_cost])

                    # 全て引いた場合
                    self.ans = min(self.ans, num*self.D + cost)
                
        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: Runtime Error

Solution code:
[n], *e = [[*map(int, t.split())] for t in open(0)]
viewers = set(range(1, n**2 + 1))
mem = {x: min((x - 1) % n, (n - x) % n, (x - 1)//n, n - 1 - (x - 1)//n)
       for x in range(1, n**2 + 1)}

ans = 0


def directions(x):
    tmp = []
    if x % n != 1:
        tmp.append(x - 1)
    if x % n > 0:
        tmp.append(x + 1)
    if (x - 1)//n > 0:
        tmp.append(x - n)
    if (x - 1)//n < n - 1:
        tmp.append(x + n)
    return tmp


for x in e[0]:

    def bfs(x):
        queue = [x]
        while queue:
            tmp = queue.pop(0)
            z = mem[tmp] + (tmp in viewers)
            for k in directions(tmp):
                if mem[k] > z:
                    mem[k] = z
                    queue.append(k)

    ans += mem[x]
    viewers.remove(x)
    bfs(x)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000)

[n], *e = [[*map(int, t.split())] for t in open(0)]
viewers = set(range(1, n**2 + 1))
mem = {x: min((x - 1) % n, (n - x) % n, (x - 1)//n, n - 1 - (x - 1)//n)
       for x in range(1, n**2 + 1)}


def directions(x):
    tmp = []
    if x % n != 1:
        tmp.append(x - 1)
    if x % n > 0:
        tmp.append(x + 1)
    if (x - 1)//n > 0:
        tmp.append(x - n)
    if (x - 1)//n < n - 1:
        tmp.append(x + n)
    return tmp


ans = 0

for x in e[0]:

    def fill(x):
        z = mem[x] + (x in viewers)
        for k in directions(x):
            if mem[k] > z:
                mem[k] = z
                fill(k)

    ans += mem[x]
    viewers.remove(x)
    fill(x)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000)

[n], *e = [[*map(int, t.split())] for t in open(0)]
viewers = set(range(1, n**2 + 1))
mem = {x: min((x - 1) % n, (n - x) % n, (x - 1)//n, n - 1 - (x - 1)//n)
       for x in range(1, n**2 + 1)}


def directions(x):
    tmp = []
    if x % n != 1:
        tmp.append(x - 1)
    if x % n > 0:
        tmp.append(x + 1)
    if (x - 1)//n > 0:
        tmp.append(x - n)
    if (x - 1)//n < n - 1:
        tmp.append(x + n)
    return tmp

ans = 0

for x in e[0]:

    def fill(x):
        z = mem[x] + (x in viewers)
        for k in directions(x):
            if mem[k] > z:
                mem[k] = z
                fill(k)

    ans += mem[x]
    viewers.remove(x)
    fill(x)
    display()

print(ans)

Submission status: Runtime Error

Solution code:
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 = deque([[n,0]])
    def dfs(self):
        while self.Q:
            num,cost = self.Q.popleft()
            if num == 0:
                self.ans = min(self.ans, cost)
            elif num == 1:
                self.ans = min(self.ans, cost + self.D * num)
            else:
                # 5の倍数に下げて5で割った場合
                temp_num = num//5
                temp_cost = cost + (num - (num//5)*5) * self.D + self.C
                self.Q.appendleft([temp_num,temp_cost])
                
                # 3の倍数に下げて3で割った場合
                temp_num = num//3
                temp_cost = cost + (num - (num//3)*3) * self.D + self.B
                self.Q.appendleft([temp_num,temp_cost])
                
                # 2の倍数に下げて2で割った場合
                temp_num = num//2
                temp_cost = cost + (num - (num//2)*2) * self.D + self.A
                self.Q.appendleft([temp_num,temp_cost])
                
                # 全て引いた場合
                self.ans = min(self.ans, num*self.D + cost)
                
        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: Runtime Error

Solution code:
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 = deque([[n,0]])
    def dfs(self):
        while self.Q:
            num,cost = self.Q.popleft()
            if num == 0:
                self.ans = min(self.ans, cost)
            elif num == 1:
                self.ans = min(self.ans, cost + self.D * num)
            else:
                # 5の倍数に上げて5で割った場合
                temp_num = num//5 + 1
                temp_cost = cost + ((num//5 + 1) * 5 - num) * self.D + self.C
                self.Q.appendleft([temp_num,temp_cost])
                
                # 5の倍数に下げて5で割った場合
                temp_num = num//5
                temp_cost = cost + (num - (num//5)*5) * self.D + self.C
                self.Q.appendleft([temp_num,temp_cost])
                
                # 3の倍数に上げて3で割った場合
                temp_num = num//3 + 1
                temp_cost = cost + ((num//3 + 1) * 3 - num) * self.D + self.B
                self.Q.appendleft([temp_num,temp_cost])
                
                # 3の倍数に下げて3で割った場合
                temp_num = num//3
                temp_cost = cost + (num - (num//3)*3) * self.D + self.B
                self.Q.appendleft([temp_num,temp_cost])
                    
                # 2の倍数に上げて2で割った場合
                temp_num = num//2 + 1
                temp_cost = cost + ((num//2 + 1) * 2 - num) * self.D + self.A
                self.Q.appendleft([temp_num,temp_cost])
                
                # 2の倍数に下げて2で割った場合
                temp_num = num//2
                temp_cost = cost + (num - (num//2)*2) * self.D + self.A
                self.Q.appendleft([temp_num,temp_cost])
                
                # 全て引いた場合
                self.ans = min(self.ans, num*self.D + cost)
                
        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: Runtime Error

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())
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]))
    answer.append(pay.coin)
for i in range(0, T):
    print(answer[i])

Submission status: Runtime Error

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 = 0
    
  def solution(self, temp:int, cointemp:int, op):
    if op == 'a':
      cointemp=cointemp + self.a
    else if op == 'b':
      cointemp=cointemp + self.b
    else if op == 'c':
      cointemp=cointemp + self.c
    else if op == 'd':
      cointemp=cointemp + self.d
    if temp == self.n:
      if cointemp < self.coin or self.coin ==0:
        self.coin ==cointemp
      return self.coin
    if (self.coin>0 and cointemp > self.coin) or cointemp > self.d*self.n:
      return self.coin
    self.solution(temp+1, cointemp, 'd')
    self.solution(temp*2, cointemp, 'a')
    self.solution(temp*3, cointemp, 'b')
    self.solution(temp*5, cointemp, 'c')
    self.solution(temp-1, cointemp, 'a')

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

Submission status: Runtime Error

Solution code:
T=int(input())
for i in range(T):
  N,a,b,c,d=map(int, input().split())
  memo={}
  memo[0]=0
  memo[1]=d
  
  def f(n):
    if n in memo:
      return memo[n]
    e2,e3,e5=n%2,n%3,n%5
    dd=min(d*n,d*2+a+f((n-e2)//2),d*2+a+f((n+e2)//2),d*e3+b+f((n-e3)//3),d*(3-e3)+b+f((n+3-e3)//3),d*e5+c+f((n-e5)//5),d*(5-e5)+c+f((n+5-e5)//5))
    memo[n]=dd
    return dd
  print(f(n))

Submission status: Runtime Error

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(ceil(log(N,2))):         #2の累乗
        for k in range(ceil(log(N,3))):     #3の累乗
            for l in range(ceil(log(N,5))): #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)
    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: Runtime Error

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 i in range(ceil(log(N,2))):         #2の累乗
        for j in range(ceil(log(N,3))):     #3の累乗
            for k in range(ceil(log(N,5))): #5の累乗
                div=pow(2,i)*pow(3,j)*pow(5,k)
                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)
    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: Runtime Error

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=20
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 i in range(ceil(log(N,2))):         #2の累乗
        for j in range(ceil(log(N,3))):     #3の累乗
            for k in range(ceil(log(N,5))): #5の累乗
                div=pow(2,i)*pow(3,j)*pow(5,k)
                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)
    while len(q)>0:
        dist,u=heappop(q)
        if d[u]<dist: continue
        for j in range(3):
            num=i+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: Runtime Error

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 = 20
for i in cases:
    #qappend=q.append
    l2=[0]*3
    N,l2[0],l2[1],l2[2],D=i
    num=0
    d = {}
    #print(l2)
    for j in range(ceil(log(N,2))):         #2の累乗
        for k in range(ceil(log(N,3))):     #3の累乗
            for l in range(ceil(log(N,5))): #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)
    while len(q)>0:
        dist,u=heappop(q)
        if d[u]<dist: continue
        for j in range(3):
            num=1+pow(2,j)
            const=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(const+((num-(u%num))%num)*D,(u-v1)*D)
            alt2 = d[u] + min(const+(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: Runtime Error

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 = 18
for i in cases:
    #qappend=q.append
    l2=[0]*3
    N,l2[0],l2[1],l2[2],D=i
    num=0
    d = {}
    #print(l2)
    for j in range(ceil(log(N,2))):         #2の累乗
        for k in range(ceil(log(N,3))):     #3の累乗
            for l in range(ceil(log(N,5))): #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)
    while len(q)>0:
        dist,u=heappop(q)
        if d[u]<dist: continue
        for j in range(3):
            num=1+pow(2,j)
            const=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(const+((num-(u%num))%num)*D,(u-v1)*D)
            alt2 = d[u] + min(const+(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))