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:
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
    #N,A,B,C,D=i
    l2=[0]*3
    lis=i
    num=0
    N=lis[0]
    D=lis[4]
    for j in range(3):
        l2[j]=lis[j+1]
    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
    #N,A,B,C,D=i
    l2=[0]*3
    lis=i
    num=0
    N=lis[0]
    D=lis[4]
    for j in range(3):
        l2[j]=lis[j+1]
    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
    #N,A,B,C,D=i
    lis=[]
    l2=[0]*3
    lis=i
    num=0
    N=lis[0]
    D=lis[4]
    for j in range(3):
        l2[j]=lis[j+1]
    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
def main():
    for i in cases:
        #qappend=q.append
        #N,A,B,C,D=i
        lis=[]
        l2=[0]*3
        lis=i
        N=lis[0]
        D=lis[4]
        for j in range(3):
            l2[j]=lis[j+1]
        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))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from math import ceil,floor,log
from decimal import *
from heapq import *
import sys
def main():
    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
        #N,A,B,C,D=i
        l=[]
        l2=[0]*3
        l=i
        N=l[0]
        D=l[4]
        for j in range(3):
            l2[j]=l[j+1]
        d = {}
        #print(l2)
        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)
                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))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from math import ceil,floor,log
from decimal import *
from heapq import *
import sys
def main():
    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
        N,A,B,C,D=i
        d = {}
        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)
                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(A+((num-(u%num))%num)*D,(u-v1)*D)
                alt2 = d[u] + min(A+(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))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from heapq import heappop,heappush
from collections import defaultdict
t = int(input())
for i in range(t):
  n,a,b,c,d=map(int,input().split())
  q=[(0,n)]
  memo = defaultdict(int)
  while q:
    s,p = heappop(q)
    if memo[p]:
      continue
    memo[p] = 1
    if p == 0:
      print(s)
      return
    heappush(q,(s+d*p,0))
    if p & 1:
      heappush(q,(s+d+a, p//2))
      heappush(q,(s+d+a, p//2+1))
    else:
      heappush(q,(s+a, p//2))
    if p % 3:
      heappush(q,(s+d*(p%3)+b, p//3))
      heappush(q,(s+d*(-p%3)+b, p//3+1))
    else:
      heappush(q,(s+b, p//3))
    if p % 5:
      heappush(q,(s+d*(p%5)+c, p//5))
      heappush(q,(s+d*(-p%5)+c, p//5+1))
    else:
      heappush(q,(s+c, p//5))

Submission status: Runtime Error

Solution code:
def calc(x):
    if x not in dp:
        divs = [5, 3, 2]
        costs = [c, b, a]
        values = lambda div, cost: [calc(x // div) + cost + x % div * d, calc((x + div - 1) // div) + cost + (-x) % div * d]
        dp[x] = min(x * d, *[value for div, cost in zip(divs, costs) for value in values(div, cost)])
    return dp[x]

for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    dp = {0: 0, 1: d}
    print(calc(n))

Submission status: Runtime Error

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
        check[x1]=-1
        if check[x1]>check[n]+x2*d+cha or check[x1]==-1:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

        #最寄りまで+1してく場合
        x1,x2=n//ttf+1,ttf-n%ttf
        check[x1]=-1
        if check[x1]>check[n]+x2*d+cha or check[x1]==-1:
            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: Runtime Error

Solution code:
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc

def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=check[n]+n*d,check[0]
    if n//ttf in check:
        if check[n//ttf]>check[n]+(n%ttf)*d+cha:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    else:
        check[n//ttf]=check[n]+(n%ttf)*d+cha
        dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    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: Runtime Error

Solution code:
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc

def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=check[n]+n*d,check[0]
    if n//ttf in check:
        if check[n//ttf]>check[n]+(n%ttf)*d+cha:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    else:
        check[n//ttf]=check[n]+(n%ttf)*d+cha
        dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global b,check,d
    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}
    dfs(N)
    print(check[0])

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
import copy

def main():
    i = 1
    src = -10
    while True:
        print("? " + "a" * i, flush = True)
        next = int(input())
        if next - src == 1:
            l = src
            break
        else:
            src = next
            
        i += 1

    ALPHA = [i for i in "ABCDEFGHIJKLMNOPQRSTUVWXYZ"]
    alpha = [i for i in "abcdefghijklmnopqrstuvwxyz"]
    num = [i for i in "0123456789"]

    q = []
    for i in (ALPHA + alpha + num):
        print("? " + i * l, flush = True)
        n = int(input())
        if n == l:
            continue
        else:
            heappush(q,(l - n, i))

    first = heappop(q)
    ans = [first[1]] * first[0]

    while len(q) != 0:
        a,w = tuple(heappop(q))
        for i in range(a):
            for j in range(i,len(ans)):
                candidate = ans[:j] + [w] + [j:]
                print("? " + "".join(candidate) ,flush = True)
                n = int(input())
                if n == l - len(ans) - 1:
                    ans = copy.copy(candidate)
                    break
                else:
                    continue

    print("! " + "".join(ans))
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline

check=dict()
N,b,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 check.get(x1) is None:
            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 check.get(x1) is None:
            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,check,d
    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: Runtime Error

Solution code:
import sys
input=sys.stdin.readline

check=dict()
N,b,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,x3=n//ttf,n%ttf,x2*d
    x3=x2*d
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x3:
                    check[x1]=check[n]+x3
            else:
                check[x1]=check[n]+x3
        else:
            if x1 in check:
                if check[x1]>check[n]+x3+cha:
                    check[x1]=check[n]+x3+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x3+cha
                dfs(x1)

    x1,x2,x3=n//ttf+1,ttf-n%ttf,x2*d
    if ttf-x2>x2:
        if x1 in check:
            if check[x1]>check[n]+x3+cha:
                check[x1]=check[n]+x3+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x3+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    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: Runtime Error

Solution code:
from functools import lru_cache

T = int(input())

caseList = []

for i in range(T):
    caseList.append(list(map(int, input().split())))


@lru_cache(maxsize=None)
def solve(n, A, B, C, D):
    if n == 0:
        return 0
    if n == 1:
        return D
    if n == 2:
        return min(D + D, A + D)

    ans = n * D

    for num, cost in zip([2, 3, 5], [A, B, C]):
        ans = min(
            f((n + (num - n % num)) // num, A, B, C, D) + cost + D * (num - n % num),
            f((n - n % num) // num, A, B, C, D) + cost + D * (n % num),
            ans,
        )

    return ans


for N, A, B, C, D in caseList:
    print(solve(N, A, B, C, D))

Submission status: Runtime Error

Solution code:
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check.get(0))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf),check[n]+(n%ttf)*d)
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


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}
    dfs(N)
    print(check[0])

Submission status: Runtime Error

Solution code:
import heapq
import numpy as np

t = int(input())

for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    # x to lowest coin
    cheapest = dict()
    # (coin, x)
    search = [(d, 1)]
    first = True

    while 1:
        coin, x = heapq.heappop(search)

        if (x > 1 or first) and x not in cheapest:
            first = False
            if x == n:
                print(coin)
                break
            cheapest[x] = coin

            heapq.heappush(search, (coin + a, 2 * x))
            heapq.heappush(search, (coin + b, 3 * x))
            heapq.heappush(search, (coin + c, 5 * x))
            heapq.heappush(search, (coin + d, x + 1))
            if x - 1 > 1:
                heapq.heappush(search, (coin + d, x - 1))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
from functools import lru_cache
from math import ceil as C
  
for _ in range(t):
    n,a,b,c,d = map(int,input().split())
    @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(C(k/2))+a+-k%2*d,f(k//3)+b+k%3*d,f(C(k/3))+b+-k%3*d,f(k//5)+c+k%5*d,f(C(k/5))+c+-k%5*d)
    print(f(n))

Submission status: Runtime Error

Solution code:
T = int(input())

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

    def dist(n):
        if n == 0:
            return 0
        if n in memo:
            return memo[n]
        
        ret = min(
            D * n,
            D * abs(n - n//5*5) + C + dist(n//5),
            D * abs(n - (n+4)//5*5) + C + dist((n+4)//5),
            D * abs(n - n//3*3) + B + dist(n//3),
            D * abs(n - (n+2)//3*3) + B + dist((n+2)//3),
            D * abs(n - n//2*2) + A + dist(n//2),
            D * abs(n - (n+1)//2*2) + A + dist((n+1)//2)
        )

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

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
P = np.array([int(c)-1 for c in input().split()])
def proc(N, P):
    ans = 0
    Removed = np.zeros((500, 500), dtype=np.int8)
    Mat = np.zeros((500, 500), dtype=np.int16)
    Dy, Dx = [1,0,-1,0], [0,1,0,-1]
 
    for y in range(N):
        for x in range(N):
            Mat[y, x] = min(y, N-1-y, x, N-1-x)
    #print(Mat)
    for i in range(N*N):
        p = P[i]
        y, x = divmod(p, N)
        ans += Mat[y,x]
        Removed[y,x] = 1
        st = [(y, x)]
        while st:
            vy, vx = st.pop()
            vr = Removed[vy,vx]
            val = Mat[vy,vx]
            #for dy, dx in zip(Dy, Dx):
            for j in range(4):
                dy,dx = Dy[j],Dx[j]
                uy = vy + dy
                ux = vx + dx
                if not (0<=uy<N and 0<=ux<N):
                    continue
                ur = Removed[uy,ux]
                if vr:
                    if Mat[uy,ux] >= val+1:
                        Mat[uy,ux] = val
                        st.append((uy, ux))
                else:
                    if Mat[uy,ux] >= val+2:
                        Mat[uy,ux] = val+1
                        st.append((uy, ux))
    # for m in Mat:
    #     print(m)
    print(ans)
proc(N, P)

Submission status: Runtime Error

Solution code:
import numba
import numpy as np
N = int(input())
P = np.array([int(c)-1 for c in input().split()])
 
#from random import shuffle
#N = 500
#P = list(range(N*N))
#shuffle(P)
#P = np.array(P)
 
@numba.njit("void(i8,i8[:])")
def proc(N, P):
    ans = 0
    Removed = np.zeros((500, 500), dtype=np.int8)
    Mat = np.zeros((500, 500), dtype=np.int16)
    Dy, Dx = [1,0,-1,0], [0,1,0,-1]
 
    for y in range(N):
        for x in range(N):
            Mat[y, x] = min(y, N-1-y, x, N-1-x)
    #print(Mat)
    for i in range(N*N):
        p = P[i]
        y, x = divmod(p, N)
        ans += Mat[y,x]
        Removed[y,x] = 1
        st = [(y, x)]
        while st:
            vy, vx = st.pop()
            vr = Removed[vy,vx]
            val = Mat[vy,vx]
            #for dy, dx in zip(Dy, Dx):
            for j in range(4):
                dy,dx = Dy[j],Dx[j]
                uy = vy + dy
                ux = vx + dx
                if not (0<=uy<N and 0<=ux<N):
                    continue
                ur = Removed[uy,ux]
                if vr:
                    if Mat[uy,ux] >= val+1:
                        Mat[uy,ux] = val
                        st.append((uy, ux))
                else:
                    if Mat[uy,ux] >= val+2:
                        Mat[uy,ux] = val+1
                        st.append((uy, ux))
    # for m in Mat:
    #     print(m)
    print(ans)
proc(N, P)

Submission status: Runtime Error

Solution code:
def f(k):
    if k==1:return d
    if k==0:return 0
    if k in dic:return m[k]
    s=k*d
    s=min(s,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)
    m[k]=s
    return s
for _ in range(int(input())):
    m={}
    n,a,b,c,d=map(int,input().split())
    print(s(n))

Submission status: Runtime Error

Solution code:
n=int(input())
x=list(map(int,input().split()))
num=[]
num2=[]
ans=[]
count=0
numcount=0
numcount2=0
yn=0
for i in range(n):
    x[i]=[i+1,x[i]]
str1= lambda val: val[1]
x.sort(key=str1)
for i in range(n):
    num+=[x[i][0]]*((x[i][0])-1)
for i in range(n):
    num2+=[x[i][0]]*(n-(x[i][0]))
for i in range(n*n):
    if count<n:
        if x[count][1]==i+1:
            if ans.count(str(x[count][0]))!=(x[count][0])-1:
                yn=1
                break
            else:
                ans+=str(x[count][0])
            count+=1
        else:
            if numcount<len(num):
                ans+=str(num[numcount])
                numcount+=1
            elif numcount2<len(num2):
                ans+=str(num2[numcount2])
                numcount2+=1
            else:
                yn=1
                break
    else:
        if numcount<len(num):
            ans+=str(num[numcount])
            numcount+=1
        else:
            ans+=str(num2[numcount2])
            numcount2+=1
if yn==1:
    print("No")
else:
    print("Yes")
    print(*ans)

Submission status: Runtime Error

Solution code:

def estimateZeroToFive(A, B, C, D):
    List = [0] * 7
    List[1] = D
    List[2] = min(A+D, 2 * D)
    List[3] = min(3*D, List[2] + D, List[1] + B)
    List[6] = min(6*D, List[2] + B, List[3] + A, C+2*D)
    List[4] = min(4*D, List[2] + A, List[3] + D, 2*D+C, List[2]+B+2*D)
    List[5] = min(5*D, List[1] + C, List[4] + D, List[6] + D, List[2]+B+D )

    return List

def queue(Queue_CostValue):
    Values = Queue_CostValue.pop(0)
    return Values

def OneTurn(A, B, C, D, Costs_ZeroToFive, Acchieved, Queue_CostValue_Turns):
    while(len(Queue_CostValue_Turns)>0):

        CostValue = queue(Queue_CostValue_Turns)

        Cost = CostValue[0]
        Value = CostValue[1]
        CostMin = Acchieved[0]
        Flag = True
        if(Cost > CostMin):
            Flag = False
        elif(Value <= 6):
            Cost += Costs_ZeroToFive[Value]
            if(Cost < CostMin):
                Acchieved[0] = Cost
                Flag = False
        if(Flag==True):
            if(Value %5 ==0):
                Queue_CostValue_Turns.append([Cost+C, Value//5 ])
            if(Value%3 == 0):
                Queue_CostValue_Turns.append([Cost+B, Value//3 ])
            if(Value%2==0):
                Queue_CostValue_Turns.append([Cost+A, Value//2 ])

            Queue_CostValue_Turns.append([Cost+D, Value+1])
            Queue_CostValue_Turns.append([Cost+D, Value-1])
            OneTurn(A, B, C, D, Costs_ZeroToFive, Acchieved, Queue_CostValue_Turns)


def OneTurn2(A, B, C, D, Costs_ZeroToFive, Acchieved, Queue_CostValue_Turns):
    while(len(Queue_CostValue_Turns)>0):

        CostValue = queue(Queue_CostValue_Turns)

        Cost = CostValue[0]
        Value = CostValue[1]
        Turns = CostValue[2]
        CostMin = Acchieved[0]
        Flag = True
        if(Cost > CostMin):
            Flag = False
        elif(Value <= 6):
            Cost += Costs_ZeroToFive[Value]
            if(Cost < CostMin):

                Acchieved[0] = Cost

                if(len(Acchieved)==1):
                    Acchieved.append(Turns)
                else:
                    Acchieved[1]=Turns
                Flag = False
        if(Flag==True):
            if(Value %5 ==0):
                Queue_CostValue_Turns.append([Cost+C, Value//5, Turns+"C" ])
            if(Value%3 == 0):
                Queue_CostValue_Turns.append([Cost+B, Value//3, Turns+"B" ])
            if(Value%2==0):
                Queue_CostValue_Turns.append([Cost+A, Value//2, Turns+"A" ])

            Queue_CostValue_Turns.append([Cost+D, Value+1, Turns+"D+"])
            Queue_CostValue_Turns.append([Cost+D, Value-1, Turns+"D-"])
            OneTurn2(A, B, C, D, Costs_ZeroToFive, Acchieved, Queue_CostValue_Turns)


if(__name__ == "__main__"):
    T = int( input().strip() )
    #T = 1
    NABCDList =[]
    for Num in range(T):
        StrList = input().strip().split()
        for m in range( len(StrList) ):
            N = int(StrList[0])
            A = int(StrList[1])
            B = int(StrList[2])
            C = int(StrList[3])
            D = int(StrList[4])

        Costs_ZeroToFive= estimateZeroToFive(A, B, C, D)
        Acchieved = [N*D]
        # print("0-6: ", Costs_ZeroToFive)
        # OneTurn2(A, B, C, D, Costs_ZeroToFive, Acchieved, [ [0, N, ""] ])
        OneTurn(A, B, C, D, Costs_ZeroToFive, Acchieved, [ [0, N] ])
        print(Acchieved[0])
        #estimatemin(N, A, B, C, D, N, Min, 0)
        #print(Min)

        #estimatemin(N, A, B, C, D, Value, Min, Coin_Used = 0):