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:
t=int(input())
# n,a,b,c,d
s= [list(map(int, input().split())) for i in range(t)]

for i in range(t):
    a1=s[i][1]
    b1=s[i][2]
    c1=s[i][3]
    d1=s[i][4]
    ans=float('inf')
    for q in range(8):
        for a in range(61):
            for b in range(41):
                for c in range(31):
                    n = s[i][0]
                    cnt = 0
                    a2=a
                    b2=b
                    c2=c
                    q2=q
                    while n > 0:
                        if a2 > 0 and not (q2 >> 0) & 1:
                            cnt += (n % 2) * d1
                            cnt += a1
                            n //= 2
                            a2 -= 1
                        elif a2 > 0 and (q2 >> 0) & 1:
                            cnt += abs(n % 2 - 2) * d1
                            cnt += a1
                            n //= 2
                            n += 1
                            a2 -= 1
                            q2 -= 1


                        elif b2 > 0 and not (q2 >> 1) & 1:
                            cnt += (n % 3) * d1
                            cnt += b1
                            n //= 3
                            b2 -= 1

                        elif b2 > 0 and (q2 >> 1) & 1:
                            cnt += abs(n % 3 - 3) * d1
                            cnt += b1
                            n //= 3
                            n += 1
                            b2 -= 1
                            q2 -= 2

                        elif c2 > 0 and not (q2 >> 2) & 1:
                            cnt += (n % 5) * d1
                            cnt += c1
                            n //= 5
                            c2 -= 1

                        elif c2 > 0 and (q2 >> 2) & 1:
                            cnt += abs(n % 5 - 5) * d1
                            cnt += c1
                            n //= 5
                            n += 1
                            c2 -= 1
                            q2 -= 4
                        else:
                            cnt += n * d1
                            n = 0
                    ans = min(cnt, ans)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

def solve(t,ans):
    global a,b,c,d,fin,al,dic1
    if t < 5:
        if t==1:
            fin = min(fin,ans+d)
        elif t == 2:
            fin = min(fin,ans+2*d,ans+a+d,)
        elif t == 3:
            fin = min(fin,ans+3*d,ans+b+d,ans+a+2*d)
        else:
            fin = min(fin,ans+2*d+c,ans+4*d,ans+2*d+b,ans+2*a+d,ans+a+2*d)
    else:
        for i in al:
            u = t+i
            ans_temp = ans + d*abs(i)
            if u % 5 == 0:
                if c > 4*u//5 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//5 not in dic1:
                        solve(u//5,ans_temp+c)
                        dic1[u//5] = ans_temp+c
                    elif dic1[u//5] > ans_temp+c:
                        solve(u//5,ans_temp+c)
                        dic1[u//5] = ans_temp+c
            if u % 3 == 0:
                if b > 2*u//3 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//3 not in dic1:
                        solve(u//3,ans_temp+b)
                        dic1[u//3] = ans_temp+b
                    elif dic1[u//3] > ans_temp+b:
                        solve(u//3,ans_temp+b)
                        dic1[u//3] = ans_temp+b

            if u % 2 and -2 < i < 2 == 0:
                if a > u//2 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//2 not in dic1:
                        solve(u//2,ans_temp+a)
                        dic1[u//2] = ans_temp+a
                    elif dic1[u//2] > ans_temp+a:
                        solve(u//2,ans_temp+a)
                        dic1[u//2] = ans_temp+a

t = int(input())
al = [0,-1,1,-2,2]

for i in range(t):
    n,a,b,c,d = map(int,input().split())
    fin = 10**30
    dic1 = {}
    solve(n,0)
    print(fin)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = ""

if N <= 1999:
  S = "un"

print(S + "rated")

Submission status: Wrong Answer

Solution code:
from collections import deque
t = int(input())

def bfs(cur, cost, a, b, c, d, target):
    memo = {0: float('inf')}
    stack = deque([(cur, cost)])
    while stack:
        cur, cost = stack.pop()
        if cur in memo and memo[cur] <= cost:
            continue
        if cur > 2 * target:
            continue
        if cur < 0:
            continue
        memo[0] = min(memo[0], cost + cur * d)
        memo[cur] = cost
        stack.append((cur//5, cost + c + (cur % 5) * d))
        stack.append((cur//3, cost + b + (cur % 3) * d))
        stack.append((cur//2, cost + a + (cur % 2) * d))
    return memo[0]

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import heapq


def solve():
  N, A, B, C, D = map(int, input().split())
  seen_values = set()
  queue = []
  heapq.heappush(queue, (0, N))

  while True:
    cost, value = heapq.heappop(queue)

    if value in seen_values:
      continue

    seen_values.add(value)

    if value == 1:
      print(cost + D)
      return

    for k, c in ((2, A), (3, B), (5, C)):
      v, m = divmod(value, k)

      if v == 0:
        continue
      elif m == 0:
        heapq.heappush(queue, (cost + c, v))
      elif m <= k // 2:
        heapq.heappush(queue, (cost + c + D * m, v))
      else:
        heapq.heappush(queue, (cost + c + D * (k - m), v + 1))

      heapq.heappush(queue, (cost + D * (value - v), v))


def main():
  for _ in range(int(input())):
    solve()


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
N = int(input())

if N <= 1999:
  print("unrated")
  
else:
  print("rated")

Submission status: Wrong Answer

Solution code:
T=int(input())

def solve(N):
    if N==0:
        return 0
    if N==1:
        return D
    if N in dic:
        return dic[N]
    tmp=N*D    
    if N%2==0:
        tmp=min(tmp,solve(N//2)+A)
    else:
        tmp=min(tmp,solve((N-1)//2)+A+D)
    b=N%3 
    if N%3==0:
        tmp=min(tmp,solve(N//3)+B)
    elif b==1:
        tmp=min(tmp,solve((N-1)//3)+B+D)
    else:
        tmp=min(tmp,solve((N+1)//3)+B+D)
    c=N%5
    if N%5==0:
        tmp=min(tmp,solve(N//5)+C)
    elif c==1 or c==2:
        tmp=min(tmp,solve((N-c)//5)+C+D*c)
    else:
        c=5-c
        tmp=min(tmp,solve((N+c)//5)+C+D*c)
    dic[N]=tmp
    return tmp

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

Submission status: Wrong Answer

Solution code:
def dfs(n):
    if n not in memo:
        ans = min(dfs(n//2) + a + d*(n%2), n*d)
        ans = min(ans, dfs(n//3) + b + d*(n % 3), dfs((n+2)//3) + b + d*(3 - n%3))
        ans = min(ans, dfs(n//5) + c + d*(n % 5), dfs((n+4)//5) + c + d*(5 - n%5))
        memo[n] = ans
    return memo[n]


t = int(input())

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

def solve(t,ans):
    global a,b,c,d,fin,al,dic1
    if t < 5:
        if t==1:
            fin = min(fin,ans+d)
        elif t == 2:
            fin = min(fin,ans+2*d,ans+a+d,)
        elif t == 3:
            fin = min(fin,ans+3*d,ans+b+d,ans+a+2*d)
        else:
            fin = min(fin,ans+2*d+c,ans+4*d,ans+2*d+b,ans+2*a+d,ans+a+2*d)
    else:
        for i in al:
            u = t+i
            ans_temp = ans + d*abs(i)
            if u % 5 == 0:
                if c > 4*u//5 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//5 not in dic1:
                        solve(u//5,ans_temp+c)
                        dic1[u//5] = ans_temp+c
                    elif dic1[u//5] > ans_temp+c:
                        solve(u//5,ans_temp+c)
                        dic1[u//5] = ans_temp+c
            if u % 3 == 0:
                if b > 2*u//3 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//3 not in dic1:
                        solve(u//3,ans_temp+b)
                        dic1[u//3] = ans_temp+b
                    elif dic1[u//3] > ans_temp+b:
                        solve(u//3,ans_temp+b)
                        dic1[u//3] = ans_temp+b

            if u % 2 == 0:
                if a > u//2 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//2 not in dic1:
                        solve(u//2,ans_temp+a)
                        dic1[u//2] = ans_temp+a
                    elif dic1[u//2] > ans_temp+a:
                        dic1[u//2] = ans_temp+a

t = int(input())
al = [0,-1,1,-2,2]

for i in range(t):
    n,a,b,c,d = map(int,input().split())
    fin = 10**30
    dic1 = {}
    solve(n,0)
    print(fin)

Submission status: Wrong Answer

Solution code:
def solve(n):
    if n in memo:
        return memo[n]
    if n == 0:
        return INF
    if n == 1:
        return d
    ans = INF
    for i in (-1, 0, 1):
        res = n + i
        if res % 2 == 0:
            tmp = res - (res // 2)
            ans = min(solve(res // 2) + min(a + abs(i) * d, tmp * d), ans)

    for i in (-2, -1, 0, 1, 2):
        res = n + i
        if res % 3 == 0:
            tmp = res - (res // 3)
            ans = min(solve(res // 3) + min(b + abs(i) * d, tmp * d), ans)
          
    for i in (-4, -3, -2, -1, 0, 1, 2, 3, 4):
        res = n + i
        if res % 5 == 0:
            tmp = res - (res // 5)
            ans = min(solve(res // 5) + min(c + abs(i) * d, tmp * d), ans)

    memo[n] = ans
    return ans

INF = 10 ** 30
t = int(input())

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

Submission status: Wrong Answer

Solution code:
t=int(input())
def f(x,a,b,c,d):
    if x==1:
        return d
    if x==0:
        return 0
    if x==2:
        return(min(d*2,a+d))
    if x==3:
        return(min(d*3,b+d, d+a+b))
    if x==5:
        return(min(d*5,c+d,d+b+d,d+a+b+d))
    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: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import heapq


def solve():
  N, A, B, C, D = map(int, input().split())
  seen_values = set()
  queue = []
  heapq.heappush(queue, (0, N))

  while True:
    cost, value = heapq.heappop(queue)

    if value in seen_values:
      continue

    seen_values.add(value)

    if value == 1:
      print(cost + D)
      return

    for k, c in ((2, A), (3, B), (5, C)):
      v, m = divmod(value, k)

      if v == 0:
        continue
      elif m == 0:
        heapq.heappush(queue, (cost + c, v))
      else:
        heapq.heappush(queue, (cost + c + D * m, v))
        heapq.heappush(queue, (cost + c + D * (k - m), v + 1))


def main():
  for _ in range(int(input())):
    solve()


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

def solve(t,ans):
    global a,b,c,d,fin,al,dic1
    dic1[t] = ans
    if t < 5:
        if t==1:
            fin = min(fin,ans+d)
        elif t == 2:
            fin = min(fin,ans+2*d,ans+a+d,)
        elif t == 3:
            fin = min(fin,ans+3*d,ans+b+d,ans+a+2*d)
        else:
            fin = min(fin,ans+2*d+c,ans+4*d,ans+2*d+b,ans+2*a+d,ans+a+2*d)
    else:
        fa,fb,fc = 1,1,1
        for i in al:
            u = t+i
            ans_temp = ans + d*abs(i)
            if u % 5 == 0 and fc == 1:
                fc = 0
                if c > 4*u//5 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//5 not in dic1:
                        solve(u//5,ans_temp+c)
                    elif dic1[u//5] > ans_temp+c:
                        solve(u//5,ans_temp+c)
            if u % 3 == 0 and fb == 1:
                fb = 0
                if b > 2*u//3 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//3 not in dic1:
                        solve(u//3,ans_temp+b)
                    elif dic1[u//3] > ans_temp+b:
                        solve(u//3,ans_temp+b)

            if u % 2 == 0 and fa == 1:
                fa = 0
                if a > u//2 * d:
                    fin = min(fin,ans_temp+u*d)
                else:
                    if u//2 not in dic1:
                        solve(u//2,ans_temp+a)
                    elif dic1[u//2] > ans_temp+a:
                        solve(u//2,ans_temp+a)

t = int(input())
al = [0,-1,1,-2,2]

for i in range(t):
    n,a,b,c,d = map(int,input().split())
    fin = 10**30
    dic1 = {}
    solve(n,0)
    print(fin)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import heapq


def solve():
  N, A, B, C, D = map(int, input().split())
  seen_values = set()
  queue = []
  heapq.heappush(queue, (0, N))

  while True:
    if len(queue) == 0:
      print(min_cost)
      return

    cost, value = heapq.heappop(queue)

    if value in seen_values:
      continue

    seen_values.add(value)

    if value == 1:
      print(cost + D)
      return

    # div 2
    v, m = divmod(value, 2)
    c = A

    if v == 0:
      continue
    elif m == 1:
      c += D

    heapq.heappush(queue, (cost + min(c, (value - v) * D), v))

    # div 3
    v, m = divmod(value, 3)
    c = B

    if v == 0:
      continue
    elif m == 1:
      c += D
    elif m == 2:
      c += D
      v += 1

    heapq.heappush(queue, (cost + min(c, (value - v) * D), v))

    # div 5
    v, m = divmod(value, 5)
    c = C

    if v == 0:
      continue
    elif m == 1:
      c += D
    elif m == 2:
      c += D * 2
    elif m == 3:
      c += D * 2
      v += 1
    elif m == 4:
      c += D
      v += 1

    heapq.heappush(queue, (cost + min(c, (value - v) * D), v))


def main():
  for _ in range(int(input())):
    solve()


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
t = int(input())
for _ in range(t):
  n,a,b,c,d = map(int,input().split())
  dc = defaultdict(int)
  for i in range(-4,5):
    dc[n+i] = 1+abs(i)*d
  for i in range(60):
    if n//(2**i) >= 1:
      for j in range(60):
        if n//((2**i)*(3**j)) >= 1:
          for k in range(60):
            if n//((2**i)*(3**j)*(5**k)) >= 1:
              for x in (n//((2**i)*(3**j)*(5**k)),n//((2**i)*(3**j)*(5**k))+1):
                if not dc[x]:
                  dc[x] = 10**27
                if dc[x*2] >= 1:
                  dc[x] = min(dc[x],dc[x*2]+a)
                if dc[x*3] >= 1:
                  dc[x] = min(dc[x],dc[x*3]+b)
                if dc[x*5] >= 1:
                  dc[x] = min(dc[x],dc[x*5]+c)
                if dc[x+1] >= 1:
                  dc[x] = min(dc[x+1]+d,dc[x])
                if dc[x-1] >= 1:
                  dc[x] = min(dc[x-1]+d,dc[x])
  print(min(dc[1]+d-1,n*d))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def func(t, MAX, dic, num, coin):
  ans = dic.get(num, -1)
  a,b,c,d = t
  
  if ans != -1:
    return ans
  
  ans = sys.maxsize

  if num == 0:
    dic[0] = 0
    MAX = min(coin,MAX)
    return 0

  if num == 1:
    dic[1] = d
    MAX = min(coin + d, MAX)
    return d

  if coin >= MAX:
    return sys.maxsize

  if num % 2 == 0:
    ans = min(func(t, MAX, dic, num//2, coin+a)+a, ans)
  else:
    ans = min(func(t, MAX, dic, (num+1)//2, coin+a+d)+a+d, ans)
    ans = min(func(t, MAX, dic, (num-1)//2, coin+a+d)+a+d, ans)

  if num % 3 == 0:
    ans = min(func(t, MAX, dic, num//3, coin+b)+b, ans)
  elif num % 3 == 1:
    ans = min(func(t, MAX, dic, (num-1)//3, coin+b+d)+b+d, ans)
  else:
    ans = min(func(t, MAX, dic, (num+1)//3, coin+b+d)+b+d, ans)

  if num % 5 == 0:
    ans = min(func(t, MAX, dic, num//5, coin+c)+c, ans)
  elif num % 5 <= 2:
    tmp = num % 5
    ans = min(func(t, MAX, dic, (num-tmp)//5, coin+c+d*tmp)+c+d*tmp, ans)
  else:
    tmp = 5 - (num % 5)
    ans = min(func(t, MAX, dic, (num+tmp)//5, coin+c+d*tmp)+c+d*tmp, ans)
    
  dic[num] = ans
  MAX = min(coin+ans, MAX)
  return ans

def main():
  t = int(input())

  e = []
  f = []
  g = []
  h = []
  j = []

  for i in range(t):
    n,a,b,c,d = map(int,input().split())
    e.append(n)
    f.append(a)
    g.append(b)
    h.append(c)
    j.append(d)

  for i in range(t):
    n = e[i]
    a = f[i]
    b = g[i]
    c = h[i]
    d = j[i]
    
    t = (a,b,c,d)
    

    print(func(t, sys.maxsize, {}, n, 0))
    
main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import heapq


def solve():
  N, A, B, C, D = map(int, input().split())
  seen_values = set()
  queue = []
  heapq.heappush(queue, (0, N))

  while True:
    if len(queue) == 0:
      print(min_cost)
      return

    cost, value = heapq.heappop(queue)

    if value in seen_values:
      continue

    seen_values.add(value)

    if value == 1:
      print(cost + D)
      return

    # div 2
    v, m = divmod(value, 2)
    c = A

    if m == 1:
      c += D

    heapq.heappush(queue, (cost + min(c, (value - v) * D), v))

    # div 3
    v, m = divmod(value, 3)
    c = B

    if m == 1:
      c += D
    elif m == 2:
      c += D
      v += 1

    heapq.heappush(queue, (cost + min(c, (value - v) * D), v))

    # div 5
    v, m = divmod(value, 5)
    c = C

    if m == 1:
      c += D
    elif m == 2:
      c += D * 2
    elif m == 3:
      c += D * 2
      v += 1
    elif m == 4:
      c += D
      v += 1

    heapq.heappush(queue, (cost + min(c, (value - v) * D), v))


def main():
  for _ in range(int(input())):
    solve()


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
1.

Submission status: Wrong Answer

Solution code:
def agc044_a():
    T = int(input())
    Case = [tuple(map(int, input().split())) for _ in range(T)]

    def solve(N, A, B, C, D):
        mincost = N * D
        for x in range(60):  # 2の乗数
            for y in range(38):  # 3の乗数
                for z in range(26):  # 5の乗数
                    f = (2**x) * (3**y) * (5**z)
                    a1, b1 = divmod(N, f)
                    a2, b2 = a1+1, f*(a1+1) - N
                    cost1 = A*x + B*y + C*z + D*(a1+b1)
                    cost2 = A*x + B*y + C*z + D*(a2+b2)
                    mincost = min(mincost, cost1, cost2)
        return mincost

    for cs in Case:
        ans = solve(*cs)
        print(ans)

agc044_a()

Submission status: Wrong Answer

Solution code:
from math import ceil
T = int(input())
for i in range(T):
    N,A,B,C,D = map(int,input().split())
    memo = {0:0,1:D}
    def f(n):
        if n in memo:
            return memo[n]
        else:
            res = D*n
            r2 = n%2
            r3 = n%3
            r5 = n%5
            res = min(res,f(n//2)+A+r2*D,f(n//3)+B+r3*D,f(n//5)+C+r5*D)
            res = min(res,f(ceil(n/2))+A+(2-r2)*D,f(ceil(n/3))+B+(3-r3)*D,f(ceil(n/5))+C+(5-r5)*D)
            memo[n] = res
            return res
    print(f(N))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import heapq


def solve():
  N, A, B, C, D = map(int, input().split())
  min_cost = 1e+18
  seen_value = set()
  queue = []
  heapq.heappush(queue, (0, N))

  while True:
    if len(queue) == 0:
      print(min_cost)
      return

    c, n = heapq.heappop(queue)

    if n in seen_value:
      continue

    seen_value.add(n)

    if n < 1e+9:
      min_cost = min(c + D * n, min_cost)

    if n < 2:
      continue

    m2 = n % 2

    if m2 == 0:
      heapq.heappush(queue, (c + A, n // 2))
    else:
      heapq.heappush(queue, (c + A + D, (n - 1) // 2))

    if n < 3:
      continue

    m3 = n % 3

    if m3 == 0:
      heapq.heappush(queue, (c + B, n // 3))
    elif m3 == 1:
      heapq.heappush(queue, (c + B + D * 1, (n - 1) // 3))
    else:
      heapq.heappush(queue, (c + B + D * 2, (n - 2) // 3))

    if n < 5:
      continue

    m5 = n % 5

    if m5 == 0:
      heapq.heappush(queue, (c + C, n // 5))
    elif m5 == 1:
      heapq.heappush(queue, (c + C + D * 1, (n - 1) // 5))
    elif m5 == 2:
      heapq.heappush(queue, (c + C + D * 2, (n - 2) // 5))
    elif m5 == 3:
      heapq.heappush(queue, (c + C + D * 3, (n - 3) // 5))
    else:
      heapq.heappush(queue, (c + C + D * 4, (n - 4) // 5))


def main():
  for _ in range(int(input())):
    solve()


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import heapq


def solve():
  N, A, B, C, D = map(int, input().split())
  min_cost = 1e+18
  seen_value = set()
  queue = []
  heapq.heappush(queue, (0, N))

  while True:
    if len(queue) == 0:
      print(min_cost)
      return

    c, n = heapq.heappop(queue)

    if n in seen_value:
      continue

    seen_value.add(n)

    if n < 1e+9:
      min_cost = min(c + D * n, min_cost)

    if n < 2:
      continue

    m2 = n % 2

    if m2 == 0:
      heapq.heappush(queue, (c + A, n // 2))
    else:
      heapq.heappush(queue, (c + A + D, (n - 1) // 2))

    if n < 3:
      continue

    m3 = n % 3

    if m3 == 0:
      heapq.heappush(queue, (c + B, n // 3))
    elif m3 == 1:
      heapq.heappush(queue, (c + B + D, (n - 1) // 3))
    else:
      heapq.heappush(queue, (c + B + D, (n + 1) // 3))

    if n < 5:
      continue

    m5 = n % 5

    if m5 == 0:
      heapq.heappush(queue, (c + C, n // 5))
    elif m5 == 1:
      heapq.heappush(queue, (c + C + D, (n - 1) // 5))
    elif m5 == 2:
      heapq.heappush(queue, (c + C + D * 2, (n - 2) // 5))
    elif m5 == 3:
      heapq.heappush(queue, (c + C + D * 3, (n - 3) // 5))
    else:
      heapq.heappush(queue, (c + C + D * 4, (n - 4) // 5))


def main():
  for _ in range(int(input())):
    solve()


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
t = int(input())
import heapq
def tr(pnt,m):
  try:
    if use[m] > pnt:
      heapq.heappush(now,[pnt,m])
      use[m] = pnt
  except:
    heapq.heappush(now,[pnt,m])
    use[m] = pnt
for _ in range(t):
  n,a,b,c,d = map(int,input().split())
  now = [[0,n],[d,n+1],[d,n-1],[2*d,n+2],[2*d,n-2]]
  use = {}
  ans = n*d
  while True:
    sc,num = heapq.heappop(now)
    ans = min(ans,sc+num*d)
    if num == 1:
      print(ans)
      break
    
    if num % 2 == 0:
      tr(sc+a,num//2)
    else:
      tr(sc+a+d,(num-1)//2)
      tr(sc+a+d,(num+1)//2)
    
    if num % 3 == 0:
      tr(sc+b,num//3)
    elif num % 3 == 1:
      tr(sc+b+d,(num-1)//3)
    else:
      tr(sc+b+d,(num+1)//3)
    
    if num % 5 == 0:
      tr(sc+c,num//5)
    elif num % 5 == 1:
      tr(sc+c+d,(num-1)//5)
    elif num % 5 == 2:
      tr(sc+2*c+d,(num-2)//5)
    elif num % 5 == 3:
      tr(sc+2*c+d,(num+2)//5)
    else:
      tr(sc+c+d,(num+1)//5)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import heapq


def solve():
  N, A, B, C, D = map(int, input().split())
  min_cost = 1e+18
  seen_value = set()
  queue = []
  heapq.heappush(queue, (0, N))

  while True:
    if len(queue) == 0:
      print(min_cost)
      return

    c, n = heapq.heappop(queue)

    if n in seen_value:
      continue

    seen_value.add(n)

    if n < 1e+9:
      min_cost = min(c + D * n, min_cost)

    if n < 2:
      continue

    m2 = n % 2

    if m2 == 0:
      heapq.heappush(queue, (c + A, n // 2))
    else:
      heapq.heappush(queue, (c + A + D, (n - 1) // 2))

    if n < 3:
      continue

    m3 = n % 3

    if m3 == 0:
      heapq.heappush(queue, (c + B, n // 3))
    elif m3 == 1:
      heapq.heappush(queue, (c + B + D, (n - 1) // 3))
    else:
      heapq.heappush(queue, (c + B + D, (n + 1) // 3))

    if n < 5:
      continue

    m5 = n % 5

    if m5 == 0:
      heapq.heappush(queue, (c + C, n // 5))
    elif m5 == 1:
      heapq.heappush(queue, (c + C + D, (n - 1) // 5))
    elif m5 == 2:
      heapq.heappush(queue, (c + C + D + D, (n - 2) // 5))
    elif m5 == 3:
      heapq.heappush(queue, (c + C + D + D, (n + 2) // 5))
    else:
      heapq.heappush(queue, (c + C + D, (n + 1) // 5))


def main():
  for _ in range(int(input())):
    solve()


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import heapq


def solve():
  N, A, B, C, D = map(int, input().split())
  min_cost = 1e+20
  seen_value = set()
  queue = []
  heapq.heappush(queue, (0, N))

  while True:
    if len(queue) == 0:
      print(min_cost)
      return

    c, n = heapq.heappop(queue)

    if n in seen_value:
      continue

    if n == 0:
      print(c)
      return

    seen_value.add(n)

    if n < 1e+9:
      min_cost = min(c + D * n, min_cost)

    if n < 2:
      continue

    m2 = n % 2

    if m2 == 0:
      heapq.heappush(queue, (c + A, n // 2))
    else:
      heapq.heappush(queue, (c + A + D, (n - 1) // 2))

    if n < 3:
      continue

    m3 = n % 3

    if m3 == 0:
      heapq.heappush(queue, (c + B, n // 3))
    elif m3 == 1:
      heapq.heappush(queue, (c + B + D, (n - 1) // 3))
    else:
      heapq.heappush(queue, (c + B + D, (n + 1) // 3))

    if n < 5:
      continue

    m5 = n % 5

    if m5 == 0:
      heapq.heappush(queue, (c + C, n // 5))
    elif m5 == 1:
      heapq.heappush(queue, (c + C + D, (n - 1) // 5))
    elif m5 == 2:
      heapq.heappush(queue, (c + C + D + D, (n - 2) // 5))
    elif m5 == 3:
      heapq.heappush(queue, (c + C + D + D, (n + 2) // 5))
    else:
      heapq.heappush(queue, (c + C + D, (n + 1) // 5))


def main():
  for _ in range(int(input())):
    solve()


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
t = int(input())
inp=[]
for i in range(int(t)):

  
    inp.append(input().split(" "))
    n = int(inp[i][0])
    a = int(inp[i][1])
    b = int(inp[i][2])
    c = int(inp[i][3])
    d = int(inp[i][4])
    ans = d
    l = 0
    n_try = n

    while True:
        l = l + 1
        n_try = n_try + l
        ans += d
        while n_try % 2 == 0:
            n_try = int(n_try / 2)
            ans += a
        while n_try % 3 == 0:
            n_try = int(n_try / 3)
            ans += b
        while n_try % 5 == 0:
            n_try = int(n_try / 5)
            ans += c
            
        if n_try == 1:
            ans_p = ans
            break
    
    l = 0
    n_try = n
    ans = d
    while True:
        l = l + 1
        n_try = n_try - l
        ans += d
        while n_try % 2 == 0:
            n_try = int(n_try / 2)
            ans += a
        while n_try % 3 == 0:
            n_try = int(n_try / 3)
            ans += b
        while n_try % 5 == 0:
            n_try = int(n_try / 5)
            ans += c
            
        if n_try == 1:
            ans_n = ans
            break
    
    final_ans = ans_p, ans_n
    final_ans_v = min(final_ans)
    print(final_ans_v)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

import sys #追加
sys.setrecursionlimit(12*100000) #追加

@lru_cache(maxsize=None)
def solve(a, b, c, d, n, x):
    val = 10 ** 18
    if n == 0:
        # print(x, st)
        return x
    if n == 1:
        # print(x + d, st + "d")
        return x + d
    if n % 2 == 0:
        val_tmp = solve(a, b, c, d, n // 2, x + a)
        val = min(val, val_tmp)
    else:
        val_tmp = solve(a, b, c, d, (n + 1) // 2, x + a + d)
        val = min(val, val_tmp)
        val_tmp = solve(a, b, c, d, (n - 1) // 2, x + a + d)
        val = min(val, val_tmp)
    if n % 3 == 0:
        val_tmp = solve(a, b, c, d, n // 3, x + b)
        val = min(val, val_tmp)
    else:
        mod3 = n % 3
        val_tmp = solve(a, b, c, d, (n + (3 - mod3)) // 3, x + b + d * (3 - mod3))
        val = min(val, val_tmp)
        val_tmp = solve(a, b, c, d, (n - mod3) // 3, x + b + d * mod3)
        val = min(val, val_tmp)
    if n % 5 == 0:
        val_tmp = solve(a, b, c, d, n // 5, x + c)
        val = min(val, val_tmp)
    else:
        mod5 = n % 5
        val_tmp = solve(a, b, c, d, (n + (5 - mod5)) // 5, x + c + d * (5 - mod5))
        val = min(val, val_tmp)
        val_tmp = solve(a, b, c, d, (n - mod5) // 5, x + c + d * mod5)
        val = min(val, val_tmp)
    return val

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