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 math
import sys
sys.setrecursionlimit(10**9)
T = int(input())

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

for t in range(T):
    solve()

Submission status: Wrong Answer

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

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

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

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

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


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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
import math
T = int(input())

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

for t in range(T):
    solve()

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
from math import ceil,floor
import sys
sys.setrecursionlimit(10**7)
t=int(input())
for _ in range(t):
    memo=dict()
    n,a,b,c,d=map(int,input().split())
    def dfs(x):
        if x==0:
            return 0
        if x==1:
            return d
        if x in memo:
            return memo[x]
        l2=2*floor(x/2)
        r2=2*ceil(x/2)
        l3=3*floor(x/3)
        r3=3*ceil(x/3)
        l5=5*floor(x/5)
        r5=5*ceil(x/5)
        mini=d*x
        mini=min(mini,abs(l2-x)*d+a+dfs(l2//2))
        mini=min(mini,abs(r2-x)*d+a+dfs(r2//2))
        mini=min(mini,abs(l3-x)*d+b+dfs(l3//3))
        mini=min(mini,abs(r3-x)*d+b+dfs(r3//3))
        mini=min(mini,abs(l5-x)*d+c+dfs(l5//5))
        mini=min(mini,abs(r5-x)*d+c+dfs(r5//5))
        memo[x]=mini
        return mini
    print(dfs(n))

Submission status: Wrong Answer

Solution code:
from math import ceil
import sys
sys.setrecursionlimit(10**7)
t=int(input())
for _ in range(t):
    memo=dict()
    n,a,b,c,d=map(int,input().split())
    def dfs(x):
        if x==0:
            return 0
        if x==1:
            return d
        if x in memo:
            return memo[x]
        l2=2*(x//2)
        r2=2*ceil(x/2)
        l3=3*(x//3)
        r3=3*ceil(x/3)
        l5=5*(x//5)
        r5=5*ceil(x/5)
        mini=d*x
        mini=min(mini,abs(l2-x)*d+a+dfs(l2//2))
        mini=min(mini,abs(r2-x)*d+a+dfs(r2//2))
        mini=min(mini,abs(l3-x)*d+b+dfs(l3//3))
        mini=min(mini,abs(r3-x)*d+b+dfs(r3//3))
        mini=min(mini,abs(l5-x)*d+c+dfs(l5//5))
        mini=min(mini,abs(r5-x)*d+c+dfs(r5//5))
        memo[x]=mini
        return mini
    print(dfs(n))

Submission status: Wrong Answer

Solution code:
from functools import *
from math import *

t = int(input())

@lru_cache(maxsize=None)
def sol(n, a, b, c, d):
    if n == 1: return d
    ans = n * d
    cn = ceil(n / 2)
    fn = floor(n / 2)
    if cn: ans = min(ans, sol(cn, a, b, c, d) + abs(cn * 2 - n) * d + a)
    if fn: ans = min(ans, sol(fn, a, b, c, d) + abs(fn * 2 - n) * d + a)
    cn = ceil(n / 3)
    fn = floor(n / 3)
    if cn: ans = min(ans, sol(cn, a, b, c, d) + abs(cn * 3 - n) * d + b)
    if fn: ans = min(ans, sol(fn, a, b, c, d) + abs(fn * 3 - n) * d + b)
    cn = ceil(n / 5)
    fn = floor(n / 5)
    if cn: ans = min(ans, sol(cn, a, b, c, d) + abs(cn * 5 - n) * d + c)
    if fn: ans = min(ans, sol(fn, a, b, c, d) + abs(fn * 5 - n) * d + c)
    # print(str(n) + ", " + str(ans))
    return ans

for _ in range(t):
    n, a, b, c, d = list(map(int, input().split()))
    sol.cache_clear()
    print(min(d * n, sol(n, a, b, c, d)))

Submission status: Wrong Answer

Solution code:
from math import ceil
import sys
sys.setrecursionlimit(10**7)
t=int(input())
for _ in range(t):
    memo=dict()
    n,a,b,c,d=map(int,input().split())
    def dfs(x):
        if x==0:
            return 0
        if x==1:
            return d
        if x in memo:
            return memo[x]
        l2=2*(x//2)
        r2=2*ceil(x/2)
        l3=3*(x//3)
        r3=3*ceil(x/3)
        l5=5*(x//5)
        r5=5*ceil(x/5)
        mini=d*x
        mini=min(mini,abs(l2-x)*d+a+dfs(x//2))
        mini=min(mini,abs(r2-x)*d+a+dfs(ceil(x/2)))
        mini=min(mini,abs(l3-x)*d+b+dfs(x//3))
        mini=min(mini,abs(r3-x)*d+b+dfs(ceil(x/3)))
        mini=min(mini,abs(l5-x)*d+c+dfs(x//5))
        mini=min(mini,abs(r5-x)*d+c+dfs(ceil(x/5)))
        memo[x]=mini
        return mini
    print(dfs(n))

Submission status: Wrong Answer

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

T=int(input())
for i in range(T):
    solve()

Submission status: Wrong Answer

Solution code:
from math import floor,ceil
import sys
sys.setrecursionlimit(10**7)
def solve():
    N,A,B,C,D=map(int,input().split())
    memo={}
    def rec(x):
        if x in memo:
            return memo[x]
        if x==1:
            return D
        if x==0:
            return 0
        res=min(
            D*x,
            D*abs(x-ceil(x/2)*2)+A+rec(ceil(x/2)),
            D*abs(x-floor(x/2)*2)+A+rec(floor(x/2)),
            D*abs(x-ceil(x/3)*3)+B+rec(ceil(x/3)),
            D*abs(x-floor(x/3)*3)+B+rec(floor(x/3)),
            D*abs(x-ceil(x/5)*5)+C+rec(ceil(x/5)),
            D*abs(x-floor(x/5)*5)+C+rec(floor(x/5))
        )
        memo[x]=res
        return res
    print(rec(N))

T=int(input())
for i in range(T):
    solve()

Submission status: Wrong Answer

Solution code:
from math import floor,ceil
import sys
sys.setrecursionlimit(10**7)
def solve():
    N,A,B,C,D=map(int,input().split())
    memo={}
    def rec(x):
        if memo.get(x,None)!=None:
            return memo[x]
        if x==1:
            return D
        if x==0:
            return 0
        res=D*x
        for y,cost in zip([2,3,5],[A,B,C]):
            c,f=ceil(x/y),floor(x/y)
            res=min(res,rec(c)+cost+abs(x-c*y)*D)
            res=min(res,rec(f)+cost+abs(x-f*y)*D)
        memo[x]=res
        return res
    print(rec(N))

T=int(input())
for i in range(T):
    solve()

Submission status: Wrong Answer

Solution code:
from math import ceil
import sys
sys.setrecursionlimit(10**7)
memo=dict()
def dfs(x,a,b,c,d):
    if x==0:
        return 0
    if x==1:
        return d
    if x in memo:
        return memo[x]
    l2=2*(x//2)
    r2=2*ceil(x/2)
    l3=3*(x//3)
    r3=3*ceil(x/3)
    l5=5*(x//5)
    r5=5*ceil(x/5)
    mini=d*x
    mini=min(mini,abs(l2-x)*d+a+dfs(x//2,a,b,c,d))
    mini=min(mini,abs(r2-x)*d+a+dfs(ceil(x/2),a,b,c,d))
    mini=min(mini,abs(l3-x)*d+b+dfs(x//3,a,b,c,d))
    mini=min(mini,abs(r3-x)*d+b+dfs(ceil(x/3),a,b,c,d))
    mini=min(mini,abs(l5-x)*d+c+dfs(x//5,a,b,c,d))
    mini=min(mini,abs(r5-x)*d+c+dfs(ceil(x/5),a,b,c,d))
    memo[x]=mini
    return mini
t=int(input())
for _ in range(t):
    memo=dict()
    n,a,b,c,d=map(int,input().split())
    print(dfs(n,a,b,c,d))

Submission status: Wrong Answer

Solution code:
from math import ceil
import sys
sys.setrecursionlimit(10**7)
memo=dict()
def dfs(x,a,b,c,d):
    if x==0:
        return 0
    if x==1:
        return d
    if x in memo:
        return memo[x]
    l2=2*(x//2)
    r2=2*ceil(x/2)
    l3=3*(x//3)
    r3=3*ceil(x/3)
    l5=5*(x//5)
    r5=5*ceil(x/5)
    mini=10**18
    if x<mini//d:
        mini=d*x
    mini=min(mini,abs(l2-x)*d+a+dfs(x//2,a,b,c,d))
    mini=min(mini,abs(r2-x)*d+a+dfs(ceil(x/2),a,b,c,d))
    mini=min(mini,abs(l3-x)*d+b+dfs(x//3,a,b,c,d))
    mini=min(mini,abs(r3-x)*d+b+dfs(ceil(x/3),a,b,c,d))
    mini=min(mini,abs(l5-x)*d+c+dfs(x//5,a,b,c,d))
    mini=min(mini,abs(r5-x)*d+c+dfs(ceil(x/5),a,b,c,d))
    memo[x]=mini
    return mini
t=int(input())
for _ in range(t):
    memo=dict()
    n,a,b,c,d=map(int,input().split())
    print(dfs(n,a,b,c,d))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(20000)

times = int(input())
n, a, b, c, d = list(), list(), list(), list(), list()
for t in range(times):
    x = list(map(int, input().split()))
    n.append(x[0])
    a.append(x[1])
    b.append(x[2])
    c.append(x[3])
    d.append(x[4])


def f(N):
    if N == 0:
        return 0
    if N == 1:
        return D
    if N in dic:
        return dic[N]

    if N%2 == 0:
        N2 = f(N // 2) + A
    elif N%2 == 1:
        N2 = min(f((N-1) // 2), f((N+1) // 2)) + A + D

    if N%3 == 0:
        N3 = f(N // 3) + B
    elif N%3 == 1:
        N3 = min(f((N-1) // 3), f((N+1) // 3)) + B + D
    elif N%3 == 2:
        N3 = min(f((N-2) // 3), f((N+2) // 3)) + B + 2*D

    if N%5 == 0:
        N5 = f(N // 5) + C
    elif N%5 == 1:
        N5 = min(f((N-1) // 5), f((N+1) // 5)) + C + D
    elif N%5 == 2:
        N5 = min(f((N-2) // 5), f((N+2) // 5)) + C + 2*D
    elif N%5 == 3:
        N5 = min(f((N-3) // 5), f((N+3) // 5)) + C + 3*D
    elif N%5 == 4:
        N5 = min(f((N-4) // 5), f((N+4) // 5)) + C + 4*D

    Y = min(N2, N3, N5, N*D)
    dic[N] = Y
    return Y


for t in range(times):
    N, A, B, C, D = n[t], a[t], b[t], c[t], d[t]
    dic = {}
    print(f(N))

Submission status: Wrong Answer

Solution code:
t = int(input())

import sys
sys.setrecursionlimit(10 ** 6)

def calc(x):
    if x in dp:
        return dp[x]
    
    res = d * x
    if x >= 5:
        res = min(res, calc(x//5) + c + x%5 * d)
    if x > 5:
        res = min(res, calc(x//5+1) + c + (5-x%5) * d)
    if x >= 3:
        res = min(res, calc(x//3) + b + x%3 * d)
    if x > 3:
        res = min(res, calc(x//3+1) + b + (3-x%3) * d)
    if x >= 2:
        res = min(res, calc(x//2) + a + x%2 * d)
    if x > 2:
        res = min(res, calc(x//2+1) + a + x%2 * d)
    dp[x] = res
    return res

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

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**7)
@lru_cache(maxsize=None)
def dfs(x):
    if x == 0:
        return 0
    if x == 1:
        return d
    l2 = x//2
    r2 = (x+1)//2
    l3 = x//3
    r3 = (x+2)//3
    l5 = x//5
    r5 = (x+4)//5
    count = x*d
    count = min(count,abs(l2*2-x)*d+a+dfs(l2))
    count = min(count,abs(r2*2-x)*d+a+dfs(r2))
    count = min(count,abs(l3*3-x)*d+b+dfs(l3))
    count = min(count,abs(r3*3-x)*d+b+dfs(r3))
    count = min(count,abs(l5*5-x)*d+c+dfs(l5))
    count = min(count,abs(r5*5-x)*d+c+dfs(r5))
    return count

t = int(input())
for _ in range(t):
    n,a,b,c,d = map(int,input().split())
    print(dfs(n))

Submission status: Wrong Answer

Solution code:
from math import ceil
import sys
sys.setrecursionlimit(10**7)
memo=dict()
def dfs(x,a,b,c,d):
    if x==0:
        return 0
    if x==1:
        return d
    if x in memo:
        return memo[x]
    l2=2*(x//2)
    r2=2*ceil(x/2)
    l3=3*(x//3)
    r3=3*ceil(x/3)
    l5=5*(x//5)
    r5=5*ceil(x/5)
    mini=float("inf")
    mini=min(d*x,mini)
    mini=min(mini,abs(l2-x)*d+a+dfs(x//2,a,b,c,d))
    mini=min(mini,abs(r2-x)*d+a+dfs(ceil(x/2),a,b,c,d))
    mini=min(mini,abs(l3-x)*d+b+dfs(x//3,a,b,c,d))
    mini=min(mini,abs(r3-x)*d+b+dfs(ceil(x/3),a,b,c,d))
    mini=min(mini,abs(l5-x)*d+c+dfs(x//5,a,b,c,d))
    mini=min(mini,abs(r5-x)*d+c+dfs(ceil(x/5),a,b,c,d))
    memo[x]=mini
    return mini
t=int(input())
for _ in range(t):
    memo=dict()
    n,a,b,c,d=map(int,input().split())
    print(dfs(n,a,b,c,d))

Submission status: Wrong Answer

Solution code:
from math import ceil
import sys
sys.setrecursionlimit(10**7)
memo=dict()
def dfs(x,a,b,c,d):
    if x==0:
        return 0
    if x==1:
        return d
    if x in memo:
        return memo[x]
    l2=2*(x//2)
    r2=2*ceil(x/2)
    l3=3*(x//3)
    r3=3*ceil(x/3)
    l5=5*(x//5)
    r5=5*ceil(x/5)
    mini=float("inf")
    mini=min(d*n,mini)
    mini=min(mini,abs(l2-x)*d+a+dfs(x//2,a,b,c,d))
    mini=min(mini,abs(r2-x)*d+a+dfs(ceil(x/2),a,b,c,d))
    mini=min(mini,abs(l3-x)*d+b+dfs(x//3,a,b,c,d))
    mini=min(mini,abs(r3-x)*d+b+dfs(ceil(x/3),a,b,c,d))
    mini=min(mini,abs(l5-x)*d+c+dfs(x//5,a,b,c,d))
    mini=min(mini,abs(r5-x)*d+c+dfs(ceil(x/5),a,b,c,d))
    memo[x]=mini
    return mini
t=int(input())
for _ in range(t):
    memo=dict()
    n,a,b,c,d=map(int,input().split())
    print(dfs(n,a,b,c,d))

Submission status: Wrong Answer

Solution code:
from math import ceil
import sys
sys.setrecursionlimit(10**7)
memo=dict()
def dfs(x,a,b,c,d):
    if x==0:
        return 0
    if x==1:
        return d
    if x in memo:
        return memo[x]
    l2=2*(x//2)
    r2=2*ceil(x/2)
    l3=3*(x//3)
    r3=3*ceil(x/3)
    l5=5*(x//5)
    r5=5*ceil(x/5)
    mini=10**18
    mini=min(d*x,mini)
    mini=min(mini,abs(l2-x)*d+a+dfs(x//2,a,b,c,d))
    mini=min(mini,abs(r2-x)*d+a+dfs(ceil(x/2),a,b,c,d))
    mini=min(mini,abs(l3-x)*d+b+dfs(x//3,a,b,c,d))
    mini=min(mini,abs(r3-x)*d+b+dfs(ceil(x/3),a,b,c,d))
    mini=min(mini,abs(l5-x)*d+c+dfs(x//5,a,b,c,d))
    mini=min(mini,abs(r5-x)*d+c+dfs(ceil(x/5),a,b,c,d))
    memo[x]=mini
    return mini
t=int(input())
for _ in range(t):
    memo=dict()
    n,a,b,c,d=map(int,input().split())
    print(dfs(n,a,b,c,d))

Submission status: Wrong Answer

Solution code:
from math import ceil
import sys
sys.setrecursionlimit(10**7)
memo=dict()
def dfs(x,a,b,c,d):
    if x==0:
        return 0
    if x==1:
        return d
    if x in memo:
        return memo[x]
    l2=2*(x//2)
    r2=2*ceil(x/2)
    l3=3*(x//3)
    r3=3*ceil(x/3)
    l5=5*(x//5)
    r5=5*ceil(x/5)
    mini=10**18
    mini=min(mini,abs(l2-x)*d+a+dfs(x//2,a,b,c,d))
    mini=min(mini,abs(r2-x)*d+a+dfs(ceil(x/2),a,b,c,d))
    mini=min(mini,abs(l3-x)*d+b+dfs(x//3,a,b,c,d))
    mini=min(mini,abs(r3-x)*d+b+dfs(ceil(x/3),a,b,c,d))
    mini=min(mini,abs(l5-x)*d+c+dfs(x//5,a,b,c,d))
    mini=min(mini,abs(r5-x)*d+c+dfs(ceil(x/5),a,b,c,d))
    memo[x]=mini
    return mini
t=int(input())
for _ in range(t):
    memo=dict()
    n,a,b,c,d=map(int,input().split())
    print(dfs(n,a,b,c,d))

Submission status: Wrong Answer

Solution code:
# Problem A - Pay to Win

import math

# input
T = int(input())

# initialization
dict = {}

def dfs(n, a, b, c, d, coin):
    # stop condition
    if n==0:
        return 0
    if n==1:
        return d

    # memory process
    if n in dict:
        return dict[n]

    # process 1
    tmp_1 = d * n

    # process 2
    tmp_2 = d * abs(n - math.floor(n/5)*5) + c + dfs(math.floor(n/5), a, b, c, d, coin)

    # process 3
    tmp_3 = d * abs(math.ceil(n/5)*5 - n) + c + dfs(math.ceil(n/5), a, b, c, d, coin)

    # process 4
    tmp_4 = d * abs(n - math.floor(n/3)*3) + b + dfs(math.floor(n/3), a, b, c, d, coin)

    # process 5
    tmp_5 = d * abs(math.ceil(n/3)*3 - n) + b + dfs(math.ceil(n/3), a, b, c, d, coin)

    # process 6
    tmp_6 = d * abs(n - math.floor(n/2)*2) + a + dfs(math.floor(n/2), a, b, c, d, coin)

    # process 7
    tmp_7 = d * abs(math.ceil(n/2)*2 - n) + a + dfs(math.ceil(n/2), a, b, c, d, coin)

    # result process
    ans = min(tmp_1, tmp_2, tmp_3, tmp_4, tmp_5, tmp_6, tmp_7)
    dict[n] = ans
    return ans


# count
for t in range(T):
    dict = {}
    n, a, b, c, d = map(int, input().split())
    ans = dfs(n, a, b, c, d, 0)
    print(ans)

Submission status: Wrong Answer

Solution code:
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
inf=10**12
def dfs_sub(n,ttf,cha):
    global check,d
    check[0]=min(check[n]+n*d,check[0]) if 0 in check else check[n]+n*d
    if n//ttf==0:
        check[n//ttf]=min(check[n]+(n%ttf)*d,check[n//ttf]) if n//ttf in check else check[n]+(n%ttf)*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)
        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: Wrong Answer

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,0))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,0),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],[a,b,c]):
        dfs_sub(n,i,j)

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

Submission status: Wrong Answer

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,0))
    if n//ttf==0:
        check[n//ttf]=min(check.get(n//ttf,0),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: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

t = onem()

for i in range(t):
    n,a,b,c,d = m()
    ma = n*d
    de = cl.deque([[n,0]])
    while len(de):
        po = de.popleft()
        if po[0] == 0:
            ma = min(ma,po[1])
        elif po[0] == 1:
            ma = min(ma,po[1]+d)
        else:
            if po[0] % 2 == 0:
                if ma >= po[1]+a:
                    de.append([po[0]//2,po[1]+a])
            else:
                if ma >= po[1]+a+d:
                    #de.append([(po[0]+1)//2,po[1]+a+d])
                    de.append([(po[0]-1)//2,po[1]+a+d])

            if po[0] % 3 == 0:
                if ma >= po[1]+b:
                    de.append([po[0]//3,po[1]+b])
            else:
                mo = po[0] % 3
                if ma >= min(po[1]+b+d*(3-mo),po[1]+b+d*mo):
                    #de.append([(po[0]+(3-mo))//3,po[1]+b+d*(3-mo)])
                    de.append([(po[0]-mo)//3,po[1]+b+d*mo])

            if po[0] % 5 == 0:
                if ma >= po[1]+c:
                    de.append([po[0]//5,po[1]+c])
            else:
                mo = po[0] % 5
                if ma >= min(po[1]+c+d*(5-mo),po[1]+c+d*mo):
                    #de.append([(po[0]+(5-mo))//5,po[1]+c+d*(5-mo)])
                    de.append([(po[0]-mo)//5,po[1]+c+d*mo])
        print(len(de))
    print(ma)

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==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)
        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 check,a,b,c,d
    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={N:0}
    dfs(N)
    ans[i]=min(d*N,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==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)
        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 check,a,b,c,d
    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={N:0}
    dfs(N)
    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==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
    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])