Problem:


Score : 400 points

Problem Statement

You start with the number 0 and you want to reach the number N.

You can change the number, paying a certain amount of coins, with the following operations:

Multiply the number by 2, paying A coins.

Multiply the number by 3, paying B coins.

Multiply the number by 5, paying C coins.

Increase or decrease the number by 1, paying D coins.

You can perform these operations in arbitrary order and an arbitrary number of times.

What is the minimum number of coins you need to reach N?

You have to solve T testcases.

Constraints

1 \le T \le 10

1 \le N \le 10^{18}

1 \le A, B, C, D \le 10^9

All numbers N, A, B, C, D are integers.

Input

The input is given from Standard Input. The first line of the input is

T

Then, T lines follow describing the T testcases.
Each of the T lines has the format

N A B C D

Output

For each testcase, print the answer on Standard Output followed by a newline.

Sample Input 1

5
11 1 2 4 8
11 1 2 2 8
32 10 8 5 4
29384293847243 454353412 332423423 934923490 1
900000000000000000 332423423 454353412 934923490 987654321

Sample Output 1

20
19
26
3821859835
23441258666

For the first testcase, a sequence of moves that achieves the minimum cost of 20 is:

Initially x = 0.

Pay 8 to increase by 1 (x = 1).

Pay 1 to multiply by 2 (x = 2).

Pay 1 to multiply by 2 (x = 4).

Pay 2 to multiply by 3 (x = 12).

Pay 8 to decrease by 1 (x = 11).

For the second testcase, a sequence of moves that achieves the minimum cost of 19 is:

Initially x = 0.

Pay 8 to increase by 1 (x = 1).

Pay 1 to multiply by 2 (x = 2).

Pay 2 to multiply by 5 (x = 10).

Pay 8 to increase by 1 (x = 11).



Sample input:
5
11 1 2 4 8
11 1 2 2 8
32 10 8 5 4
29384293847243 454353412 332423423 934923490 1
900000000000000000 332423423 454353412 934923490 987654321


Sample output:
20
19
26
3821859835
23441258666

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**6)

# def dfs(t,ans):
#     global a,b,c,d fin
#     if t % 5 == 0:
#         if c > 4*t//5 * d:
#             fin = min(fin,ans+4*t//5*d)
#         else:
#             dfs(t//5,ans+c)
#     if t % 3 == 0:
#         if b > 2*t//3 * d:
#             fin = min(fin,ans+2*t//3*d)
#         else:
#             dfs(t//3,ans+b)
#     if t % 2 == 0:
#         if a > t//2 * d:
#             fin = min(fin,ans+t//2*d)
#         else:
#             dfs(t//2,ans+a)
def solve(t,ans):
    global a,b,c,d,fin,al,dic1
    # print(t)
    if t in dic1:
        return
    else:
        dic1[t] = 1
    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
        if t % 5 == 0:
            fc = 0
            if c > 4*t//5 * d:
                fin = min(fin,ans+t*d)
            else:
                solve(t//5,ans+c)
        if t % 3 == 0:
            fb = 0
            if b > 2*t//3 * d:
                fin = min(fin,ans+t*d)
            else:
                solve(t//3,ans+b)
        if t % 2 == 0:
            fa = 0
            if a > t//2 * d:
                fin = min(fin,ans+t*d)
            else:
                solve(t//2,ans+a)
  
        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:
                    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:
                    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:
                    solve(u//2,ans_temp+a)
        # while fa or fb or fc:
        #     u = t+cnt
        #     ans_temp = ans + d*abs(i)
        #     if u % 5 == 0:
        #         if c > 4*u//5 * d:
        #             fin = min(fin,ans_temp+u*d)
        #         else:
        #             solve(u//5,ans_temp+c)
        #     if u % 3 == 0:
        #         if b > 2*u//3 * d:
        #             fin = min(fin,ans_temp+u*d)
        #         else:
        #             solve(u//3,ans_temp+b)
        #     if u % 2 == 0:
        #         if a > u//2 * d:
        #             fin = min(fin,ans_temp+u*d)
        #         else:
        #             solve(u//2,ans_temp+a)
            # if u == 1:
            #     fin = min(fin,ans_temp+d)
t = int(input())
al = [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 search_root(item):
    min = 23441258667
    money = search(item, min, 8, 1, 1)
    if(money < min):
        min = money
    print(min)

def search(item, min, money, n, depth):
    min_value = 23441258667
    if depth == 100:
        return 23441258667
    if item[0] == n:
        return money
    if n < 1:
        return 23441258667
    if min < money:
        return 23441258667
    if item[0] + 4 < n:
        return 23441258667
    for i in range(1, 4):
        min_value = search(item, min, money + item[i], n * index_list[i], depth + 1)
        if (min > min_value):
            min = min_value
    min_value = search(item, min, money + item[4], n + 1, depth + 1)
    if (min > min_value):
        min = min_value
    min_value = search(item, min, money + item[4], n - 1, depth + 1)
    if (min > min_value):
        min = min_value
    return min

input_num = input()
input_list = []
index_list = [1000, 2, 3, 5, 1000]
for _ in range(int(input_num)):
    input_list.append(list(map(int, input().split(" "))))

for item in input_list:
    search_root(item)

Submission status: Wrong Answer

Solution code:
DP = {}

def solve(n, a, b, c, d, did_plus=False):
    if n <= 0: 
        return 0
    if n == 1: 
        return d
    if n in DP:
        return DP[n]
    ans = float('inf')
    for i in range(-4, 5):
        if did_plus:
            if i > 0:
                continue
        num = n + i
        trash = abs(i)*d
        if num < 0:
            continue
        if num%5 == 0 and num // 5 < n:
            ans = min(ans, solve(num//5, a, b, c, d, i>=0) + min(c, d*(num-(num//5))) + trash)
        if num%3 == 0 and num // 3 < n:
            ans = min(ans, solve(num//3, a, b, c, d, i>=0) + min(b, d*(num-(num//3))) + trash)
        if num%2 == 0 and num // 2 < n:
            ans = min(ans, solve(num//2, a, b, c, d, i>=0) + min(a, d*(num-(num//2))) + trash)
        # print(str(n) + ' ' + str(ans) + ' ' + str(num) + ' ' + str(i))
    DP[n] = int(ans)

    return int(ans)

def solve2():
    DP.clear()
    ans = float('inf')
    n, a, b, c, d = map(int, input().split())
    # for i in range(0, 65):
    #     for j in range(0, 30):
    #             for k in range(0, 10):
    #                 val = pow(2, i)*pow(3, j)*pow(5, k)
    #                 ans = min(ans, a*i + b*j + c*k + abs(n - val)*(d))
    # print(ans)
                    
    print(solve(n, a, b, c,d))
    
t = int(input())
for _ in range(t):
    solve2()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(2000)

def calc(n, a, b, c, d, coin):
  if n <= 1:
    return coin

  # 5で割り切れたら
  if not n % 5:
    n /= 5
    coin += c
  # 3で割り切れたら
  elif not n % 3:
    n /= 3
    coin += b
  # 2で割り切れたら
  elif not n % 2:
    n /= 2
    coin += a
  # 上記３つ以外なら
  else:
    coin += d
    #coin_A = calc(n-1, a, b, c, d, coin)
    #coin_B = calc(n+1, a, b, c, d, coin)
    if calc(n-1, a, b, c, d, coin) >= calc(n+1, a, b, c, d, coin):
      n += 1
    else:
      n -= 1
  
  coin = calc(n, a, b, c, d, coin)
  return coin


t = int(input())

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

Submission status: Wrong Answer

Solution code:
DP = {}

def solve(n, a, b, c, d, did_plus=False):
    if n <= 0: 
        return 0
    if n == 1: 
        return d
    if n in DP:
        return DP[n]
    ans = float('inf')
    for i in range(-4, 5):
        if did_plus:
            if i > 0:
                continue
        num = n + i
        trash = abs(i)*d

        if num%5 == 0 and num // 5 < n:
            ans = min(ans, solve(num//5, a, b, c, d, i>=0) + min(c, d*(num-(num//5))) + trash)
        if num%3 == 0 and num // 3 < n:
            ans = min(ans, solve(num//3, a, b, c, d, i>=0) + min(b, d*(num-(num//3))) + trash)
        if num%2 == 0 and num // 2 < n:
            ans = min(ans, solve(num//2, a, b, c, d, i>=0) + min(a, d*(num-(num//2))) + trash)
        # print(str(n) + ' ' + str(ans) + ' ' + str(num) + ' ' + str(i))
    DP[n] = int(ans)

    return int(ans)

def solve2():
    DP.clear()
    ans = float('inf')
    n, a, b, c, d = map(int, input().split())
    # for i in range(0, 65):
    #     for j in range(0, 30):
    #             for k in range(0, 10):
    #                 val = pow(2, i)*pow(3, j)*pow(5, k)
    #                 ans = min(ans, a*i + b*j + c*k + abs(n - val)*(d))
    # print(ans)
                    
    print(solve(n, a, b, c,d))
    
t = int(input())
for _ in range(t):
    solve2()

Submission status: Wrong Answer

Solution code:
T = int(input())

Submission status: Wrong Answer

Solution code:
DP = {}

def solve(n, a, b, c, d, did_plus=False):
    if n <= 0: 
        return 0
    if n == 1: 
        return d
    if n in DP:
        return DP[n]
    ans = float('inf')
    for i in range(-4, 5):
        if did_plus:
            if i >= 0:
                continue
        num = n + i
        trash = abs(i)*d

        if num%5 == 0 and num // 5 < n:
            ans = min(ans, solve(num//5, a, b, c, d, i>=0) + min(c, d*(num-(num//5))) + trash)
        if num%3 == 0 and num // 3 < n:
            ans = min(ans, solve(num//3, a, b, c, d, i>=0) + min(b, d*(num-(num//3))) + trash)
        if num%2 == 0 and num // 2 < n:
            ans = min(ans, solve(num//2, a, b, c, d, i>=0) + min(a, d*(num-(num//2))) + trash)
        # print(str(n) + ' ' + str(ans) + ' ' + str(num) + ' ' + str(i))

    DP[n] = ans

    return ans

def solve2():
    DP.clear()
    ans = float('inf')
    n, a, b, c, d = map(int, input().split())
    # for i in range(0, 65):
    #     for j in range(0, 30):
    #             for k in range(0, 10):
    #                 val = pow(2, i)*pow(3, j)*pow(5, k)
    #                 ans = min(ans, a*i + b*j + c*k + abs(n - val)*(d))
    # print(ans)
                    
    print(solve(n, a, b, c,d))
    
t = int(input())
for _ in range(t):
    solve2()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import heapq
T = int(input())
# T = 1
for t in range(T):
    N, A, B, C, D = [int(x) for x in input().split()]
    # N, A, B, C, D = 29384293847243, 454353412, 332423423, 934923490, 1
    # import pdb
    # pdb.set_trace()
    MIN_COST = min(A, B, C, D)
    headm = {0: 0}
    head = [(0, 0)]
    heapq.heapify(head)

    tailm = {N: 0}
    tail = [(0, N)]
    heapq.heapify(tail)

    answer = 1e+99

    def putHead(p, c):
        global answer
        if p < 0:
            return
        if headm.get(p, 1e+99) > c:
            headm[p] = c
            heapq.heappush(head, (c, p))
            if p in tailm:
                v = c + tailm[p]
                if v < answer:
                    answer = v

    def stepHead():
        global lastHeadCost
        cost, position = heapq.heappop(head)
        lastHeadCost = cost
        if headm[position] > cost:
            return

        putHead(position * 2, cost + A)
        putHead(position * 3, cost + B)
        putHead(position * 5, cost + C)
        putHead(position + 1, cost + D)
        putHead(position - 1, cost + D)

    def putTail(p, c):
        global answer
        if p < 0:
            return
        if tailm.get(p, 1e+99) > c:
            tailm[p] = c
            heapq.heappush(tail, (c, p))
            v = c + headm.get(p, p * D)
            if v < answer:
                answer = v

    def stepTail():
        global lastTailCost
        cost, position = heapq.heappop(tail)
        lastTailCost = cost
        if tailm[position] > cost:
            return
        if position % 2 == 0:
            putTail(position // 2, cost + A)
        else:
            putTail((position+1) // 2, cost + A + D)
            putTail((position-1) // 2, cost + A + D)

        if position % 3 == 0:
            putTail(position // 3, cost + B)
        elif position % 3 == 1:
            putTail((position-1) // 3, cost + B + D)
            putTail((position+2) // 3, cost + B + D * 2)
        else:
            putTail((position+1) // 3, cost + B + D)
            putTail((position-2) // 3, cost + B + D * 2)

        if position % 5 == 0:
            putTail(position // 5, cost + C)
        elif position % 5 == 1:
            putTail((position-1) // 5, cost + C + D)
            putTail((position+4) // 5, cost + C + D * 4)
        elif position % 5 == 2:
            putTail((position-2) // 5, cost + C + D * 2)
            putTail((position+3) // 5, cost + C + D * 3)
        elif position % 5 == 3:
            putTail((position+2) // 5, cost + C + D * 2)
            putTail((position-3) // 5, cost + C + D * 3)
        elif position % 5 == 4:
            putTail((position+1) // 5, cost + C + D)
            putTail((position-4) // 5, cost + C + D * 4)

        # putTail(position + 1, cost + D)
        # putTail(position - 1, cost + D)

    lastHeadCost = lastTailCost = 0
    while True:
        if head[0][0] < tail[0][0] and False:
            # print("head")
            stepHead()
        else:
            # print("tail")
            stepTail()
        # print(lastHeadCost + lastTailCost + MIN_COST)
        if lastHeadCost + lastTailCost + MIN_COST >= answer:
            print(answer)
            break

Submission status: Wrong Answer

Solution code:
import math
T = int(input())
for i in range(T):
    N,A,B,C,D = map(int,input().split())
    ans = float("inf")
    ma = int(math.log2(30*N))
    for a in range(ma+1):
        M = int(30*N/(2.0**a))
        mb = int(math.log(M,3))
        for b in range(mb+1):
            L = int(M/(3.0**b))
            mc = int(math.log(L,5))
            for c in range(mc+1):
                p = abs(N - (2**a)*(3**b)*(5**c))
                d = 1
                a0,b0,c0 = a,b,c
                while(p > 0):
                    m = 5
                    if a0 and (not b0 or p%2 <= min([p%3,3-p%3])) and (not c0 or p%2 <= min([p%5,5-p%5])):
                        a0 -= 1
                        d += p%2
                        p = p//2
                    elif b0 and (not c0 or min([p%3,3-(p%3)]) <= min([p%5,5-(p%5)])):
                        b0 -= 1
                        if p%3 <= 3-p%3:
                            d += p%3
                            p = p//3
                        else:
                            d += 3-(p%3)
                            p = p//3+1
                    elif c0:
                        c0 -= 1
                        if p%5 <= 5-(p%5):
                            d += p%5
                            p = p//5
                        else:
                            d +=5-(p%5)
                            p = p//5+1
                    else:
                        d += p
                        p = 0
                s = A*a+B*b+C*c+D*d
                if s <= ans:
                    ans = s
    print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
T = int(input())
for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    o = sorted(((A, 2), (B, 3), (C, 5)), reverse=True)
    ans = 0
    x = N
    while x != 0:
        for num, m in o:
            if x % m == 0:
                x //= m
                ans += num
                break
        else:
            for num, m in o:
                if (x - 1) % num == 0:
                    x -= 1
                    break
                elif (x + 1) % num == 0:
                    x += 1
                    break
            else:
                x -= 1
            ans += D
    print(ans)

Submission status: Wrong Answer

Solution code:
t=int(input())
for loopi in range(t):
  n,a,b,c,d=list(map(int,input().split()))
  minest=10**40
  dd={n:0}
  while 1:
    newd={}
    for i in dd:
      if i%2:
        l=int((i-1)/2)
        if l in newd:
          newd[l]=min(dd[i]+min(a+d,(i-l)*d),newd[l])
        else:
          newd[l]=dd[i]+min(a+d,(i-l)*d)
        l=int((i+1)/2)
        if l in newd:
          newd[l]=min(dd[i]+min(a+d,(i-l)*d),newd[l])
        else:
          newd[l]=dd[i]+min(a+d,(i-l)*d)
      else:
        l=int(i/2)
        if l in newd:
          newd[l]=min(dd[i]+min(a,l*d),newd[l])
        else:
          newd[l]=dd[i]+min(a,l*d)
      l=int((i-(i+1)%3+1)/3)
      if l in newd:
        newd[l]=min(dd[i]+min(d*((i+1)%3-1)**2+b,(i-l)*d),newd[l])
      else:
        newd[l]=dd[i]+min(d*((i+1)%3-1)**2+b,(i-l)*d)
      l=int((i-(i+2)%5+2)/5)
      if l in newd:
        newd[l]=min(dd[i]+min(d*int((((i+2)%5-2)**2)**0.5)+c,(i-l)*d),newd[l])
      else:
        newd[l]=dd[i]+min(d*int((((i+2)%5-2)**2)**0.5)+c,(i-l)*d)
    if 1 in newd:
      mmm=newd.pop(1)
      if minest>mmm:
        minest=mmm
    if 0 in newd:
      newd.pop(0)
    if len(newd)==0:
      break
    dd=newd
  print(minest+d)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import heapq
T = int(input())
# T = 1
for t in range(T):
    N, A, B, C, D = [int(x) for x in input().split()]
    # N, A, B, C, D = 29384293847243, 454353412, 332423423, 934923490, 1
    # import pdb
    # pdb.set_trace()
    MIN_COST = min(A, B, C, D)
    headm = {0: 0}
    head = [(0, 0)]
    heapq.heapify(head)

    tailm = {N: 0}
    tail = [(0, N)]
    heapq.heapify(tail)

    answer = 1e+99

    def putHead(p, c):
        global answer
        if p < 0:
            return
        if headm.get(p, 1e+99) > c:
            headm[p] = c
            heapq.heappush(head, (c, p))
            if p in tailm:
                v = c + tailm[p]
                if v < answer:
                    answer = v

    def stepHead():
        global lastHeadCost
        cost, position = heapq.heappop(head)
        lastHeadCost = cost
        if headm[position] > cost:
            return

        putHead(position * 2, cost + A)
        putHead(position * 3, cost + B)
        putHead(position * 5, cost + C)
        putHead(position + 1, cost + D)
        putHead(position - 1, cost + D)

    def putTail(p, c):
        global answer
        if p < 0:
            return
        if tailm.get(p, 1e+99) > c:
            tailm[p] = c
            heapq.heappush(tail, (c, p))
            v = c + headm.get(p, p * D)
            if v < answer:
                answer = v

    def stepTail():
        global lastTailCost
        cost, position = heapq.heappop(tail)
        lastTailCost = cost
        if tailm[position] > cost:
            return
        if position % 2 == 0:
            putTail(position // 2, cost + A)
        else:
            putTail((position+1) // 2, cost + A + D)
            putTail((position-1) // 2, cost + A + D)

        if position % 3 == 0:
            putTail(position // 3, cost + B)
        elif position % 3 == 1:
            putTail((position-1) // 3, cost + B + D)
        else:
            putTail((position+1) // 3, cost + B + D)

        if position % 5 == 0:
            putTail(position // 5, cost + C)
        elif position % 5 == 1:
            putTail((position-1) // 5, cost + C + D)
        elif position % 5 == 2:
            putTail((position-2) // 5, cost + C + D * 2)
        elif position % 5 == 3:
            putTail((position+2) // 5, cost + C + D * 2)
        elif position % 5 == 4:
            putTail((position+1) // 5, cost + C + D)

        # putTail(position + 1, cost + D)
        # putTail(position - 1, cost + D)

    lastHeadCost = lastTailCost = 0
    while True:
        if head[0][0] < tail[0][0] and False:
            # print("head")
            stepHead()
        else:
            # print("tail")
            stepTail()
        # print(lastHeadCost + lastTailCost + MIN_COST)
        if lastHeadCost + lastTailCost + MIN_COST >= answer:
            print(answer)
            break

Submission status: Wrong Answer

Solution code:
t = int(input())

for i in range(t):
    N,a,b,c,d = map(int, input().split())
    ans = d #コイン枚数
    n = 1
    while (n != N):
        if N > n*5-2 :
            ans += c
            n *= 5
        elif N > n*3-2 and b<(a*2):
            ans += b
            n *= 3
        elif N > n*2-2 and abs(N-n) > 2:
            ans += a
            n *= 2
        else:
            ans += d
            if n < N:
                n += 1
            else:
                n -= 1
        print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def even(n):
  c1 = five(n)
  c2 = three(n)
  c3 = two(n)
  return c1*c+c2*b+c3*a+d


def odd(n):
  x = n-1
  c1 = five(x)
  c2 = three(x)
  c3 = two(x)
  return c1*c+c2*b+c3*a+2*d


def five(n):
  count1 = 0
  while(n% 5 != 0):
    n=n/5
    count1+=1
  return count1


def two(n):
  count2 = 0
  while(n% 2 != 0):
    n=n/2
    count2+=1
  return count2

def three(n):
  count3 = 0
  while(n % 3 != 0):
    n=n/3
    count3 += 1
  return count3


t = int(input())
for i in range(t-1):
  n, a, b, c, d = map(int, input().split())
if n % 2 == 0:
  even(n)
else:
  odd(n)

Submission status: Wrong Answer

Solution code:
t = input()
n,a,b,c,d = map(int,input().split())
count = 0

Submission status: Wrong Answer

Solution code:
import math
T = int(input())
for i in range(T):
    N,A,B,C,D = map(int,input().split())
    ans = float("inf")
    ma = int(math.log2(30*N))
    for a in range(ma+1):
        M = int(30*N/(2.0**a))
        mb = int(math.log(M,3))
        for b in range(mb+1):
            L = int(M/(3.0**b))
            mc = int(math.log(L,5))
            for c in range(mc+1):
                p = abs(N - (2**a)*(3**b)*(5**c))
                d = 1
                a0,b0,c0 = a,b,c
                while(p > 0):
                    m = 5
                    if a0 and p%2 <= min([p%3,3-p%3]) and p%2 <= min([p%5,5-p%5]):
                        a0 -= 1
                        d += p%2
                        p = p//2
                    elif b0:
                        b0 -= 1
                        if p%3 <= 3-p%3:
                            d += p%3
                            p = p//3
                        else:
                            d += 3-(p%3)
                            p = p//3+1
                    elif c0:
                        c0 -= 1
                        if p%5 <= 5-(p%5):
                            d += p%5
                            p = p//5
                        else:
                            d +=5-(p%5)
                            p = p//5+1
                    else:
                        d += p
                        p = 0
                s = A*a+B*b+C*c+D*d
                if s <= ans:
                    ans = s
    print(ans)

Submission status: Wrong Answer

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

    def cost(x):
        tmp = 0
        while x > 0:
            if x % 5 == 0:
                tmp += c
                x = x // 5
            elif x % 3 == 0:
                tmp += b
                x = x // 3
            elif x % 2 == 0:
                tmp += a
                x = x // 2
            else:
                x -= 1
                tmp += d
        return tmp

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

        x = cost(n + 1) + d
        y = cost(n)
        z = cost(n - 1) + d
        ans = min([x, y, z])
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
t = int(input())

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

Submission status: Wrong Answer

Solution code:
DP = {}

def solve(n, a, b, c, d, did_plus=False):
    if n <= 0: 
        return 0
    if n == 1: 
        return d
    if n in DP:
        return DP[n]
    ans = float('inf')
    for i in range(-4, 5):
        if did_plus:
            if i > 0:
                continue
        num = n + i
        trash = abs(i)*d

        if num%5 == 0 and num // 5 < n:
            ans = min(ans, solve(num//5, a, b, c, d, i>=0) + min(c, d*(num-(num//5))) + trash)
        if num%3 == 0 and num // 3 < n:
            ans = min(ans, solve(num//3, a, b, c, d, i>=0) + min(b, d*(num-(num//3))) + trash)
        if num%2 == 0 and num // 2 < n:
            ans = min(ans, solve(num//2, a, b, c, d, i>=0) + min(a, d*(num-(num//2))) + trash)
        # print(str(n) + ' ' + str(ans) + ' ' + str(num) + ' ' + str(i))

    DP[n] = ans

    return ans

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

Submission status: Wrong Answer

Solution code:
import numpy as np

def col(N):
    count = [0, 0, 0, 1]
    i=0
    m = [2, 3, 5]
    while i < 3:
        if N % m[i] == 0:
            count[i] += 1
            N = N // m[i]
        else:
            i += 1
    if N != 1:
        count[3] += (N-1)
    # print(cost, count)
    return np.dot(np.array(cost), np.array(count))

if __name__ == "__main__":
    T=int(input())
    for _ in range(T):
        N,A,B,C,D = map(int, input().split())
        simple_sum = N * D
        cost = (A, B, C, D)
        ans = []
        ans.append(simple_sum)
        j=True
        ans.append(col(N))
        ans.append(col(N-1)+D)
        ans.append(col(N+1)+D)

        # print('ans', ans)
        print(min(ans))

Submission status: Wrong Answer

Solution code:
t=int(input())
x=1
while x<=t:
    n,a,b,c,d=map(int,input().split())
    print(a)
    x+=1

Submission status: Wrong Answer

Solution code:
T = int(input())
number = list()
for i in range(T):
    N, A, B, C, D = map(int, input().split())
    for i in range(T):
        num = 0
        if N == 0:
            num = 0
        while N != 0:
            if N % 5 == 0:
                N = N / 5
                num += C
            elif N % 3 == 0:
                N = N / 3
                num += B
            elif N % 2 == 0:
                N = N / 2
                num += A
            else: 
                N = N - 1
                num += D
        number.append(num)
for n in range(T + 1):
    if n % 2 == 0:
        print(number[n])

Submission status: Wrong Answer

Solution code:
t = int(input())

test_cases = []
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    test_cases.append([n, a, b, c, d])
print('10')

Submission status: Wrong Answer

Solution code:
t = int(input())
P = [list(map(int,input().split())) for i in range(t)]
print(t)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=input();
n,a,b,c,d = map(int, input().split());
print(n);

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

t = ni()

for _ in range(t):
    n,a,b,c,d = na()
    p2,p3,p5 = n*2,n*3,n*5
    ans = 1000000000000000000
    for i in range(61):
        ii = 2**i
        if ii > p2:
            break
        for j in range(39):
            jj = ii*(3**j)
            if jj > p3:
                break
            for k in range(27):
                kk = jj*(5**k)
                if kk > p5:
                    break
                x = a*i+b*j+c*k+abs(kk-n)*d
                ans = min(ans, x)
    print(ans+d)

Submission status: Wrong Answer

Solution code:
T=int(input())
g=0
co=0
for i in range(T):
    n,a,b,c,d=map(int, input().split())
    while g!=n:
        da=abs(2*g-n)
        db=abs(3*g-n)
        dc=abs(5*g-n)
        dda=abs(g+1-n)
        ddb=abs(g-1-n)
        tmp=min(da,db,dc,dda,ddb)
        if tmp==da:
            co+=a
            g=2*g
        elif tmp==db:
            co+=b
            g=3*g
        elif tmp==dc:
            co+=c
            g=5*g
        elif tmp==dda:
            co+=d
            g+=1
        else:
            co+=d
            g-=1
        print(n,g)
    print(co)

Submission status: Wrong Answer

Solution code:
import sys
sys.stdin.readline

T = int(input())
a = [[int(i) for i in input().split()] for j in range(T)]
ans = []
tiba = []

for i in range(T):
    tame = []
    s = a[i][0]
    two = s//2
    two_a = s % 2
    three = s//3
    three_a = s % 3
    five = s//5
    five_a = s % 5
    tame.append(a[i][1] * two + a[i][4] * two_a)
    tame.append(a[i][2] * three + a[i][4] * three_a)
    tame.append(a[i][3] * five + a[i][4] * five_a)
    tiba.append(min(tame))

print(tiba)

Submission status: Wrong Answer

Solution code:
def num_ratio(a,b,c):
    a = 2 / a
    b = 3 / b
    c = 5 / c

    if a > b and a > c:
        if b > c:
            return [2,3,5]
        else:
            return [2,5,3]
    elif b > a and b > c:
        if a > c:
            return [3,2,5]
        else:
            return [3,5,2]
    else:
        if a > b:
            return [5,2,3]
        else:
            return [5,3,2]

def check(n,result):
    if n == result:
        return True
    else:
        return False

def cul_coin(a,b,c,num):
    if num == 2:
        return a
    elif num == 3:
        return b
    else:
        return c

def find_result(n,a,b,c,d):
    coin = d
    result = 1
    li = num_ratio(a,b,c)

    tmp = li.pop(0)
    cul = int(n / tmp)
    coin += cul_coin(a,b,c,tmp) * cul
    result = result * cul * tmp
    if result + 1 == n:
        coin += d
        result += 1
    if check(n,result):
        return coin

    tmp = li.pop(0)
    cul = int(n / tmp)
    coin += cul_coin(a,b,c,tmp) * cul
    result = result * cul * tmp
    if result + 1 == n:
        coin += d
        result += 1
    if check(n,result):
        return coin

    tmp = li.pop(0)
    cul = int(n / tmp)
    coin += cul_coin(a,b,c,tmp) * cul
    result = result * cul * tmp
    if result + 1 == n:
        coin += d
        result += 1
    if check(n,result):
        return coin

        


t = int(input())

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

Submission status: Wrong Answer

Solution code:
t = int(input())
list = []
list1 = []
temp = []
x = 0
count = 0
for i in range(0, t):
    n,a,b,c,d = map(int, input().strip().split())
    list1.append(n)
    list1.append(a)
    list1.append(b)
    list1.append(c)
    list1.append(d)
    list.append(list1)
    list1 = []
print(list)
for i in list:
    index = 1
    for j in range(0, len(i)-1):
        if x == 0:
            x = 1
            count = count + i[len(i)-1]
        elif x>0 and x<i[0]:
            x = x*2
            count = count + i[index]
            index = index + 1
print(count)