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: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    T=int(input())         
    for _ in range(T):
        N,A,B,C,D=map(int,input().split())
        memo={}
        def saiki(m):
            if m in memo:
                return memo[m]
            if m==0:
                tmp=0
            elif m==1:
                tmp=D
            else:
                tmp=INF
                for k,P in [(2,A),(3,B),(5,C)]:
                    tmp=min(tmp,saiki(m//k)+(m-m//k*k)*D+min((m//k*k-m//k)*D,P))
                    tmp=min(tmp,saiki(-(-m//k))+(-(-m//k)*k-m)*D+min(((-(-m//k))*k+(-m//k))*D,P))
            memo[m]=tmp
            return tmp
        print(saiki(N))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
t = int(input())

def solve(n,a,b,c,d):
  mem = {0:0,1:d}
  def f(n):
    if n in mem:
      return mem[n]
    ret = n*d
    if n%2 == 0:
      ret = min(ret,a+f(n//2))
    else:
      ret = min(ret,a+d+f(n//2+1),a+d+f(n//2))
    
    if n%3 == 0:
      ret = min(ret,b+f(n//3))
    elif n%3 == 1:
      ret = min(ret,b+d+f(n//3))
    else:
      ret = min(ret,b+d+f(n//3+1))
    
    if n%5 == 0:
      ret = min(ret,c+f(n//5))
    elif n%5 == 1:
      ret = min(ret,c+d+f(n//5))
    elif n%5 == 2:
      ret = min(ret,c+d+d+f(n//5))
    elif n%5 == 3:
      ret = min(ret,c+d+d+f(n//5+1))
    else:
      ret = min(ret,c+d+f(n//5+1))
    mem[n] = ret
    return ret
  return f(n)
 
for _ in range(t):
  n,a,b,c,d = map(int,input().split())
  print(solve(n,a,b,c,d))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
def main():
    T = int(input())
    for _ in range(T):
        N, A, B, C, D = map(int, input().split())
        memo = {}

        def f(n):
            if n == 0:return 0
            if n == 1:return D
            if n in memo:return memo[n]

            ret = min(
                D * n,
                D * (n%2) + A + f(n//2),
                D * abs(n - (n+1)//2*2) + A + f((n+1)//2),
                D * (n%3) + B + f(n//3),
                D * abs(n - (n+2)//3*3) + B + f((n+2)//3),
                D * (n%5) + C + f(n//5),
                D * abs(n - (n+4)//5*5) + C + f((n+4)//5)
            )

            memo[n] = ret
            return ret
        print(f(N))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def dist(n):
  if n==0:
    return 0
  if n==1:
    return d
  if n in memo:
    return memo[n]
  
  res=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]=res
  return res

T=int(input())
for _ in range(T):
  n,a,b,c,d=map(int,input().split())
  memo={}
  print(dist(n))

Submission status: Accepted

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)
      break
    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: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

from heapq import heappush, heappop

def calc(N, A, B, C, D):
    abc = [(2, A), (3, B), (5, C),]
    ans = N * D
    ans2 = min(2*D, D+A)

    dq = []

    heappush(dq, (0, N))
    seen = set()
    while dq:
        cost, rest = heappop(dq)

        if rest in seen:
            continue
        else:
            seen.add(rest)

        if rest <= 2:
            if rest == 1:
                cost += D
            elif rest == 2:
                cost += ans2
            else:
                cost += -rest * D
            ans = min(ans, cost)
            continue

        if cost >= ans:
            continue

        for r, co1 in abc:
            a1, a2 = divmod(rest, r)

            if a2 == 0:
                heappush(dq, (cost+co1, a1))
                continue

            a3 = r - a2
            if a2 == a3:
                heappush(dq, (cost + co1 + a3*D, a1+1))
            elif a2 > a3:
                a1 += 1
                a2 = a3

            cd = a2 * D
            if (rest - a1) * D < co1 + cd:
                ans = min(ans, rest*D + cost)
            else:
                co2 = cost + co1
                heappush(dq, (co2 + cd, a1))

    return ans


def resolve():
    T = int(input())
    S = [list(iim()) for i in range(T)]


    ans = []
    for s in S:
        ans.append(calc(*s))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))


t=n_in()


def execute(n, memo, setting):
    if n in memo:
        return memo[n]

    res = setting[1]*n
    for k in [2,3,5]:
        if n%k == 0:
            res = min(res, execute(n//k, memo, setting) + setting[k])
        else:            
            down = (n//k)*k
            res = min(res, execute(down//k, memo, setting) + setting[k] + (n-down)*setting[1])
            up = (n//k)*k+k
            res = min(res, execute(up//k, memo, setting) + setting[k] + (up-n)*setting[1])

    memo[n] = res
    return res

    

for _ in range(t):
    n,a,b,c,d = l_in()

    setting={2: a, 3: b, 5: c, 1: d}
    memo={1: d, 0: 0}

    print(execute(n,memo,setting))

Submission status: Accepted

Solution code:
t = int(input())

for _ in range(t):
  n, a, b, c, d = map(int, input().split())
  
  memo = {}
  def f(n):
    if n == 0:
      return 0
    if n == 1:
      return d
    if n in memo:
      return memo[n]

    m2 = n % 2
    m3 = n % 3
    m5 = n % 5 
    ret = min(
      d * n,
      d * m2 + a + f((n - m2) // 2),
      d * m2 + a + f((n + m2) // 2),
      d * m3 + b + f((n - m3) // 3),
      d * (3 - m3) + b + f((n + 3 - m3) // 3),
      d * m5 + c + f((n - m5) // 5),
      d * (5 - m5) + c + f((n + 5 - m5) // 5),
    )
    memo[n] = ret
    return ret
  print(f(n))

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

from heapq import heappush, heappop

def calc(N, A, B, C, D):
    abc = [(3, B), (5, C), (2, A)]
    ans = N * D
    ans2 = min(2*D, D+A)

    dq = []

    heappush(dq, (0, N))
    seen = set()
    while dq:
        cost, rest = heappop(dq)

        if rest <= 2:
            if rest == 1:
                cost += D
            elif rest == 2:
                cost += ans2
            else:
                cost += -rest * D
            ans = min(ans, cost)
            continue

        if rest in seen:
            continue
        else:
            seen.add(rest)

        if cost >= ans:
            continue

        for r, co1 in abc:
            a1, a2 = divmod(rest, r)

            if a2 == 0:
                heappush(dq, (cost+co1, a1))
                continue

            if a2 > r - a2:
                a1 += 1
                a2 = r - a2

            cd = a2 * D
            if (rest - a1) * D < co1 + cd:
                ans = min(ans, rest*D + cost)
            else:
                co2 = cost + co1
                heappush(dq, (co2 + cd, a1))

        if a2 == 1:
            heappush(dq, (cost+A+D, a1+1))


    return ans


def resolve():
    T = int(input())
    S = [list(iim()) for i in range(T)]


    ans = []
    for s in S:
        ans.append(calc(*s))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
t=int(input())
from functools import lru_cache####
@lru_cache(maxsize=10000)####
def f(x,a,b,c,d):
    if x==1:
        return d
    
    if x==0:
        return 0
    
    res1,res2=0,0
    if x%2:
        res1 = f(x//2,a,b,c,d)+a+d
        res2 = f(x//2+1,a,b,c,d)+a+d
    else:
        res1=res2=f(x//2,a,b,c,d)+a
    res3,res4=0,0
    if x%3:
        res3 = f(x//3,a,b,c,d)+b+d*(x%3)
        res4 = f(x//3+1,a,b,c,d)+b+d*(3-x%3)
    else:
        res3=res4=f(x//3,a,b,c,d)+b
    if x%5:
        res5 = f(x//5,a,b,c,d)+c+d*(x%5)
        res6 = f(x//5+1,a,b,c,d)+c+d*(5-x%5)
    else:
        res5=res6=f(x//5,a,b,c,d)+c
    return(min(res1,res2,res3,res4,res5,res6,x*d))
for _ in range(t):
    n,a,b,c,d=map(int, input().split( ))
    
    ans=f(n,a,b,c,d)
    print(ans)

Submission status: Accepted

Solution code:
T = int(input())

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

    def f(n):
         if n == 0:
             return 0
         if n == 1:
             return D
         if n in memo:
             return memo[n]

         ret = min(
             D * n,
             D * abs(n - n//5*5) + C + f(n//5),
             D * abs(n - (n+4)//5*5) + C + f((n+4)//5),
             D * abs(n - n//3*3) + B + f(n//3),
             D * abs(n - (n+2)//3*3) + B + f((n+2)//3),
             D * abs(n - n//2*2) + A + f(n//2),
             D * abs(n - (n+1)//2*2) + A + f((n+1)//2)
         )

         memo[n] = ret
         return ret

    print(f(N))

Submission status: Accepted

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

N = 0
A = 0
B = 0
C = 0
D = 0
cost_result = {} # ある数に達するために必要なコインの枚数
each_cost = {} # 与えられたコスト

def cost(target):
    """
    Args:
        target: 目標とする数字

    Returns:
        result: その数字に達するまでに必要なコスト
    """
    if target in cost_result:
        return cost_result[target]

    else:
        result_dict = {}
        for i in [2, 3, 5]:
            if target % i == 0:
                result_dict[i] = cost(target//i) + each_cost[i]
            else:
                result_dict[i] = min(
                    cost(target//i) + each_cost[i] + D * (target % i),
                    cost((target//i)+1) + each_cost[i] + D * (i - target % i)
                )
        simplest = target * D
        result = min(min(result_dict.values()), simplest)
        cost_result[target] = result
        return result



if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        N, A, B, C, D = list(map(int, input().split()))

        each_cost[2] = A
        each_cost[3] = B
        each_cost[5] = C
        cost_result[1] = D
        cost_result = {0:0, 1:D}

        print(cost(N))

Submission status: Accepted

Solution code:
t = int(input())

def calc(x):
    if x not in dp:
        divs = [5, 3, 2]
        costs = [c, b, a]
        values = lambda div, cost: [calc((x + i) // div) + cost + (sign * x) % div * d for i, sign in [(0, 1), (div - 1, -1)]]
        dp[x] = min(*[value for div, cost in zip(divs, costs) for value in values(div, cost)], x * d)
    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: Accepted

Solution code:
t = int(input())

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: Accepted

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 == 1:
            return D
        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: Accepted

Solution code:
import sys
from functools import lru_cache
t=int(input())
def solve(n,A,B,C,D):
	@lru_cache(None)#メモ化再帰
	def f(x):
		if x<=1:
			return D*x
		ret=D*x

		if x%2==0:
			ret=min(ret,f(x//2)+A)
		else:
			ret=min(ret,f(x//2)+A+D,f(x//2+1)+A+D)
		
		if x%3==0:
			ret=min(ret,f(x//3)+B)
		elif x%3==1:
			ret=min(ret,f(x//3)+B+D)
		else:
			ret=min(ret,f(x//3+1)+B+D)

		if x%5<=2:
			ret=min(ret,f(x//5)+C+D*(x%5))
		else:
			ret=min(ret,f(x//5+1)+C+D*(5-x%5))
		return ret
	return f(n)
for _ in range(t):
	n,A,B,C,D=map(int,input().split())
	print(solve(n,A,B,C,D))

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
def input():
    return sys.stdin.readline()[:-1]

def solve(N, A, B, C, D):
    @lru_cache(None)
    def f(N):
        if N == 0:
            return 0
        if N == 1:
            return D
        # すべて-1の遷移で0にしたケース
        ret = D * N

        q, r = divmod(N, 2)
        if r == 0:
            # 2で割り算
            ret = min(ret, f(q) + A)
        else:
            # -1して2で割り算、+1して2で割り算
            ret = min(ret, f(q) + A + D, f(q+1) + A + D)

        q, r = divmod(N, 3)
        if r == 0:
            # 3で割り算
            ret = min(ret, f(q) + B)
        elif r == 1:
            # -1して3で割り算
            ret = min(ret, f(q) + B + D)
        else:
            # +1して3で割り算
            ret = min(ret, f(q+1) + B + D)

        q, r = divmod(N, 5)
        if r == 0:
            # 5で割り算
            ret = min(ret, f(q) + C)
        elif r == 1:
            # -1して5で割り算
            ret = min(ret, f(q) + C + D)
        elif r == 2:
            # -2して5で割り算
            ret = min(ret, f(q) + C + D + D)
        elif r == 3:
            # +2して5で割り算
            ret = min(ret, f(q+1) + C + D + D)
        else:
            # +1して5で割り算
            ret = min(ret, f(q+1) + C + D)
        return ret
    return f(N)

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

Submission status: Accepted

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
        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 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)

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: Accepted

Solution code:
# heapq -> deque

def main():
    from collections import defaultdict, deque

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

        inf = N * D + 1

        dq = deque()
        dq.append((0, N))  # cost,value

        checked = defaultdict(lambda: inf)
        checked[N] = 0

        ans = inf
        while dq:
            cost, x = dq.popleft()
            if cost >= ans: continue
            if cost > checked[x]: continue

            # 0まで1ずつ減らす
            ans = min(ans, cost + x * D)

            for d, c in ((2, A), (3, B), (5, C)):
                nx, r = divmod(x, d)
                ncost = cost + r * D + c
                if checked[nx] > ncost:
                    checked[nx] = ncost
                    dq.append((ncost, nx))

                if r == 0: continue
                ncost = cost + (d - r) * D + c
                if checked[nx + 1] > ncost:
                    checked[nx + 1] = ncost
                    dq.append((ncost, nx + 1))

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
memo=dict()
t=int(input())
def f(x):
	if x in memo:
		return memo[x]
	if x<=1:
		return D*x
	ret=D*x

	if x%2==0:
		ret=min(ret,f(x//2)+A)
	else:
		ret=min(ret,f(x//2)+A+D,f(x//2+1)+A+D)
	
	if x%3==0:
		ret=min(ret,f(x//3)+B)
	elif x%3==1:
		ret=min(ret,f(x//3)+B+D)
	else:
		ret=min(ret,f(x//3+1)+B+D)

	if x%5<=2:
		ret=min(ret,f(x//5)+C+D*(x%5))
	else:
		ret=min(ret,f(x//5+1)+C+D*(5-x%5))
	memo[x]=ret
	return ret
for _ in range(t):
	memo=dict()
	n,A,B,C,D=map(int,input().split())
	print(f(n))

Submission status: Accepted

Solution code:
# heapq -> deque

def main():
    from collections import defaultdict, deque

    inf = 10 ** 27

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

        dq = deque()
        dq.append((0, N))  # cost,value
        checked = defaultdict(lambda: inf)

        ans = N * D + 1
        while dq:
            cost, x = dq.popleft()
            if cost >= ans: continue
            if cost >= checked[x]: continue
            checked[x] = cost

            # 0まで1ずつ減らす
            ans = min(ans, cost + x * D)

            for d, c in ((2, A), (3, B), (5, C)):
                # すでにheapqからnxがpopしていれば
                # より低コストでnxを生成できているので
                # nxの生成は不要
                nx, r = divmod(x, d)
                ncost = cost + r * D + c
                if checked[nx] > ncost:
                    dq.append((ncost, nx))
                ncost = cost + (d - r) * D + c
                if (r > 0) and (checked[nx + 1] > ncost):
                    dq.append((ncost, nx + 1))

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def solve(n, a, b, c, d):
    if n == 1:
        return d
    if n == 0:
        return 0
    
    if n in memo:
        return memo[n]
    
    ans = min(
        n * d, 
        
        abs(n-n//2*2)*d + a + solve(n//2, a, b, c, d),
        abs(n-(n+1)//2*2)*d + a + solve((n+1)//2, a, b, c, d),
        
        abs(n-n//3*3)*d + b + solve(n//3, a, b, c, d),
        abs(n-(n+2)//3*3)*d + b + solve((n+2)//3, a, b, c, d),
        
        abs(n-n//5*5)*d + c + solve(n//5, a, b, c, d),
        abs(n-(n+4)//5*5)*d + c + solve((n+4)//5, a, b, c, d)        
        )
    memo[n] = ans
    return ans


t = int(input())
for i in range(t):
    n, a, b, c, d = map(int, input().split())
    memo = {}
    print(solve(n, a, b, c, d))

Submission status: Accepted

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

def dfs_sub(n,ttf,cha,d):
    global check

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

    #最寄りまで-してく場合
    x1,x2=n//ttf,n%ttf
    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 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 b,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j,d)

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

Submission status: Accepted

Solution code:
def solve(N, A, B, C, D):
    d = {0:0, 1:D}
    s = set()
    return dfs(N, A, B, C, D, d, s)

def dfs(n, A, B, C, D, d, s):
    if n in d:
        return d[n]
    if n in s:
        return float('inf')
    
    s.add(n)
    ans = float('inf')
    
    p = n % 2
    if p == 0:
        ans = min(ans, dfs(n // 2, A, B, C, D, d, s) + A)
    else:
        ans = min(ans, dfs((n - p) // 2, A, B, C, D, d, s) + A + D * p)
        ans = min(ans, dfs((n + (2 - p)) // 2, A, B, C, D, d, s) + A + D * (2 - p))

    q = n % 3
    if q == 0:
        ans = min(ans, dfs(n // 3, A, B, C, D, d, s) + B)
    else:
        ans = min(ans, dfs((n - q) // 3, A, B, C, D, d, s) + B + D * q)
        ans = min(ans, dfs((n + (3 - q)) // 3, A, B, C, D, d, s) + B + D * (3 - q))
    
    r = n % 5
    if r == 0:
        ans = min(ans, dfs(n // 5, A, B, C, D, d, s) + C)
    else:
        ans = min(ans, dfs((n - r) // 5, A, B, C, D, d, s) + C + D * r)
        ans = min(ans, dfs((n + (5 - r)) // 5, A, B, C, D, d, s) + C + D * (5 - r))
    
    ans = min(ans, D * n)
    
    d[n] = ans
    return ans

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

Submission status: Accepted

Solution code:
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 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 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 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())
    z=list(zip([2,3,5],b))
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Submission status: Accepted

Solution code:
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 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 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())
    z=list(zip([2,3,5],b))
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Submission status: Accepted

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

def dfs_sub(n,ttf,cha):
    global check,d
    
    check[0]=min(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: Accepted

Solution code:
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*(-(-x//2))
        l3=3*(x//3)
        r3=3*(-(-x//3))
        l5=5*(x//5)
        r5=5*(-(-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: Accepted

Solution code:
import heapq

def pay2win():
  num = set()
  q = []
  heapq.heapify(q)
  heapq.heappush(q,( 0, N ))
  cost = N*D
  while q:
    c0, n0 = heapq.heappop(q)
    if n0 in num:
      continue
    num.add(n0)
    if n0 == 0:
      break
    if c0 >= cost:
      break
    cost = min(cost,c0+n0*D)
    #
    n2, m = divmod(n0, 2)
    if m == 0:
      heapq.heappush(q,( c0+A, n2 ))
    else:
      heapq.heappush(q,( c0+D+A, n2 ))
      heapq.heappush(q,( c0+D+A, n2+1 ))
    #
    n3, m = divmod(n0, 3)
    if m == 0:
      heapq.heappush(q,( c0+B, n3 ))
    elif m == 1:
      heapq.heappush(q,( c0+D+B, n3 ))
    else:
      heapq.heappush(q,( c0+D+B, n3+1 ))
    #
    n5, m = divmod(n0, 5)
    if m == 0:
      heapq.heappush(q,( c0+C, n5 ))
    elif m <= 2:
      heapq.heappush(q,( c0+D*m+C, n5 ))
    else:
      heapq.heappush(q,( c0+D*(5-m)+C, n5+1 ))
    #
  print(cost)
#

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

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    T=I()
    import heapq
    from collections import defaultdict
    inf=10**18+1
    for _ in range(T):
        #print("---")
        L=[0]*4
        N,L[0],L[1],L[2],L[3]=MI()
        LL=[2,3,5]
        dd = defaultdict(lambda: inf)
        dd[0]=0
        q=[(0,N,1)]#cost，数字，+-1を使えるか
        heapq.heapify(q)
        ans=L[3]*N
        while True:
            cost,now,flag=heapq.heappop(q)
            if now==0:
                ans=cost
                break
            if cost>ans:
                break
            ans=min(ans,cost+now*L[3])
            
            for i in range(3):
                if now%LL[i]==0:
                    nxt=now//LL[i]
                    ncost=cost+L[i]
                    if ncost<dd[nxt]:
                        dd[nxt]=ncost
                        heapq.heappush(q,(ncost,nxt,1))
            
            if flag:
                for k in range(1,5):
                    for pm in [1,-1]:
                        nxt=now+k*pm
                        ncost=cost+L[3]*k
                        if ncost<dd[nxt]:
                            dd[nxt]=ncost
                            heapq.heappush(q,(ncost,nxt,0))
                    
        print(ans)
                
                    
            
        
        
        
        
        
        

main()

Submission status: Accepted

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 == 1:
            return D
        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: Accepted

Solution code:
from functools import lru_cache

def calc(n):
    @lru_cache(maxsize=None)
    def rec(n):
        if n <= 0: return 0
        S = [2, 3, 5]
        mi = D * n
        for i, a in enumerate(S):
            for j in range(-a//2, a//2 + 1):
                if (n + j) % a == 0 and (n + j) // a < n:
                    mi = min(mi, rec((n+j) // a) + X[i] + D * abs(j))
        return mi
    return rec(n)

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

Submission status: Accepted

Solution code:
from functools import lru_cache

def solve(n,a,b,c,d):
    @lru_cache(None)
    def rec(cur):
        if cur == 0:    return 0
        if cur == 1:    return d
        ret = cur * d
        p,q = divmod(cur, 2)
        if q == 0:  ret = min(ret, rec(p) + a)
        if q == 1:  ret = min(ret, rec(p) + a + d, rec(p + 1) + a + d)
        p,q = divmod(cur, 3)
        if q == 0:  ret = min(ret, rec(p) + b)
        if q == 1:  ret = min(ret, rec(p) + b + d)
        if q == 2:  ret = min(ret, rec(p) + b + d * 2, rec(p + 1) + b + d)
        p,q = divmod(cur, 5)
        if q == 0:  ret = min(ret, rec(p) + c)
        if q == 1:  ret = min(ret, rec(p) + c + d)
        if q == 2:  ret = min(ret, rec(p) + c + d * 2)
        if q == 3:  ret = min(ret, rec(p) + c + d * 3, rec(p + 1) + c + d * 2)
        if q == 4:  ret = min(ret, rec(p) + c + d * 4, rec(p + 1) + c + d)
        return ret

    return rec(n)

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