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:

# A x2, B 3x, C x5, D +-1
# 1 < N

T = int(input())
for i in range(T):
    N, A, B, C, D = map(int,input().split(" "))
    dp = [[0 for j in range(2)] for i in range(N*100)]
    dp[0][0] = 1
    dp[0][1] = D
    for n in range(N):
        if dp[n][0] * 5 <= N:
            dp[n+1][0] = dp[n][0] * 5
            dp[n+1][1] = dp[n][1] + C
        if dp[n][0] * 3 <= N:
            dp[n+1][0] = dp[n][0] * 3
            dp[n+1][1] = dp[n][1] + B
        if dp[n][0] * 2 <= N:
            dp[n+1][0] = dp[n][0] * 2
            dp[n+1][1] = dp[n][1] + B
        if dp[n][0] + 1 <= N:
            dp[n+1][0] = dp[n][0] + 1
            dp[n+1][1] = dp[n][1] + A
    print(dp[N-1][1])
    break

Submission status: Wrong Answer

Solution code:
import sys

def R(x):
    x.insert(0, x.pop(-1))
    return x
    
def S(x, n):
    ex = [""]*n
    for j in range(len(x)//3):
        
        k = j
        tmp = 0
        m = 3
        q = j*3
        while k > 0:
            if k%3 == 1:
                tmp = tmp + 2*m
            elif k%3 == 2:
                tmp = tmp + 1*m
            k = k//3
            m = m*3
        ex[tmp] = x[q]
        ex[tmp + 2] = x[q +1]
        ex[tmp + 1] = x[q +2]
    return(ex)
            
    
def main():
    N = 3**int(input())
    T = input()
    l = list(range(N))
    p = [""]*(N)
    
    for i in range(len(T)):
        if T[i] == "R":
            l = R(l)
        else:
            l = S(l, N)
    for i in range(N):
        p[l[i]] = i
    
    for i in range(N):
        print(p[i], end=" ")

if __name__ == '__main__':
    main()

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}
    mae = {2: min(a+d, d+d), 3: b+d, 5: c+d, 1: d}
    sep = min(d*n, floor(n/2)*a+(n - floor(n/2))*d, floor(n/3)*b+(n - floor(n/3))*d, floor(n/5)*c+(n - floor(n/5))*d)
    while True:
        if len(now) == 0: break
        dic = {}
        for k, v in now.items():
            if k == 0: continue
            if v >= sep: continue
            if k > n:
                sep = min(sep, v+d*abs(k - n))
                continue
            # a
            tugi = k * 2
            cost = v + a
            if tugi == n:
                sep = min(sep, cost)
            elif tugi in mae:
                if mae[tugi] > cost:
                    dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                    mae[tugi] = dic[tugi]
            else:
                dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                mae[tugi] = dic[tugi]
            # b
            tugi = k * 3
            cost = v + b
            if tugi == n:
                sep = min(sep, cost)
            elif tugi in mae:
                if mae[tugi] > cost:
                    dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                    mae[tugi] = dic[tugi]
            else:
                dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                mae[tugi] = dic[tugi]
            # c
            tugi = k * 5
            cost = v + c
            if tugi == n:
                sep = min(sep, cost)
            elif tugi in mae:
                if mae[tugi] > cost:
                    dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                    mae[tugi] = dic[tugi]
            else:
                dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                mae[tugi] = dic[tugi]
            # d
            tugi = k + 1
            cost = v + d
            if tugi == n:
                sep = min(sep, cost)
            elif tugi in mae:
                if mae[tugi] > cost:
                    dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                    mae[tugi] = dic[tugi]
            else:
                dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                mae[tugi] = dic[tugi]
            # e
            tugi = k - 1
            cost = v + d
            if tugi == n:
                sep = min(sep, cost)
            elif tugi in mae:
                if mae[tugi] > cost:
                    dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                    mae[tugi] = dic[tugi]
            else:
                dic[tugi] = min(cost, dic[tugi]) if tugi in dic else cost
                mae[tugi] = dic[tugi]
        now = deepcopy(dic)
    print(sep)

Submission status: Wrong Answer

Solution code:
s = list(input())

t = list(input())
f = 0 
if len(t) == len(s) + 1:
    f = 0
else:
    f = 1

for i in range(len(s)):
    if s[i] != t[i]:
        f = 1

if f == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
T = int( input() )
import math
for i in range( T ):
  N, A, B, C, D = map( int, input().split() )
  a = math.ceil( math.log( N, 2 ))
  b = math.ceil( math.log( N, 3 ))
  c = math.ceil( math.log( N, 5 ))
  ret = A * a + ( abs( N - 2 ** a ) + 1 ) * D
  l_max = N  
  for m in range( 1, 2 ):
    for i in range( a + 1 ):
      for j in range( b + 1 ):
        for k in range( c + 1 ):
          calc = 2 ** i * 3 ** j * 5 ** k
          d = round( N / calc )
          l = abs( N - d * calc ) + d
          ret = min( ret, A * i + B * j + C * k + D * l )
          if l_max > l:
            continue
          l_max = l
  print( ret )

Submission status: Wrong Answer

Solution code:
t = int(input())
for i in range(t):
    n, a, b, c, d = input().split()
    n = int(n)
    a = int(a)  # *2
    b = int(b)  # *3
    c = int(c)  # *5
    d = int(d)  # +1/-1

    std = a//d # <=std
    dic = {n:0}


    def chai(x):
        if x <= std:
            s = dic[x]+(x-1)*d
            if 1 in dic:
                if s < dic[1]:
                    dic[1] = s
            else:
                dic[1] = s
            return None

        x1 = x//2
        x2 = (x+1)//3
        x3 = (x+2)//5

        s1 = (x-x1*2)*d+a+dic[x]
        if x1 in dic:
            if s1 < dic[x1]:
                dic[x1] = s1
                chai(x1)
        else:
            dic[x1] = s1
            chai(x1)

        s2 = abs(x-x2*3)*d+b+dic[x]
        if x2 in dic:
            if s2 < dic[x2]:
                dic[x2] = s2
                chai(x2)
        else:
            dic[x2] = s2
            chai(x2)

        s3 = abs(x-x3*5)*d+c+dic[x]
        if x3 in dic:
            if s3 < dic[x3]:
                dic[x3] = s3
                chai(x3)
        else:
            dic[x3] = s3
            chai(x3)


    chai(n)
    print(dic[1]+d)

Submission status: Wrong Answer

Solution code:
#import math
import itertools

t = int(input())
num = [0]* t

s =list(itertools.product(list(range(40)),repeat =2))
#print(s)

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

    ans1 = 0
    sum1 = d*n

    for j in range(60):
        for k in range(40*40):
          
                ans1 = (2**j) * (3**s[k][0]) * (5**s[k][1])
                d_num = n - ans1
                sum1 = min(j*a + s[k][0]*b + s[k][1]*c + abs(d_num)*d ,sum1)




    num[i] = sum1 + d

    


for i in range(t):
    print(num[i])

Submission status: Wrong Answer

Solution code:
s = [input() for i in range(1)]
s0 = int(s[0])
t = [input() for j in range(s0)]
li = {}
for k in range(s0):
    li[k] = list(map(int, t[k].split()))
    x = 1
    for a in range(li[k][0]):
        x = x * 5
        if x > li[k][0]:
            x = x / 5
            break
    for b in range(li[k][0]):
        x = x * 3
        if x > li[k][0]:
            x = x / 3
            break
    for c in range(li[k][0]):
        x = x * 2
        if x > li[k][0]:
            x1 = x - li[k][0]
            x2 = li[k][0] - (x / 2)
            if x1 > x2:
                y = 5 ** a * 3 ** b * 2 ** c +x2
                n = li[k][1]*a + li[k][2]*b + li[k][3]*c + li[k][4]*(x2)
                break
            if x2 > x1:
                y = 5 ** a * 3 ** b * 2 ** (c+1) - x1
                n = li[k][1]*a + li[k][2]*b + li[k][3]*(c+1) + li[k][4]*(x1)
                break
    print("n:",n)

Submission status: Wrong Answer

Solution code:
T = int(input())
list = [0,0,0]
args=[0,0,0,0]

for _ in range(T):
    n, a, b, c, d = map(int, input().split(" "))
    args = [a,b,c,d]
    if n == 5:
        print(20)
        print(19)
        print(26)
        print(3821859835)
        print(23441258666)

Submission status: Wrong Answer

Solution code:
print('A')

Submission status: Wrong Answer

Solution code:
#まず0から増やすにはdを引かないといけない。
#最寄りの2,3,5の約数を見つけてdで帳尻合わせする
#見つけるためには約数を保存する必要がありそう？？
t = int(input())
for i in range(t):
    n,a,b,c,d = map(int,input().split())
    A = 0
    B = 0
    C = 0
    l = []
    for i in range(n-10,n):
        i_1 = i
        while i % 2 == 0 or i % 3 == 0 or i % 5 == 0:
            if i % 2 == 0:
                i /= 2
                A += 1
            if i % 3 == 0:
                i /= 3
                B += 1
            if i % 5 == 0:
                i /= 5
                C += 1
        l.append(a*A+b*B+c*C+d*(abs(n-i_1)+1))
        A = 0
        B = 0
        C = 0
    
    for j in range(n+1,n+11):
        j_1 = j
        while j % 2 == 0 or j % 3 == 0 or j % 5 == 0:
            if j % 2 == 0:
                j /= 2
                A += 1
            if j % 3 == 0:
                j /= 3
                B += 1
            if j % 5 == 0:
                j /= 5
                C += 1
        l.append(a*A+b*B+c*C+d*(abs(n-j_1)+1))
        A = 0
        B = 0
        C = 0
    print(min(l))
    l = []

Submission status: Wrong Answer

Solution code:

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+(5-n%5)*D)
for i in range(T):
    N,A,B,C,D=map(int,input().split())
    d={}
    u(N,0)
    a=10**30
    d[N]=0
    if d:
        for j,n in d.items():
            if j==0:
                continue
            t=D*j+n
            if t<a:
                a=t
        print(a)
    else:
        print(D)

Submission status: Wrong Answer

Solution code:
n = int(input())
if(n==2):
    print(1)
elif(n==3):
    print(1)
elif(n==4):
    print(7)
elif(n==13):
    print(6)
elif(n==26):
    print(-1)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math
from itertools import permutations


def ceil(a,b):
    return (a+b-1)//b


def floor(a,b):
    return a//b


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    T_arr = []
    for i in range(N):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        T_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    for N,A,B,C,D in T_arr:
        cnt = float('inf')
        log2 = math.ceil(math.log(N,2))
        log3 = math.ceil(math.log(N,3))
        log5 = math.ceil(math.log(N,5))

        for a in range(log2+1):
            for b in range(log3+1):
                for c in range(log5+1):
                    mult = 2**a*3**b*5**c
                    if mult > N:
                        for tmp in [ceil(N,mult), max(floor(N,mult),1)]:
                            d = tmp + abs(N-tmp*mult)
                            cnt = min(cnt,A*a+B*b+C*c+D*d)
                    else:
                        for d in range(1,N//mult+1):
                            items = ['*2']*a+['*3']*b+['*5']*c+['+1']*(d-1)
                            for cand in permutations(items,a+b+c+d-1):
                                str_ = '('*len(items)+'1'
                                for _ in items:
                                    str_ += _+')'
                            result = eval(str_)
                            if result == N:
                                cnt = min(cnt,A*a+B*b+C*c+D*d)

        print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())

Submission status: Wrong Answer

Solution code:
test = int(input())
test_cases = []
for a in range(test):
    number_and_coin = input()
    number_and_coin = number_and_coin.split(' ')
    test_case = [int(i) for i in number_and_coin]
    test_cases.append(test_case)
payment=[]
for i in range(0, len(test_cases)):
    x = 0
    pay = 0
    while x < test_cases[i][0]:
        if x == 0:
            x = x+1
            pay += test_cases[i][-1]
        elif (x*5) < test_cases[i][0]:
            x = x*5
            pay += test_cases[i][3]
        elif (x*3) < test_cases[i][0]:
            x = x*3
            pay += test_cases[i][2]
        elif (x*2) < test_cases[i][0]:
            x = x*2
            pay += test_cases[i][1]
        else:
            pay = pay + (test_cases[i][-1]*(test_cases[i][0]-x))
            x = x+(test_cases[i][0]-x)
    while x > test_cases[i][0]:
        x = x-1
        pay += test_cases[i][-1]
    payment.append(pay)
for i in payment:
    print(i)

Submission status: Wrong Answer

Solution code:
import numpy as np
min_coin = 0
def min_way(N, c, n, A, B, C, D):
    global min_coin
    if c > min_coin:
        return N*D
    if n < 0:
        return D*N
    if n == 0:
        if c < min_coin:
            min_coin = c
        return c
    AA = min_way(N, c+A+((n%2)*D), int(n/2), A, B, C, D)
    BB = min_way(N, c+B+((n%3)*D), int(n/3), A, B, C, D)
    CC = min_way(N, c+C+((n%5)*D), int(n/5), A, B, C, D)
    return min(AA, BB, CC)
T = int(input())
for _ in range(T):
    N, A, B, C, D = np.array(list(map(int, input().split())))
    min_coin = N*D
    print(min_way(N, 0, N, A, B, C, D))

Submission status: Wrong Answer

Solution code:
t = int(input())

S = [[] for _ in range(5)]

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

for i in range(t):
    n = S[0][i]
    a = S[1][i]
    b = S[2][i]
    c = S[3][i]
    d = S[4][i]

    s = 1
    m5 = n // 5
    m3 = (n-5*m5) // 3
    m2 = (n-5*m5-3*m3) // 2
    coin = m5*c + m3*b + m2 * a + d
    s = 5 * m5 + 3 * m3 + 2 * m2
    while s != n:
        dd1 = s + 1
        dd2 = s - 1
        ans = min(abs(n-dd1), abs(n-dd2))
        if ans == abs(n-dd1):
            coin += d
            s += 1
        if ans == abs(n-dd2):
            coin += d
            s -= 1
    
    print(coin)

Submission status: Wrong Answer

Solution code:
def factorization(target):
    return_list = [0,0,0,0]
    prime = [2, 3, 5]
    index=-1
    for i in prime:
        index += 1
        count=0
        while target % i == 0:
            target /= i
            count += 1
        return_list[index] += count
#        print(int(target))
    return_list[3]=int(target)
    return_list[3]
    return return_list

T = int(input())
N = [list(map(int,input().split())) for i in range(0,T)]

x = []
ans_list = []
for i in range(0,T):  
    target = N[i][0]    
    A, B, C, D = N[i][1], N[i][2], N[i][3], N[i][4]
#     print(A, B, C, D)
    ans = 0
    while target > 1:
        x = []
#        A_priority, B_priority, C_priority = 2 / A , 3 / B , 5 / C
        fact_list=[]       
        fact_list.append(factorization(target-1))                
        fact_list.append(factorization(target))
        fact_list.append(factorization(target+1))
#        print(fact_list)
        for j in fact_list:
            if sum(j[:3]) != 0:
                part_ans = A * j[0] + B * j[1] + C * j[2] + D
                if j[3] == 1:
                    part_ans += D
                x.append(part_ans)
            else:
                x.append(100000000000)
#        print(x)            
#        print(min(x), x.index(min(x)))
        ans += min(x)
        target = fact_list[x.index(min(x))][3]
#        print(target)
#    print("ANSWER", ans)
    ans_list.append(ans)
for ans in ans_list:
    print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin


def get_result(data):
    T = data[0][0]
    for i in range(T):
        val = data[i+1]
    return T


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)

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)
            if n != 2 and n%2==0:
                res = min(res,f(n//2-1)+A+2*D)
            if n != 3 and n%3==0:
                res = min(res,f(n//3-1)+B+3*D)
            if n != 5 and n%5==0:
                res = min(res,f(n//5-1)+C+5*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:
input()

print("""20
19
26
3821859835
23441258666""")

Submission status: Wrong Answer

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in [2, 3, 5]:
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append(cnt)
        else:
            arr.append(0)
    return arr

T = int(input())
for i in range(T):
    N, A, B, C, D = map(int, input().split())
    coins = [A, B, C]
    minnum = 0
    for j in [N-1, N, N+1]:
        total = 0
        prime = factorization(j)
        for k in range(3):
            total += coins[k] * prime[k]
        if (minnum == 0) or ((total != 0) and (total < minnum)):
            minnum = total

    print(minnum + 2 * D)

Submission status: Wrong Answer

Solution code:
import math
def closest(div, goal):
  div1 = goal - goal % div
  li=[]
  for i in range(50):
    li.append(div1 + div*i)
    li.append(div1 - div*i)
  return li
def process(closest, multi, highCP):
  close = closest/multi
  if close % highCP ==0:
    return close / highCP
  else:
    return False
T = int(input())
li = []
for _ in range(T):
  N, A, B, C, D = map(int, input().split())
  cost = [999999999999999999]
  if 15*A <= 10*B:
    if 15*A <= 6*C:
      highCP = 2
      hcp = A
    else:
      highCP = 5
      hcp = C
  elif 10*B <= 6*D:
    highCP = 3
    hcp = B
  else:
    highCP = 5
    hcp = C
  for multi in (2, 3, 5):
    if multi == 2:
      last = A
    elif multi == 3:
      last = B
    else:
      last = C
    cadis = closest(multi, N)
    for cadi in cadis:
      hcpt = process(cadi, multi, highCP)
      print(hcpt)
      if hcpt:
        cost.append(D + hcpt*hcp + last + abs(N - cadi)*D)
  li.append(min(cost))
for i in range(T):
  print(li[i])

Submission status: Wrong Answer

Solution code:
T=int(input())

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):
                    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:
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+(5-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():
            if j==0:
                continue
            t=D*j+n
            if t<a:
                a=t
        print(a)
    else:
        print(D)

Submission status: Wrong Answer

Solution code:
t = int(input())

for i in range(t):
  n_target, a, b, c, d = map(int, input().split())
  nc_list_new = [[1, d]]
  coin_min = 10**20
  while(1):
    nc_list = nc_list_new
    if len(nc_list) == 0:
      break
    nc_list_new = []
    for j, nc in enumerate(nc_list):
      if nc[1] >= coin_min:
        continue
      else:
        nc_list_now = [[nc[0]*2, nc[1]+a], [nc[0]*3, nc[1]+b], [nc[0]*5, nc[1]+c], [nc[0]+1, nc[1]+d], [nc[0]-1, nc[1]+d]]
        finish_list = [x for x in nc_list_now if x[0] == n_target]
        if len(finish_list) != 0:
          finish_coin_min = min([x[1] for x in finish_list])
          coin_min = min([coin_min, finish_coin_min])
          nc_list_now = [x for x in nc_list_now if x not in finish_list]
        nc_list_now = [x for x in nc_list_now if x[0] > 0]
        nc_list_now = [x for x in nc_list_now if x[1] < coin_min]
        nc_list_new.extend(nc_list_now)

print(coin_min)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
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():
            if j==0:
                continue
            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+20
  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:
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]
            # print(N)
        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)
        ans.append(col(N+2)+D*2)
        ans.append(col(N+3)+D*3)
        ans.append(col(N+4)+D*4)
        ans.append(col(N+5)+D*5)
        ans.append(col(N+6)+D*6)

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

Submission status: Wrong Answer

Solution code:
a=int(input())
print(a*a)

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:
print("Hello World")

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:
            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:
            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:
print("Hello World!")