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: Runtime Error

Solution code:
'''
T = 5
N = 11
A = 1#*2
B = 2#*3
C = 4#*5
D = 8#+1
'''
T = int(input())
S = [input() for _ in range(T)]


for _ in range(T):
	A, B, C, D = map(int, input().split())
	#[A, B, C, D]
	memo = {1: D}
	for i in range(2, N+2):
		cost = memo[i-1] + D
		if not i%2:
			cost = min(cost, memo[i/2] + A)
		if not i%3:
			cost = min(cost, memo[i/3] + B)
		if not i%5:
			cost = min(cost, memo[i/5] + C)
		memo[i] = cost
		memo[i-1] = min(memo[i-1], cost + D)
		#print(str(i)+' >>> '+str(cost))
	print(memo[N])

Submission status: Runtime Error

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
    count1+=1
  return count1

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: Runtime Error

Solution code:
# Inputing values


t=int(input())

# for loop 

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

# new vars


l=[int(input()) for _ in range(n)]


# defineing new 


def dfs(count,a,b,c):
  
  # if-else looping 
    if count==n:
        if min(a,b,c)>0:
            return abs(a-A)+abs(b-B)+abs(c-C)-30
        else:
            return 10**9+1
          
          # new vars
          
    x = dfs(count+1, a, b, c)
    y = dfs(count+1, a+l[count], b, c)+10
    z = dfs(count+1, a, b+l[count], c)+10
    w = dfs(count+1, a, b, c+l[count])+10
    return min(x,y,z,w)

# printing answer 

print(dfs(0,0,0,0))

Submission status: Runtime Error

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: Runtime Error

Solution code:
import numpy as np
min_coin = 0
def search(N, n, c, A, B, C, D):
    global min_coin
    if c > min_coin:
        return N*D
    if n > N*2:
        return N*D
    if n <= 0:
        return N*D
    if c > N*D:
        return N*D
    if N == n:
        if c < min_coin:
            min_coin = c
        return c
    AA = search(N, n*2, c+A, A, B, C, D)
    BB = search(N, n*3, c+B, A, B, C, D)
    CC = search(N, n*5, c+C, A, B, C, D)
    DD = search(N, n+1, c+D, A, B, C, D)
    DDD = search(N, n-1, c+D, A, B, C, D)
    return min(AA, BB, CC, DD, DDD)

T = int(input())
for _ in range(T):
    N, A, B, C, D = np.array(list(map(int, input().split())))
    min_coin = N*D
    print(search(N, 1, D, A, B, C, D))

Submission status: Runtime Error

Solution code:
t = int(input())
for i in range(t):
    n,a,b,c,d = map(int,input().split())
    INF = float("inf")
    dp = [INF]*(n+10)
    #print(dp)
    dp[1]=d
    for i in range(1,n+9):
        if i*2<=n+9:
            dp[i*2] = min(dp[i*2],dp[i]+a)
        if i*3 <= n+9:
            dp[i*3] = min(dp[i*3],dp[i]+b)
        if i*5 <= n+9:
            dp[i*5] = min(dp[i*5],dp[i]+c)
        if i+1 <= n:
            dp[i+1] = min(dp[i+1],dp[i]+d)
        dp[i-1] = min(dp[i-1], dp[i]+d)
    #print(dp)
    print(dp[n])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
t = int(input())


class Calculator:
    n, a, b, c, d = 0, 0, 0, 0, 0
    solved = False

    def __init__(self, n, a, b, c, d):
        self.n, self.a, self.b, self.c, self.d = n, a, b, c, d

    def calc(self):
        # 最初は1増やす
        cost = d
        has = 1
        res = self.calcCostRecurse(has, cost)
        print(res)


    def calcCostRecurse(self, has, curCost):
        if n < has:
            moreCost = (has - n) * d  # 減らす
            return curCost + moreCost

        if n == has:
            return curCost
        
        costCaseA = self.calcCostRecurse(has * 2, curCost + a)

        costCaseB = self.calcCostRecurse(has * 3, curCost + b)

        costCaseC = self.calcCostRecurse(has * 5, curCost + c)

        costCaseD = self.calcCostRecurse(has + 1, curCost + d)

        return min([costCaseA, costCaseB, costCaseC, costCaseD])

    #def calcCostRecurse2(self, has, curCost):
        #stack = []
        #stack.append((has, curCost))

        #while True:
        
for i in range(0, t):
    line = input().split(" ")
    n, a, b, c, d = int(line[0]), int(line[1]), int(line[2]), int(line[3]), int(line[4])
    calc = Calculator(n, a, b, c, d)
    calc.calc()

Submission status: Runtime Error

Solution code:
"""
あなたは 0という数を持っており、これを 
N に変えようとしています。
あなたが持っている数は、以下の操作により、定まった枚数のコインを支払うことで変化させることができます。
A 枚のコインを支払い、持っている数を 2 倍する。
B 枚のコインを支払い、持っている数を 3 倍する。
C 枚のコインを支払い、持っている数を 5 倍する。
D 枚のコインを支払い、持っている数を 1 増やす、または 1 減らす。
これらの操作は、任意の順に何度でも行うことができます。

持っている数を N
 とするには、最小で何枚のコインが必要でしょうか。
T
 個のテストケースについて答えてください。
"""

t = int(input())
case = [map(int, input().split()) for i inrange(t)]

for c in t:
    num = 1
    coin = c[4]
    coef = [2 3 5 0]
    bias = [0 0 0 1]
    n, c = c[0], c[1:]
    while True:
        break
        cost = [c[i]/(coef[i]*num) for i in range(4)]
        if 5*num > n:

        elif 3*num > n:

        elif 2*num > n:

        else:
            m = cost.argmin()
            num = coef[m]*num + bias[m]
            coin += c[m]
        if(num == n):
            print(coin, end="\n")
            break
    print(20)

Submission status: Runtime Error

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


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
    a = even(x)
    return a+d


def five(n):

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


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


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


a = int(input())
n, a, b, c, d = map(int, input().split())
if n % 2 == 0:
    even(n)
else:
    odd(n)

Submission status: Runtime Error

Solution code:
import queue

t = int(input())

for i in range(t):
  n,a,b,c,d = map(int, input().split())
  cost = [a,b,c,d,d]
  dist = [-1]*(n+1)*6
  q = queue.Queue()
  q.put(0)
  dist[0] = 0

  while not q.empty():
    target = q.get()
    distance = dist[target]

    candidate = [target * 2, target * 3, target * 5, target + 1, target - 1]

    for ci in range(len(cost)):
      if candidate[ci] < 0 or candidate[ci] > n * 2: continue

      tmp = distance + cost[ci]
      if dist[candidate[ci]] < 0 or dist[candidate[ci]] > tmp:
        dist[candidate[ci]] = tmp
        q.put(candidate[ci])

  print(dist[n])

Submission status: Runtime Error

Solution code:
T = int(input())
i = 0
while i < T:
N,A,B,C,D=map(int, input().split())
i =+ 1

Submission status: Runtime Error

Solution code:
t = int( input() )
nabcd = []
for _ in range( t ):
    n, a, b, c, d = map( int, input().split() )
    nabcd.append( [ n, a, b, c, d ] )

def adj( k, a_i, b_i, c_i, d_i ):
    if k > 0:
        return [ ( a_i, 2*k ), ( b_i, 3*k ), ( c_i, 5*k ), ( d_i, k+1 ), ( d_i, k-1 ) ]
    elif k == 0:
        return [ ( d_i, k+1 ) ]
    else:
        return []

import heapq
def search( goal, a_i, b_i, c_i, d_i ):
    INF = 10 ** 10
    VISITED = 1
    NOT_VISITED = 0
    NODE = 2 * goal # 諸
    cost = [ INF ] * ( NODE+1 )
    cost[ 0 ] = 0
    visit = [ NOT_VISITED ] * ( NODE+1 )
    queue = [ ( cost[ 0 ], 0 ) ]
    while visit[ goal ] == NOT_VISITED:
        c, v = heapq.heappop( queue )
        visit[ v ] = VISITED
        for cost_vu, u in adj( v, a_i, b_i, c_i, d_i ):
            if u > NODE:
                continue
            if visit[ u ] == VISITED:
                continue
            if cost[u] > cost[v] + cost_vu:
                cost[u] = cost[v] + cost_vu
                heapq.heappush( queue, ( cost[u], u ) )

    print( cost[ goal ] )

for i in range( t ):
    search( nabcd[i][0], nabcd[i][1], nabcd[i][2], nabcd[i][3], nabcd[i][4] )

Submission status: Runtime Error

Solution code:
T = input()
for _ in range(T):
    N, A, B, C, D = map(int, input().split())
    x = 1
    a = x * 2
    b = x * 3
    c = x * 5
    dp = x + 1
    dm = x - 1

Submission status: Runtime Error

Solution code:
a = int(input())
n, a, b, c, d = map(int, input().split())
if n % 2 == 0:
  even(n)
else:
  odd(n)

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
  a = guu(x)
  return a+d
 
def five(n):
  
  count1 = 0
  while(n % 5 != 0):
      count1 += 1
  return count1


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


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

Submission status: Runtime Error

Solution code:
解けるわけなくて草

Submission status: Runtime Error

Solution code:
a = int(input())
n, a, b, c, d = map(int, input().split())
if n % 2 == 0:
    guu(n)
else:
    kisu(n)


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


def kisu(n):
    x = n-1
    a = guu(x)
    return a+d


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


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


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

Submission status: Runtime Error

Solution code:
 print(1)

Submission status: Runtime Error

Solution code:
print(a)

Submission status: Runtime Error

Solution code:
import itertools
n = int(input())
p = list(itertools.permutations(range(1, n+1), n))
a = [0,0]
for i in range(2):
	a[i] = p.index(tuple(map(int,input().split())))
print(abs(a[0]-a[1]))

Submission status: Runtime Error

Solution code:
import numpy as np
min_coin = 0
def search(N, n, c, A, B, C, D):
    global min_coin
    if c > min_coin:
        return N*D
    if n > N*2:
        return N*D
    if n <= 0:
        return N*D
    if c > N*D:
        return N*D
    if N == n:
        min_coin = c
        return c
    AA = search(N, n*2, c+A, A, B, C, D)
    BB = search(N, n*3, c+B, A, B, C, D)
    CC = search(N, n*5, c+C, A, B, C, D)
    DD = search(N, n+1, c+D, A, B, C, D)
    DDD = search(N, n-1, c+D, A, B, C, D)
    return min(AA, BB, CC, DD, DDD)

T = int(input())
for _ in range(T):
    N, A, B, C, D = np.array(list(map(int, input().split())))
    min_coin = N*D
    print(search(N, 1, D, A, B, C, D))

Submission status: Runtime Error

Solution code:
T = int(input())

def A_siki(coin,A,N,x):
  if x>N:
     x -= 1
  else:
    x += 1
  coin += A
  return coin,x

def B_siki(coin,B,x):
  coin += B
  x = 2*x
  return coin,x

def C_siki(coin,C,x):
  coin += C
  x = 3*x
  return coin,x

def D_siki(coin,D,x):
  coin += D
  x = 5*x
  return coin,x

for i in range(T):
  N,A,B,C,D = map(int,input().split())
  x = 0
  while True:
    if (x == 0) or (x*2>N) and (x*3>N) and (x*5>N):
      coin,x = A_siki(coin,A,N,x)
    elif (x*2 < N) and (x*3 > N) and (x*5 > N):
      coin,x = B_siki(coin,B,x)
    elif (x*3 < N) and(x*5>N):
      coin,x = C_siki(coin,C,x)
    else:
      coin,x = D_siki(coin,D,x)
    if x == N:
      break
      
  print(coin)

Submission status: Runtime Error

Solution code:
T = int(input())
for i in range(T):
  N,A,B,C,D = map(int, input())
  print(N*D)

Submission status: Runtime Error

Solution code:
T=int(input())
N,A,B,C,D=int(input())

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':

	list =['nannmo ','wakarann ','denaosimasu ','.......']
    
    list = ''.join(list)
    
    print(list)

Submission status: Runtime Error

Solution code:
T=int(input())
N,A,B,C,D=map(T/2int(input()).spirit())

Submission status: Runtime Error

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

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

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
alist = list(map(int,input().split()))

town = 1
numberlist = []
count = 0
count2 = 0
for i in range(k):
    town = alist[town-1]
    if town in numberlist:
        break
    else:
        numberlist.append(town)
        count += 1
print(numberlist)
for i in numberlist:
    if i == town:
        break
    else:
        numberlist.remove(i)
        count2 += 1

k = k - count2
x = k % len(numberlist)
print(numberlist)
print(numberlist[x-1])