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
from math import ceil, floor, sqrt, sin, cos, pi, log
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

t = int(input())
for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    now = {2: min(a+d, d+d), 3: b+d, 5: c+d}
    sep = d*n
    while True:
        if len(now) == 0: break
        pop_list = []
        dic = {}
        for k, v in now.items():
            if k == 0: continue
            if v >= sep: continue
            if k > n:
                sep = min(sep, v+d*(k - n))
                continue
            # a
            tugi = k * 2
            if tugi == n:
                sep = min(sep, v + a)
            else:
                cost = now[k] + a
                if tugi in now and now[tugi] < cost:
                    pass
                else:
                    if tugi in dic and dic[tugi] < cost:
                        pass
                    else: dic[tugi] = cost
            # b
            tugi = k * 3
            if tugi == n:
                sep = min(sep, v + b)
            else:
                cost = now[k] + b
                if tugi in now and now[tugi] < cost:
                    pass
                else:
                    if tugi in dic and dic[tugi] < cost:
                        pass
                    else: dic[tugi] = cost
            # c
            tugi = k * 5
            if tugi == n:
                sep = min(sep, v + c)
            else:
                cost = now[k] + c
                if tugi in now and now[tugi] < cost:
                    pass
                else:
                    if tugi in dic and dic[tugi] < cost:
                        pass
                    else: dic[tugi] = cost
            # d
            tugi = k + 1
            if tugi == n:
                sep = min(sep, v + d)
            else:
                cost = now[k] + d
                if tugi in now and now[tugi] < cost:
                    pass
                else:
                    if tugi in dic and dic[tugi] < cost:
                        pass
                    else: dic[tugi] = cost
            # e
            tugi = k - 1
            cost = now[k] + d
            if tugi in now and now[tugi] < cost:
                pass
            else:
                if tugi in dic and dic[tugi] < cost:
                    pass
                else: dic[tugi] = cost
        now = deepcopy(dic)
    print(sep)

Submission status: Wrong Answer

Solution code:
t = int(input())
# スペース区切りの整数の入力
for i in range(t):
    x = 0
    nn = 0
    n, a,b,c,d = map(int, input().split())
    if x == 0:
        x += 1
        nn += d
    
    while x != n:
        l = [abs(n-x*2),abs(n-x*3),abs(n-x*5),min(abs(n-(x+1)),abs(n-(x-1)))]
        #print(l)
        #print(x)
        #print(nn)
        min_indl = []
        mindL = 0
        flag = 0
        mins = abs(n-x*2)
        for f in range(4) :
            if mins >  l[f]:
                mins = l[f]
                mindL = f
                flag = 0
            elif mins == l[f]:
                flag = 1
                if mindL in min_indl:
                    min_indl.append(f)
                else:
                    min_indl = [mindL,f]
                    
        if flag == 0:
            if mindL ==0:
                nn += a
                x = x*2
            elif mindL ==1:
                nn += b
                x = x*3
            elif mindL ==2:
                nn += c
                x = x*5
            elif mindL ==3:
                nn += d
                if abs(n-(x+1))<abs(n-(x-1)):
                    x = x +1
                elif abs(n-(x+1))>abs(n-(x-1)):
                    x = x -1
                else:
                 print("えらーC")   
            else:
                print("えらーA")
        elif flag == 1:
            cos = 0
            cosB =0
            cosind =0
            flagB = 0
            for j in min_indl:

                if j ==0:
                    cos= a
                elif j ==1:
                    cos= b
                elif j ==2:
                    cos= c
                elif j ==3:
                    cos= d
                else:
                    print("えらーD")
                if flag ==0:
                    flag +=1
                    cosB = cos
                    cosind = j
                else:
                    if cosB > cos:
                        cosB = cos
                        cosind = j
            if cosind ==0:
                nn += a
                x = x*2
            elif cosind ==1:
                nn += b
                x = x*3
            elif cosind ==2:
                nn += c
                x = x*5
            elif cosind ==3:
                nn += d
                if abs(n-x+1)<abs(n-(x-1)):
                    x = x +1
                elif abs(n-x+1)>abs(n-(x-1)):
                    x = x -1
                else:
                 print("えらーF")   

        #print(x)
        #print(nn)
    print (nn)

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('count',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)
        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:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    pq = [(0, N)]
    used = set()
    while pq:
        c, x = heappop(pq)
        if x in used:
            continue
        used.add(x)
        if x == 1:
            print(c + D)
            break
        heappush(pq, (c + D * (x - 1), 1))
        if x % 2 == 0:
            heappush(pq, (c + A, x // 2))
        else:
            heappush(pq, (c + D + A, (x - 1) // 2))
            heappush(pq, (c + D + A, (x + 1) // 2))
        if x % 3 == 0:
            heappush(pq, (c + B, x // 3))
        else:
            a = x // 3 * 3
            b = a + 3
            heappush(pq, (c + D * (x - a) + B, a // 3))
            heappush(pq, (c + D * (b - x) + B, b // 3))
        if x % 5 == 0:
            heappush(pq, (c + C, x // 5))
        else:
            a = x // 5 * 5
            b = x + 5
            heappush(pq, (c + D * (x - a) + C, a // 5))
            heappush(pq, (c + D * (b - x) + C, b // 5))

Submission status: Wrong Answer

Solution code:
T=int(input())
def u(n,c):
    global d
    if n==1:
        return 0
    if n%2:
        if n//2 not in d or d[n//2]>c+A+D:
            d[n//2]=c+A+D
            u(n//2,c+A+D)
    else:
        if n//2 not in d or d[n//2]>c+A:
            d[n//2]=c+A
            u(n//2,c+A)
    if n%3<=1:
        if n//3 not in d or d[n//3]>c+B+n%3*D:
            d[n//3]=c+B+n%3*D
            u(n//3,c+B+n%3*D)
    else:
        if n//3+1 not in d or d[n//3+1]>c+B+D:
            d[n//3+1]=c+B+D
            u(n//3+1,c+B+D)
    if n%5<=2:
        if n//5 not in d or d[n//5]>c+C+n%5*D:
            d[n//5]=c+C+n%5*D
            u(n//5,c+C+n%5*D)
    else:
        if n//5+1 not in d or d[n//5+1]>c+C+(5-n%5)*D:
            d[n//5+1]=c+C+(5-n%5)*D
            u(n//5+1,c+C+n%5*D)
for i in range(T):
    N,A,B,C,D=map(int,input().split())
    d={}
    u(N,0)
    a=10**30
    if d:
        for j,n in d.items():
            t=D*j+n
            if t<a:
                a=t
        print(a)
    else:
        print(D)

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
  min_value = N + 1
  queue = []
  heapq.heappush(queue, (0, N))

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

    c, n = heapq.heappop(queue)

    if n >= min_value:
      continue

    if n == 0:
      print(c)
      return

    min_value = 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:
S=input()

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
import heapq
import cProfile
from collections import Counter, defaultdict, deque
from functools import reduce
import math

def get_int():
    return int(stdin.readline().strip())


def get_tuple():
    return map(int, stdin.readline().split())


def get_list():
    return list(map(int, stdin.readline().split()))


def solve():
    n,a,b,c,d = map(int,input().strip().split())
    p = max(a,b,c,d)
    limit = math.ceil(p / 30)
    pre_ans = 0
    if n>limit*30:
        dp = [0, d]
        i = 2
        while i<=limit*30+1:
            ans = dp[-1]+d
            if i%2==0:
                ans = min(ans,dp[i//2]+a)
            if i%3==0:
                ans = min(ans, dp[i // 3 ] + b)
            if i%5==0:
                ans = min(ans, dp[i // 5] + c)
            dp[-1] = min(ans+d,dp[-1])
            dp.append(ans)
            i += 1
        period = dp[-2]
        ans += period*limit
    dp = [0, d]
    i = 2
    while i<=n-(limit-1)*30+1:
        ans = dp[-1] + d
        if i % 2 == 0:
            ans = min(ans, dp[i // 2] + a)
        if i % 3 == 0:
            ans = min(ans, dp[i // 3] + b)
        if i % 5 == 0:
            ans = min(ans, dp[i // 5] + c)
        dp[-1] = min(ans + d, dp[-1])
        dp.append(ans)
        i += 1
    #print(dp)
    print(pre_ans+dp[-2])

def main():
    solve()


TestCases = True

if TestCases:
    for i in range(get_int()):
        main()
else:
    main()

Submission status: Wrong Answer

Solution code:
T = int(input())

qs = list()

def dfs(n):
    global ans
    if n == 0:
        ans = [0] * 4
        return True

    if n % 2 == 0 and dfs(n // 2):
        ans[0] += a
        return True
    if n % 3 == 0 and dfs(n // 3):
        ans[1] += b
        return True
    if n % 5 == 0 and dfs(n // 5):
        ans[2] += c
        return True
    if dfs(n - 1):
        ans[3] += d
        return True
    if dfs(n + 1):
        ans[3] += d
        return True

    return False

for i in range(T):
    qs.append(map(int, input().split()))

for q in qs:
    n, a, b, c, d = q
    dfs(n)
    print(ans)

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 and p%2 > min([p%3,3-p%3])) and not(c0 and p%2 > min([p%5,5-p%5])):
                        a0 -= 1
                        d += p%2
                        p = p//2
                    elif b0 and not (c0 and 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:
import copy


def prime_factorize(n, a, b, c, d, ans, tmp_dict={1: 0, 2: 0, 3: 0, 5: 0}):
    tmp = copy.copy(tmp_dict)
    if n == 1:
        tmp[1] += 1
        ans.append(tmp[2] * a + tmp[3] * b + tmp[5] * c + tmp[1] * d)
        return
    if n % 2 != 0:
        tmp[1] += 1
        return (
            prime_factorize(n - 1, a, b, c, d, ans, tmp),
            prime_factorize(n + 1, a, b, c, d, ans, tmp),
        )
    while n % 2 == 0:
        if a <= n * d:
            tmp[2] += 1
        else:
            tmp[1] += n - n // 2
        n //= 2
    while n % 3 == 0:
        if b <= n * d:
            tmp[3] += 1
        else:
            tmp[1] += n - n // 3
        n //= 3
    while n % 5 == 0:
        if c <= n * d:
            tmp[5] += 1
        else:
            tmp[1] += n - n // 5
        n //= 5
    return prime_factorize(n, a, b, c, d, ans, tmp)


def main():
    t = int(input())
    for _ in range(t):
        n, a, b, c, d = map(int, input().split())
        ans = []
        prime_factorize(n, a, b, c, d, ans)
        print(min(ans))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:





class coinManager:
    haveNum = 0
    spentCoin = 0
    target = 0
    costA = 0
    costB = 0
    costC = 0
    cosdD = 0

    minCost = ""

    def __init__(self, target: int, A: int, B: int, C: int, D: int):
        self.target = target
        self.costA = A
        self.costB = B
        self.costC = C
        self.costD = D

        self.setMinCost()

    def setMinCost(self):
        if self.costA * 1.5 <= self.costB and self.costA * 5 / 2 <= self.costC:
            self.minCost = "A"
        elif self.costA * 1.5 >= self.costB and self.costB * 5 / 3 <= self.costC:
            self.minCost = "B"
        elif self.costA * 5 / 2 >= self.costC and self.costB * 5 / 3 >= self.costC:
            self.minCost = "B"
        else:
            print("NNNNNNNNNNNNNNNNNNNNNNN")

        print(self.minCost)


    def checkTargetAndHaveNum(self) -> bool:
        return True if self.target == self.haveNum else False

    def remainNum(self) -> int:
        return self.target - self.haveNum

    def printCoin(self):
        print("-----Coin-----")
        print("target  = ", self.target)
        print("haveNum = ", self.haveNum)
        print("remain  = ", self.remainNum())
        print()

    def firstStep(self):
        self.spentD_increment()
        self.printCoin()


    def spentA(self):
        self.haveNum *= 2
        self.spentCoin += self.costA

    def spentB(self):
        self.haveNum *= 3
        self.spentCoin += self.costB

    def spentC(self):
        self.haveNum *= 5
        self.spentCoin += self.costC

    def spentD_increment(self):
        self.haveNum += 1
        self.spentCoin += self.costD

    def spentD_decrement(self):
        self.haveNum -= 1
        self.spentCoin += self.costD




T = int(input())

Input = []

for _ in range(T):
    line = list(map(int, input().split()))
    Input.append(line)

result = []




for line in Input:
    coins = coinManager(*line)
    coins.printCoin()

Submission status: Wrong Answer

Solution code:
T = int(input())

Submission status: Wrong Answer

Solution code:
int(input())

Submission status: Wrong Answer

Solution code:
T = int(input())

import numpy as np
import heapq

def put(num):
    heapq.heappush(heap, -num)

def pop():
    return heapq.heappop(heap)*(-1)

def empty():
    return (len(heap) == 0)

def register(num, cost):
    if num in d:
        if cost > d[num]:
            return False
    d[num] = cost
    if cost < 0:
        sys.exit()
    return True

def register_multi(nums, costs):
    res = []
    for num, cost in zip(nums, costs):
        if register(num, cost):
            res += [num]
    return res

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

    d = {}
    d[N] = 0
    pushed = {}
    put(N)

    while not empty():
        start = pop()
        if start in pushed:
            continue
        pushed[start] = 1

        station = [start - (start % 2), start + (start % 2)]
        d3 = start % 3
        station += [start - d3] if d3 <= 1 else [start - d3 + 3]
        d5 = start % 5
        station += [start - d5] if d5 <= 2 else [start - d5 + 5]

        ustation = np.unique(station)
        scosts = np.abs(ustation - start) * D

        rstatrion = register_multi(ustation, d[start] + scosts)
        rstatrion = sorted(rstatrion)[::-1]

        for s in rstatrion:
            if s % 2 == 0:
                dst = s // 2
                minc = A if A / D < dst else dst * D
                flag = register(dst, minc + d[s])
                if flag:
                    put(dst)
            if s % 3 == 0:
                dst = s // 3
                minc = B if B / D < dst else dst * 2 * D
                flag = register(dst, minc + d[s])
                if flag:
                    put(dst)
            if s % 5 == 0:
                dst = s // 5
                minc = C if C / D < dst else dst * 4 * D
                flag = register(dst, minc + d[s])
                if flag:
                    put(dst)
    print(d[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  not(b0 and p%2 > min([p%3,3-p%3])) and not(c0 and p%2 > min([p%5,5-p%5])):
                        a0 -= 1
                        d += p%2
                        p = p//2
                    elif b0 and not (c0 and 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:
import copy

t = int(input())


def prime_factorize(n, tmp_dict={1: 0, 2: 0, 3: 0, 5: 0}):
    global a, b, c, d, ans
    tmp = copy.copy(tmp_dict)
    if n == 1:
        tmp[1] += 1
        ans.append(tmp[2] * a + tmp[3] * b + tmp[5] * c + tmp[1] * d)
        return
    if n % 2 != 0:
        tmp[1] += 1
        return prime_factorize(n - 1, tmp), prime_factorize(n + 1, tmp)
    while n % 2 == 0:
        if a <= n * d:
            tmp[2] += 1
        else:
            tmp[1] += n - n // 2
        n //= 2
    while n % 3 == 0:
        if b <= n * d:
            tmp[3] += 1
        else:
            tmp[1] += n - n // 3
        n //= 3
    while n % 5 == 0:
        if c <= n * d:
            tmp[5] += 1
        else:
            tmp[1] += n - n // 5
        n //= 5
    return prime_factorize(n, tmp)


for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    ans = []
    prime_factorize(n)
    print(min(ans))

Submission status: Wrong Answer

Solution code:
T = int(input())

import numpy as np
import heapq
heap = []

def put(num):
    heapq.heappush(heap, -num)

def pop():
    return heapq.heappop(heap)*(-1)

def empty():
    return (len(heap) == 0)

def register(num, cost):
    if num in d:
        if cost > d[num]:
            return False
    d[num] = cost
    return True

def register_multi(nums, costs):
    res = []
    for num, cost in zip(nums, costs):
        if register(num, cost):
            res += [num]
    return res
  
for _ in range(T):
    N, A, B, C, D = map(int, input().split())

    d = {}
    d[N] = 0
    pushed = {}
    put(N)

    while not empty():
        start = pop()
        if start in pushed:
            continue
        pushed[start] = 1

        station = [start - (start % 2), start + (start % 2)]
        d3 = start % 3
        station += [start - d3] if d3 <= 1 else [start - d3 + 3]
        d5 = start % 5
        station += [start - d5] if d5 <= 2 else [start - d5 + 5]

        ustation = np.unique(station)
        scosts = np.abs(ustation - start) * D

        rstatrion = register_multi(ustation, d[start] + scosts)
        rstatrion = sorted(rstatrion)[::-1]

        for s in rstatrion:
            if s % 2 == 0:
                dst = s // 2
                minc = A if A / D < dst else dst * D
                flag = register(dst, minc + d[s])
                if flag:
                    put(dst)
            if s % 3 == 0:
                dst = s // 3
                minc = B if B / D < dst else dst * 2 * D
                flag = register(dst, minc + d[s])
                if flag:
                    put(dst)
            if s % 5 == 0:
                dst = s // 5
                minc = C if C / D < dst else dst * 4 * D
                flag = register(dst, minc + d[s])
                if flag:
                    put(dst)
    print(d[0])

Submission status: Wrong Answer

Solution code:
t = int(input())
n = [0]*t
a = [0]*t
b = [0]*t
c = [0]*t
d = [0]*t

for i in range(t):
    n[i], a[i], b[i], c[i], d[i] = map(int, input().split())
    
#入力しかできん
#出るコンテスト間違えた

Submission status: Wrong Answer

Solution code:
T = int(input())
X = [list(map(int, input().split())) for _ in range(T)]

for i in range(T):
    print(sum(X[i]))

Submission status: Wrong Answer

Solution code:
T=int(input())
T_ans=[0]*T
ans=0
N_ans=0
for i in range(T):
    N,A,B,C,D=map(int, input().split()) 
    ans+=D
    N_ans+=1
print('ans')

Submission status: Wrong Answer

Solution code:
from collections import deque

T = int(input())
for _ in range(T):
  N,A,B,C,D = map(int, input().split())
  s = deque([2,3,5])

Submission status: Wrong Answer

Solution code:
import math

T=int(input())
ans_list=[]
for t in range(T):
    N,a,b,c,d=map(int,input().split())

    min_val = 99999999999999999999999

    vali=0
    numi=1
    for i in range(2+int(math.log(N)/math.log(2))):
        onumi=numi
        numi=2**i
        add=numi-onumi
        if a > d*add:
            vali+=d*add
        else:
            vali+=a

        numj=1
        valj=0
        for j in range(2+int(math.log(N/numi)/math.log(3))):
            onumj=numj
            numj=3**j
            add=numi*(numj-onumj)
            if b > d*add:
                valj+=d*add
            else:
                valj+=b


            numk=1
            valk=0
            for k in range(2+int(math.log(N/numi/numj)/math.log(5))):
                onumk=numk
                numk=5**k
                add=numi*numj*(numk-onumk)
                if c > d*add:
                    valk+=d*add
                else:
                    valk+=c


                val=d+vali+valj+valk+d*abs(N-numi*numj*numk)
                if min_val>val:
                    print(numi,numj,numk,val)
                    min_val=val
    
    ans_list.append(int(min_val))

for a in ans_list:
    print(a)

Submission status: Wrong Answer

Solution code:
t=int(input())
for _ in range(t):
    n,a,b,c,d=map(int,input().split())
    ans=10**20
    tmp=d
    i,j,k=0,0,0
    while pow(5,i)<=3*n:
        j=0
        while pow(5,i)*pow(3,j)<=3*n:
            k=0
            while pow(5,i)*pow(3,j)*pow(2,k)<=3*n:
                tmp=a*k+b*j+c*i+d
                if n-pow(5,i)*pow(3,j)*pow(2,k)>=0:
                    m=n-pow(5,i)*pow(3,j)*pow(2,k)
                    p=min(m//5,i)
                    m-=5*p
                    q=min(j,m//3)
                    m-=3*q
                    r=min(m//2,k)
                    m-=2*r
                    tmp+=(p+q+r+m)*d
                else:
                    tmp+=(pow(5,i)*pow(3,j)*pow(2,k)-n)*d
                ans=min(tmp,ans)
                k+=1
            j+=1
        i+=1
            
    print(ans)

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())
  L=list()
  a=math.floor(math.log(N,2))             
  b=math.floor(math.log(N,3))
  c=math.floor(math.log(N,5))
  for cc in range(c+1):
    for bb in range(b+1):
      for aa in range(a+1):
        Key=(2**aa)*(3**bb)*(5**cc)
        ans=(aa*A+bb*B+cc*C)
        L.append(D*(abs((N-Key)))+ans)
  print(min(L))

Submission status: Wrong Answer

Solution code:
T = int(input())
query = [0]*T
for i in range(T):
    query[i] = list(map(int,input().split()))
# print(query)
# A枚のコインを支払い、持っている数を 2倍する。 
# B枚のコインを支払い、持っている数を3倍する。
# C枚のコインを支払い、持っている数を 5倍する。
# D枚のコインを支払い、持っている数を 1増やす、
# または1減らす。
# 11 1 2 4 8
# N  A B C D
for i in range(T):
    A = query[i][1]*2.5
    B = query[i][2]/3*5
    C = query[i][3]/5 
    print(A,B,C)
    pay = min(A,(min(B,C)))
    N = query[i][0]
    # while all:
    #     if(N%2 != 0 and N%3 != 0 and N%5 != 0):
    #         if(N-1 % ==0):


    # have_num = 0
    # coin = 0
    # coin += query[i][4]
    # have_num += 1

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(-6, 7):
        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:
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)