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
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
    if n%ttf<=(ttf//2):
        if n//ttf==0:
            if n//ttf in check:
                if check[n//ttf]>check[n]+(n%ttf)*d:
                    check[n//ttf]=check[n]+(n%ttf)*d
                    dfs(n//ttf,check[n]+(n%ttf)*d)
            else:
                check[n//ttf]=check[n]+(n%ttf)*d
                dfs(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,check[n]+(n%ttf)*d+cha)
            else:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf,check[n]+(n%ttf)*d+cha)
    if n%ttf>(ttf//2) or (ttf==2 and n%ttf==1):
        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,check[n]+(ttf-n%ttf)*d+cha)
        else:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf,check[n]+(ttf-n%ttf)*d+cha)
'''

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


def dfs(n,x):
    global check,a,b,c,d
    if n==1:
        if n-1 in check:
            if check[n-1]>x+d:
                check[n-1]=x+d
        else:
            check[n-1]=x+d
        return
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

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

Submission status: Wrong Answer

Solution code:
import sys
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
    if n%ttf<=(ttf//2):
        if n//ttf==0:
            if n//ttf in check:
                if check[n//ttf]>check[n]+(n%ttf)*d:
                    check[n//ttf]=check[n]+(n%ttf)*d
                    dfs(n//ttf,check[n]+(n%ttf)*d)
            else:
                check[n//ttf]=check[n]+(n%ttf)*d
                dfs(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,check[n]+(n%ttf)*d+cha)
            else:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf,check[n]+(n%ttf)*d+cha)
    if n%ttf>(ttf//2) or (ttf==2 and n%ttf==1):
        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,check[n]+(ttf-n%ttf)*d+cha)
        else:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf,check[n]+(ttf-n%ttf)*d+cha)
'''

def dfs_sub(n,ttf,cha):
    global check,d
    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,check[n]+(n%ttf)*d+cha)
    else:
        check[n//ttf]=check[n]+(n%ttf)*d+cha
        dfs(n//ttf,check[n]+(n%ttf)*d+cha)
    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,check[n]+(ttf-n%ttf)*d+cha)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf,check[n]+(ttf-n%ttf)*d+cha)


def dfs(n,x):
    global check,a,b,c,d
    if n==1:
        if n-1 in check:
            if check[n-1]>x+d:
                check[n-1]=x+d
        else:
            check[n-1]=x+d
        return
    if n==0:
        return
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

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

Submission status: Wrong Answer

Solution code:
import sys
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
    if n%ttf<=(ttf//2):
        if n//ttf==0:
            if n//ttf in check:
                if check[n//ttf]>check[n]+(n%ttf)*d:
                    check[n//ttf]=check[n]+(n%ttf)*d
                    dfs(n//ttf,check[n]+(n%ttf)*d)
            else:
                check[n//ttf]=check[n]+(n%ttf)*d
                dfs(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,check[n]+(n%ttf)*d+cha)
            else:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf,check[n]+(n%ttf)*d+cha)
    if n%ttf>(ttf//2) or (ttf==2 and n%ttf==1):
        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,check[n]+(ttf-n%ttf)*d+cha)
        else:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf,check[n]+(ttf-n%ttf)*d+cha)
'''
def dfs_sub(n,ttf,cha):
    global check,d
    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,check[n]+(n%ttf)*d+cha)
    else:
        check[n//ttf]=check[n]+(n%ttf)*d+cha
        dfs(n//ttf,check[n]+(n%ttf)*d+cha)
    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,check[n]+(ttf-n%ttf)*d+cha)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf,check[n]+(ttf-n%ttf)*d+cha)
'''

def dfs(n,x):
    global check,a,b,c,d
    if n==1:
        if n-1 in check:
            if check[n-1]>x+d:
                check[n-1]=x+d
        else:
            check[n-1]=x+d
    if n==0:
        return
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

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

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
T = int(input())
for _ in range(T):
    N,A,B,C,D = map(int,input().split())
    ch1 = [[[N]*100 for _ in range(100)] for __ in range(100)]
    ch2 = [[[N]*100 for _ in range(100)] for __ in range(100)]
    ch1[0][0][0] = 0
    ch2[0][0][0] = 0
    deq = deque([[N,0,0,0,0]])
    MIN = INF
    while len(deq) != 0:
        n,a,b,c,d = deq.popleft()
        am = n % 2
        n2 = n // 2
        MIN = min(MIN,a*A+b*B+c*C+D*(d+n-1))
        if n2 == 0:
            continue
        if n2 == 1:
            MIN = min(MIN,(a+1)*A+b*B+c*C+D*(d+am))
        else:
            if ch1[a+1][b][c] > d+am:
                ch1[a+1][b][c] = d+am
                deq.append([n2,a+1,b,c,d+am])
            if ch2[a+1][b][c] > d+1:
                ch2[a+1][b][c] = d+1
                deq.append([n2+1,a+1,b,c,d+1])
        bm = n % 3
        n3 = n // 3
        if n3 == 0:
            continue
        if n3 == 1:
            MIN = min(MIN,a*A+(b+1)*B+c*C+D*(d+bm))
        else:
            if ch1[a][b+1][c] > d+bm:
                ch1[a][b+1][c] = d+bm
                deq.append([n3,a,b+1,c,d+bm])
            if ch2[a][b+1][c] > d+1+bm%2:
                ch2[a][b+1][c] = d+1+bm%2
                deq.append([n3+1,a,b+1,c,d+1+bm%2])
        cm = n % 5
        n5 = n // 5
        if n5 == 0:
            continue
        if n5 == 1:
            if cm == 4:
                cmm = 2
            else:
                cmm = cm
            MIN = min(MIN,a*A+b*B+(c+1)*C+D*(d+cmm))
        else:
            if cm <= 2:
                if ch1[a][b][c+1] > d+cm:
                    ch1[a][b][c+1] = d+cm
                    deq.append([n5,a,b,c+1,d+cm])
                if ch2[a][b][c+1] > d+cm+1:
                    ch2[a][b][c+1] = d+cm+1
                    deq.append([n5,a,b,c+1,d+cm+1])
            else:
                if ch1[a][b][c+1] > d+6-cm:
                    ch1[a][b][c+1] = d+6-cm
                    deq.append([n5,a,b,c+1,d+6-cm])
                if ch2[a][b][c+1] > d+5-cm:
                    ch2[a][b][c+1] = d+5-cm
                    deq.append([n5,a,b,c+1,d+5-cm])
    print(MIN+D)

Submission status: Wrong Answer

Solution code:
T = int(input())
for i in range(T):
    n, A, B, C, D = map(int, input().split())
    memo = {}
    
    def herasu(N):
        if N == 0:
            return 0
        if N == 1:
            return D
        if N in memo:
            return memo[N]
        m = 100000000000000000000000
        if N % 2 == 0:
            m = min([m, A + herasu(N//2)])
        else:
            m = min([m, A + herasu(N//2) + D])
            m = min([m, A + herasu(N//2 + 1) + D])
        if N % 3 == 0:
            m = min(m, B + herasu(N//3))
        else:
            m = min([m, B + herasu(N//3) + (B%3) * D])
            m = min([m, B + herasu(N//3 + 1) + (3-(B%3)) * D])
        if N % 5 == 0:
            m = min(m, C + herasu(N // 5))
        else:
            m = min([m, C + herasu(N//5) + (B%5) * D])
            m = min([m, C + herasu(N//5 + 1) + (5-(B%5)) * D])
        m = min([m, D * N])
        memo[N] = m
        return m

    print(herasu(n))

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections
from heapq import *


def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    for _ in range(NI()):
        N,A,B,C,D = LI()

        q = []
        heapify(q)

        memo = {}

        def push(c,n):
            if memo.get(n,INF) > c :
                heappush(q,(c,n))
                memo[n] = c


        push(0,N)

        while q:
            c,n = heappop(q)
            m = [0] * 9
            if n == 1:
                print(c+D)
                break

            if n % 2 == 0:
                push(c+min(A,n//2*D),n//2)
            else:
                m[1] = m[-1] = 1
            if n % 3 == 0:
                push(c+min(B,n//3*2*D),n//3)
                m[n%3] = m[-(n%3)] = 1
            if n % 5 == 0:
                push(c+min(C,n//5*4*D),n//5)
                m[n%5] = m[-(n%5)] = 1
            for i in range(-4,5):
                if m[i] and n+i > 0: push(c+D*abs(i),n+i)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
from functools import lru_cache

T = int(input())


class Resolver:
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    @lru_cache(maxsize=None)
    def resolve(self, n):
        if n == 0:
            return 0
        elif n == 1:
            return self.d
        else:
            div5f = n // 5
            div5c = (n + 4) / 5
            div3f = n // 3
            div3c = (n + 2) / 3
            div2f = n // 2
            div2c = (n + 1) / 2
            return min(
                self.d * n,
                self.d * abs(n - div5f * 5) + self.c + self.resolve(div5f),
                self.d * abs(n - div5c * 5) + self.c + self.resolve(div5c),
                self.d * abs(n - div3f * 3) + self.b + self.resolve(div3f),
                self.d * abs(n - div3c * 3) + self.b + self.resolve(div3c),
                self.d * abs(n - div2f * 2) + self.a + self.resolve(div2f),
                self.d * abs(n - div2c * 2) + self.a + self.resolve(div2c),
            )


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

Submission status: Wrong Answer

Solution code:
import math
from functools import lru_cache

T = int(input())


class Resolver:
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    @lru_cache(maxsize=None)
    def resolve(self, n):
        if n == 0:
            return 0
        elif n == 1:
            return self.d
        else:
            div5f = n // 5
            div5c = math.ceil(n / 5)
            div3f = n // 3
            div3c = math.ceil(n / 3)
            div2f = n // 2
            div2c = math.ceil(n / 2)
            return min(
                self.d * n,
                self.d * abs(n - div5f * 5) + self.c + self.resolve(div5f),
                self.d * abs(n - div5c * 5) + self.c + self.resolve(div5c),
                self.d * abs(n - div3f * 3) + self.b + self.resolve(div3f),
                self.d * abs(n - div3c * 3) + self.b + self.resolve(div3c),
                self.d * abs(n - div2f * 2) + self.a + self.resolve(div2f),
                self.d * abs(n - div2c * 2) + self.a + self.resolve(div2c),
            )


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

Submission status: Wrong Answer

Solution code:
import math
from functools import lru_cache

T = int(input())


class Resolver:
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    @lru_cache(maxsize=None)
    def resolve(self, n):
        if n == 0:
            return 0
        elif n == 1:
            return self.d
        else:
            div5f = math.floor(n / 5)
            div5c = math.ceil(n / 5)
            div3f = math.floor(n / 3)
            div3c = math.ceil(n / 3)
            div2f = math.floor(n / 2)
            div2c = math.ceil(n / 2)
            return min(
                self.d * n,
                self.d * abs(n - div5f * 5) + self.c + self.resolve(div5f),
                self.d * abs(n - div5c * 5) + self.c + self.resolve(div5c),
                self.d * abs(n - div3f * 3) + self.b + self.resolve(div3f),
                self.d * abs(n - div3c * 3) + self.b + self.resolve(div3c),
                self.d * abs(n - div2f * 2) + self.a + self.resolve(div2f),
                self.d * abs(n - div2c * 2) + self.a + self.resolve(div2c),
            )


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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from functools import lru_cache

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

    DP=[N*D]*(10**5)
    DP[0]=0

    for i in range(10**5):
        for k in range(i-10,i+10):
            if 0<=k<10**5 and DP[k]>DP[i]+abs(i-k)*D:
                DP[k]=DP[i]+abs(i-k)*D
        #if 0<=i+1<10**5 and DP[i+1]>DP[i]+D:
        #    DP[i+1]=DP[i]+D
            
        #if 0<=i-1<10**5 and DP[i-1]>DP[i]+D:
        #    DP[i-1]=DP[i]+D

        if 0<=2*i<10**5 and DP[2*i]>DP[i]+A:
            DP[2*i]=DP[i]+A

        if 0<=3*i<10**5 and DP[3*i]>DP[i]+B:
            DP[3*i]=DP[i]+B

        if 0<=5*i<10**5 and DP[5*i]>DP[i]+C:
            DP[5*i]=DP[i]+C

    @lru_cache(maxsize=None)
    def calc(x):
        if x<=10**3:
            return DP[x]

        ANS=x*D

        two=x//2*2

        ANS=min(ANS,abs(two-x)*D+A+calc(two//2))
        ANS=min(ANS,abs(two+2-x)*D+A+calc(two//2+1))

        three=x//3*3
        ANS=min(ANS,abs(three-x)*D+B+calc(three//3))
        ANS=min(ANS,abs(three+3-x)*D+B+calc(three//3+1))

        five=x//5*5
        ANS=min(ANS,abs(five-x)*D+C+calc(five//5))
        ANS=min(ANS,abs(five+5-x)*D+C+calc(five//5+1))

        return ANS

    print(calc(N))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
from functools import lru_cache
from math import ceil as C
t = int(input())
  
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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
from functools import lru_cache
from math import ceil as C

t = int(input())
  
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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
from functools import lru_cache
from math import ceil as C

t = int(input())
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: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


t = I()
for _ in range(t):
    n, a, b, c, d = LI()
    memo = {0: 0, 1: d}
    def dfs(x):
        if x in memo:
            return memo[x]
        ret = x * d
        ret = min(ret, a + dfs(x // 2) + d * (x % 2))
        if (x % 3) < (-x % 3):
            ret = min(ret, b + dfs(x // 3) + d * (x % 3))
        else:
            ret = min(ret, b + dfs((x - 1) // 3 + 1) + d * (-x % 3))
        if (x % 5) < (-x % 5):
            ret = min(ret, c + dfs(x // 5) + d * (x % 5))
        else:
            ret = min(ret, c + dfs((x - 1) // 5 + 1) + d * (-x % 5))

        memo[x] = ret
        return ret

    print(dfs(n))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


t = I()
for _ in range(t):
    n, a, b, c, d = LI()
    memo = {0: 0, 1: d}
    def dfs(x):
        if x in memo:
            return memo[x]
        ret = x * d
        ret = min(ret, a + dfs(x // 2) + d * (x % 2))
        if (x % 3) < (-x % 3):
            ret = min(ret, b + dfs(x // 3) + d * (x % 3))
        else:
            ret = min(ret, b + dfs((x + 1) // 3) + d * (-x % 3))
        if (x % 5) < (-x % 5):
            ret = min(ret, c + dfs(x // 5) + d * (x % 5))
        else:
            ret = min(ret, c + dfs((x + 1) // 5) + d * (-x % 5))

        memo[x] = ret
        return ret

    print(dfs(n))

Submission status: Wrong Answer

Solution code:
def f(k):
    if k==1:return d
    if k==0:return 0
    if k in m:return m[k]
    s=min(k*d,f(k//2)+a+k%2*d,f(--k//2)+a+-k%2*d,f(k//3)+b+k%3*d,f(--k//3)+b+-k%3*d,f(k//5)+c+k%5*d,f(--k//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(f(n))

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):
                    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)
            else:
                if dc[cur//5]>p+c+d*(cur%5):
                    dc[cur//5]=p+c+d*(cur%5)
                    q.append((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 dc[1+cur//3]>p+b+d*(3-cur%3):
                    dc[1+cur//3]>p+b+d*(3-cur%3)
                    q.append((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)
            else:
                if dc[cur//3]>p+b+d*(cur%3):
                    dc[cur//3]>p+b+d*(cur%3)
                    q.append((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)
        else:
            if dc[1+cur//2]>p+a+d*(cur%2):
                dc[1+cur//2]=p+a+d*(2-cur%2)
                q.append((1+cur//2,p+a+d*(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)
        else:
            if dc[cur//2]>p+a+d*(cur%2):
                dc[cur//2]=p+a+d*(cur%2)
                q.append((cur//2,p+a+d*(cur%2)))
        
        
        
        dc[0]=min(dc[0],p+d*cur)
        
    print(dc[0])