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 = int(input())    
for _ in range(t):
    n,a,b,c,d = map(int, input().split()) 
    s = [0 for i in range(n+2)]
    s[1] = d
    s[2] = min(2*d,a+d)
    s[3] = min(3*d, b+d, a+2*d)
    s[4] = min(4*d,2*a+d,a+2*d,b+2*d, c+2*d)
    s[5] = min(5*d,a+3*d, c+2*d, 2*a+2*d,b+3*d, a+b+2*d)
    for i in range(6,n+2):
      temp = [s[i-1]+d]
      if i%2 == 0:
        temp.append(s[i//2]+a)
      if i%3 == 0:
        temp.append(s[i//3]+b)
      if i%5 == 0:
        temp.append(s[i//5]+c) 
      if (i+1)%2 == 0:
        temp.append(s[(i+1)//2]+a+d)
      if (i+1)%3 == 0:
        temp.append(s[(i+1)//3]+b+d)
      if (i+1)%5 == 0:
        temp.append(s[(i+1)//5]+c+d) 
      if (i-1)%2 == 0:
        temp.append(s[(i-1)//2]+a+d)
      if (i-1)%3 == 0:
        temp.append(s[(i-1)//3]+b+d)
      if (i-1)%5 == 0:
        temp.append(s[(i-1)//5]+c+d)       
      if (i+2)%5 == 0:
        temp.append(s[(i+2)//5]+c+2*d)      
      if (i-2)%5 == 0:
        temp.append(s[(i-2)//5]+c+d*d) 
      s[i] = min(temp)
    
    print(s[n])

Submission status: Runtime Error

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

import numpy as np
def func(N , A, B, C, D):
    lis1 =prime_factorize(N)
    lis1 = [str(n) for n in lis1]
    l1 = [A if i =="2" else i for i in lis1]
    l1= [B if i =="3" else i for i in l1]
    l1 = [C if i =="5" else i for i in l1]
    l1 = max (sum(l)+D, D*sum(l))

    lis2 = prime_factorize(N-1)
    lis2 = [str(n) for n in lis2]
    l2 = [A if i =="2" else i for i in lis2]
    l2 = [B if i =="3" else i for i in l2]
    l2 = [C if i =="5" else i for i in l2]
    l2 = min (sum(l2)+D*2, D*sum(l2))

    lis3 = prime_factorize(N+1)
    lis3 = [str(n) for n in lis3]
    l3 = [A if i =="2" else i for i in lis3]
    l3 = [B if i =="3" else i for i in l3]
    l3 = [C if i =="5" else i for i in l3]
    l3 = min (sum(l3)+D*2, D*sum(l3))
    print(min(l1,l2,l3))
    
for i in range(1, T+1):
    N, A, B, C, D = map(int, input().split())
    func(N, A, B, C, D)

Submission status: Runtime Error

Solution code:
N = int(input()
A,B,C,D = map(int,input().split)

print(N)

Submission status: Runtime Error

Solution code:
def main():
    T = int(input())
    case = [list(map(int, input().split())) for i in range(T)]
    for N, A, B, C, D in case:
        cost_table = Cost_Table({N: 0})
        will_be_evaluated = [N]
        for n in will_be_evaluated:
            if n < 2:
                continue
            accum_cost = cost_table.get_cost(n)
            if n % 2 == 0:
                temp = n // 2
                if A < (n-temp)*D:
                    table_was_updated = cost_table.update(temp, accum_cost + A)
                else:
                    table_was_updated = cost_table.update(temp, accum_cost + (n-temp)*D)
                if table_was_updated:
                    will_be_evaluated.append(temp)
            if n % 3 == 0:
                temp = n // 3
                if B < (n-temp)*D:
                    table_was_updated = cost_table.update(temp, accum_cost + B)
                else:
                    table_was_updated = cost_table.update(temp, accum_cost + (n-temp)*D)
                if table_was_updated:
                    will_be_evaluated.append(temp)
            if n % 5 == 0:
                temp = n // 5
                if C < (n-temp)*D:
                    table_was_updated = cost_table.update(temp, accum_cost + C)
                else:
                    table_was_updated = cost_table.update(temp, accum_cost + (n-temp)*D)
                if table_was_updated:
                    will_be_evaluated.append(temp)
            # plus minus 1
            if (n % 2 != 0) or (n % 3 != 0) or (n % 5 != 0):
                table_was_updated = cost_table.update(n+1, accum_cost + D)
                if table_was_updated:
                    will_be_evaluated.append(n+1)
                table_was_updated = cost_table.update(n-1, accum_cost + D)
                if table_was_updated:
                    will_be_evaluated.append(n-1)
        print(cost_table.table[1])
main()

Submission status: Runtime Error

Solution code:
import numpy as np

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

    ans, tmp = D, 1

    while tmp != N:
        pre = [2*tmp, 3*tmp, 5*tmp, tmp+1 if tmp < N else tmp-1]
        var = np.array([2*tmp/A, 3*tmp/B, 5*tmp/C, (tmp+1)/D if tmp < N else (tmp-1)/D])
        for i in range(4):
            idx = np.argsort(var)[::-1][i]
            if abs(N-pre[i]) < abs(N-tmp): break
        tmp = pre[idx]
        ans += cost[idx]
        
    print(ans)

Submission status: Runtime Error

Solution code:
import sys

T = int(input())

def findall(n, count):
    if n == N:
        l.append(count)
        return
    if n > N:
        l.append(count+(n-N)*D)
        return
    findall(n*2, count+A)
    findall(n*3, count+B)
    findall(n*5, count+C)
    findall(n+1, count+D)

for i in range(T):
    N,A,B,C,D = map(int, input().split())
    sys.setrecursionlimit(N * 4)
    l = []
    findall(1, D)
    print(min(l))

Submission status: Runtime Error

Solution code:
import sys

T = int(input())

def findall(n, count):
    if n == N:
        l.append(count)
        return
    if n > N:
        l.append(count+(n-N)*D)
        return
    findall(n*2, count+A)
    findall(n*3, count+B)
    findall(n*5, count+C)
    findall(n+1, count+D)

for i in range(T):
    N,A,B,C,D = map(int, input().split())
    sys.setrecursionlimit(N ** 3)
    l = []
    findall(1, D)
    print(min(l))

Submission status: Runtime Error

Solution code:
import sys

T = int(input())

def findall(n, count):
    if n == N:
        l.append(count)
        return
    if n > N:
        l.append(count+(n-N)*D)
        return
    findall(n*2, count+A)
    findall(n*3, count+B)
    findall(n*5, count+C)
    findall(n+1, count+D)

for i in range(T):
    N,A,B,C,D = map(int, input().split())
    sys.setrecursionlimit(N ** 2)
    l = []
    findall(1, D)
    print(min(l))

Submission status: Runtime Error

Solution code:
a

Submission status: Runtime Error

Solution code:
import numpy as np
T = int(input())
for i in range(T):
  total = 0
  N,A,B,C,D = map(int, input().split())
  coin = [A, B, C, D]
  coin = np.array(coin)
  effect = [2, 3, 5, 1]
  effect = np.array(effect)
  efficiency = [2/A, 3/B, 5/C, 1/D]
  efficiency = np.array(efficiency)
  
  sorted_idx = np.argsort(-efficiency)
  coin = coin[sorted_idx]
  effect = effect[sorted_idx]
  efficiency = efficiency[sorted_idx]

  total = np.zeros(8)
  idx_effect = 0
  
  Q = [1]
  C = [D]
  while 1:
    for j in range(len(Q)):
      if Q[j] != N:
        q = Q.pop(j)
        c = C.pop(j)
        break
    for j in range(4):
      if (j != 3 and N > q*effect[j]) or (j == 3 and N > q+effect[j]):
        if j == 3:
          Q.append(q+effect[j])
        else:
          Q.append(q*effect[j])
        C.append(c+coin[j])
      elif N < q*effect[j] and j != 3:
        Q.append(N)
        C.append(c+coin[j]+(q*effect[j]-N)*D)
      elif (j != 3 and N == q*effect[j]) or (j == 3 and N == q+effect[j]):
        if j == 3:
          Q.append(q+effect[j])
        else:
          Q.append(q*effect[j])
        C.append(c+coin[j])
    #print(Q)
    if max(Q) == N and min(Q) == N:
      break
  print(min(C))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5)
T = int(input())

def findall(n, count):
    if n == N:
        l.append(count)
        return
    if n > N:
        l.append(count+(n-N)*D)
        return
    findall(n*2, count+A)
    findall(n*3, count+B)
    findall(n*5, count+C)
    findall(n+1, count+D)

for i in range(T):
    N,A,B,C,D = map(int, input().split())
    l = []
    findall(1, D)
    print(min(l))

Submission status: Runtime Error

Solution code:
import math
#試し割法
def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
        return False
    else:
        factor.append(n)
        return factor

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

t  = int(input())
ans = []

for _ in range(t):
    k = 0
    coins = 0
    n,a,b,c,d=map(int,input().split())
    if n == 1:
        coins = d
        k += 1 
    else:
        coins = d
        k+=1
        if is_prime(n):
            L,R=trial_division(n+1),trial_division(n-1)
            LL=a*L.count(2)+b*L.count(3)+c*L.count(5)+coins+coins
            RR=a*R.count(2)+b*R.count(3)+c*R.count(5)+coins+coins
            coins=min(LL,RR)
        else:
            S = trial_division(n)
            coins=a*S.count(2)+b*S.count(3)+c*S.count(5)+coins+coins
    ans.append(coins)
for ANS in ans:
    print(ANS)

Submission status: Runtime Error

Solution code:
t = int(input())
s = [list(map(int,input().split())) for _ in range(t)]
def baka(n,N,r):
    global res
    if n == N:
        res = min(res,r)
        return
    if n < 0:
        return
    if res != 10**20 and res < r:
        return
    pat = [-1,1,2,3,5]
    n_beta,near,tag = [],[],[]
    for i in pat:
        if abs(i)==1:
            n_beta.append(n+i)
            near.append(abs(N-(n+i)))
        else:
            n_beta.append(n*i)
            near.append(abs(N-(n*i)))

    for i in range(len(n_beta)):
        if min(near) == near[i]:
            tag.append(i)
    for i in range(len(pat)):
        for j in tag:
            if abs(pat[i])==1:
                if i == j:
                    baka(n+pat[i],n_beta[j],r+D)
                else:
                    baka(n+pat[i],N,r+D)
            elif pat[i]==2:
                if i == j:
                    baka(n*pat[i],n_beta[j],r+A)
                else:
                    baka(n*pat[i],N,r+A)
            elif pat[i]==3:
                if i == j:
                    baka(n*pat[i],n_beta[j],r+B)
                else:
                    baka(n*pat[i],N,r+B)
            elif pat[i]==5:
                if i == j:
                    baka(n*pat[i],n_beta[j],r+C)
                else:
                    baka(n*pat[i],N,r+C)

for i in s:
    res = 10**20
    N,A,B,C,D = i[0],i[1],i[2],i[3],i[4]
    baka(1,N,D)
    print(res)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 10)
T = int(input())

def findall(n, count):
    if n == N:
        l.append(count)
        return
    if n > N:
        l.append(count+(n-N)*D)
        return
    findall(n*2, count+A)
    findall(n*3, count+B)
    findall(n*5, count+C)
    findall(n+1, count+D)

for i in range(T):
    N,A,B,C,D = map(int, input().split())
    l = []
    findall(1, D)
    print(min(l))

Submission status: Runtime Error

Solution code:
import math
#試し割法
def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    #リストが空ならそれは素数
    if not factor:
        return False
    else:
        factor.append(n)
        return factor

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

t  = int(input())
ans = []

for _ in range(t):
    k = 0
    coins = 0
    n,a,b,c,d=map(int,input().split())
    if n == 1:
        coins = d
        k += 1 
    else:
        coins = d
        k+=1
        if is_prime(n):
            L,R=trial_division(n+1),trial_division(n-1)
            LL=a*L.count(2)+b*L.count(3)+c*L.count(5)+coins+coins
            RR=a*R.count(2)+b*R.count(3)+c*R.count(5)+coins+coins
            coins=min(LL,RR)
        else:
            S = trial_division(n)
            coins=a*S.count(2)+b*S.count(3)+c*S.count(5)+coins+coins
    ans.append(coins)
for ANS in ans:
    print(ANS)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    P = [int(i)-1 for i in input().split(' ')]
    seat = [[1 for j in range(N)] for i in range(N)]
    score = 0
    for i in range(len(P)):
        if P[i]//N%N== 0 or P[i]%N%N == 0:
            seat[P[i]//N][(P[i])%N] = 0
            continue
        left = sum(seat[P[i]//N][:P[i]%N])
        if left == 0:
            seat[P[i]//N][(P[i])%N] = 0
            continue
        right = sum(seat[P[i]//N][P[i]%N:])-1 if sum(seat[P[i]//N][P[i]%N:])-1>=0 else 0
        if right == 0:
            seat[P[i]//N][(P[i])%N] = 0
            continue
        top = 0
        j = P[i]//N-1
        while True:
            if j >= 0:
                top += seat[j][P[i]%N]
            else:
                break
            j -= 1
        if top == 0:
            seat[P[i]//N][(P[i])%N] = 0
            continue
        bottom = 0
        j = P[i]//N+1
        while True:
            if j < N:
                bottom += seat[j][P[i]%N]
            else:
                break
            j += 1
        if bottom == 0:
            seat[P[i]//N][(P[i])%N] = 0
            continue
        score_direction = [left, right, top, bottom]
        score += min(score_direction)
        seat[P[i]//N][(P[i])%N] = 0
    print(score)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from math import log, floor
from sys import setrecursionlimit
setrecursionlimit(10**7)
t = int(input())
flag = False
mn = int()

def solve(n,a,b,c,d):
    global flag
    global mn

    if n <= 0:
        return
    if (n-c) % 5 == 0:
        mn = (n-c) // 5 ** floor(log(n-c, 5))
        return
    if (n-b) % 3 == 0:
        mn = (n-b) // 3 ** floor(log(n-b, 3))
        return
    if (n-a) % 2 == 0:
        mn = (n-a) // 2 ** floor(log(n-a, 2))
        return
    solve(n-d-1, a, b, c, d)
    solve(n-d+1, a, b, c, d)


for i in range(t):
    mn = 10 ** 18
    t0, t1, t2, t3, t4 = [int(i) for i in input().split()]
    solve(t0,t1,t2,t3,t4)
    print(mn)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 20)
T = int(input())

def findall(n, count):
    if n == N:
        l.append(count)
        return
    if n > N:
        l.append(count+(n-N)*D)
        return
    findall(n*2, count+A)
    findall(n*3, count+B)
    findall(n*5, count+C)
    findall(n+1, count+D)

for i in range(T):
    N,A,B,C,D = map(int, input().split())
    l = []
    findall(1, D)
    print(min(l))

Submission status: Runtime Error

Solution code:
def a_job(n_plus, a, c_plus):
  c_plus += a
  n_plus *= 2
def b_job(n_plus, b, c_plus):
  c_plus += b
  n_plus *= 3
def c_job(n_plus, c, c_plus):
  c_plus += c
  n_plus *= 5
def d_job(n, n_plus, d, c_plus):
  c_plus += d
  if n_plus < n:
    n_plus += 1
  elif n_plus > n:
    n_plus -= 1
  else:
    pass
def nc(n, a, b, c, d):
  n_plus = 0
  c_plus = 0
  d_job(n, n_plus, d, c_plus)
  while true:
    if n_plus * 5 <= n:
      c_job(n_plus, a, c_plus)
    elif n_plus * 3 <= n:
      b_job(n_plus, a, c_plus)
    elif n_plus * 2 <= n:
      a_job(n_plus, a, c_plus)
    else:
      d_job(n, n_plus, a, c_plus)
    if n_plus == n:
      put(c_plus)
      break
    elif n_plus > n:
      c_plus = 0
      n_plus = 0
    else:
      pass

t = input('type [T]: ')
for i in range(0, t):
  j = input('type as you want: ')
  n = item.split(' ')[0]
  a = item.split(' ')[1]
  b = item.split(' ')[2]
  c = item.split(' ')[3]
  d = item.split(' ')[4]
  nc(n, a, b, c, d)

Submission status: Runtime Error

Solution code:
T = int(intput())

def solve(N, A, B, C, D):
  def pay(x, coin=0):
    if x == 0:
      return 0
    out1 = x/2 if x%2==0 else float('inf')
    out2 = x/3 if x%3==0 else float('inf')
    out3 = x/5 if x%5==0 else float('inf')
    out4 = x+1 if x%8==0 else float('inf')
    out5 = x-1 if x%8==0 else float('inf')
    return min(pay(out1, coin+A), pay(out2, coin+B), pay(out3, coin+C), pay(out4, coin+D), pay(out5, coin+D))
  return pay(N)

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

Submission status: Runtime Error

Solution code:
T = int(input())
arr = []
list = [[] for __ in range(T)]
for k in range(T):
  arr = input().split()
  list[k] = arr
l = 0
count = 0
x = 0
coin = [0]
while l == int(T):
    while count == list[l][0]:
        for __ in range(list[l][4]):
            x += 1
            count += int(list[l][4])
        for __ in range(arr[1]):
            x *= 2
            count += int(list[l][1])
        for __ in range(list[l][2]):
            x *= 3
            count += int(list[l][2])
        for __ in range(list[l][3]):
            x *= 5
            count += int(list[l][3])

        coin.append(count)
        l += 1
        
for i in range(T):
  print(coin[i])

Submission status: Runtime Error

Solution code:
mask_features = multiply([attn_layer, bn_features])
gap_features = GlobalAveragePooling2D()(mask_features)
gap_mask = GlobalAveragePooling2D()(attn_layer)

Submission status: Runtime Error

Solution code:
ts

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    P = [int(i)-1 for i in input().split(' ')]
    seat = [[1 for j in range(N)] for i in range(N)]
    score = 0
    for i in range(len(P)):
        left = sum(seat[P[i]//N][:P[i]%N])
        right = sum(seat[P[i]//N][P[i]%N:])-1 if sum(seat[P[i]//N][P[i]%N:])-1>=0 else 0
        top = 0
        j = P[i]//N-1
        while True:
            if j >= 0:
                top += seat[j][P[i]%N]
            else:
                break
            j -= 1
        bottom = 0
        j = P[i]//N+1
        while True:
            if j < N:
                bottom += seat[j][P[i]%N]
            else:
                break
            j += 1
        score_direction = [left, right, top, bottom]
        score += min(score_direction)
        seat[P[i]//N][(P[i])%N] = 0
    print(score)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
aa

Submission status: Runtime Error

Solution code:
import re
from collections import defaultdict
import sys
#from Levenshtein import distance as ldist

def tableexp(n):
    res=[0]*(n+1)
    res[2]=1
    res2=[0]*(n+1)
    res2[2]=1
    res3=[0]*(n+1)
    res3[2]=0
    for i in range(3,n+1):
        js=sorted(list(range(1,i)),key = lambda j:j/i*res[j]+(i-j)/i*res[i-j])
        j=js[0]
        res[i]=1+j/i*res[j]+(i-j)/i*res[i-j]
        jj=i//2
        res2[i]=1+jj/i*res2[jj]+(i-jj)/i*res2[i-jj]
        js=sorted(list(range(1,i)),key = lambda j:j*j/i/i*res[j]+(i-j)/i*res[i-j])
        print(i,j,jj,res[i],res2[i])
    return res


    

def placer(lettre,n,poss, printme=True):
    if n==0:
        return [],0
    if n==len(poss):
         return poss,0
    else:
        totry="".join([lettre if i in poss[:len(poss)//2] and i not in realpresence else fs[i] for i in range(lenstr)])
        testres=lenstr-minpresence-wheretotest(totry)
        a=placer(lettre,testres,poss[:len(poss)//2],printme=False)
        b=placer(lettre,n-testres,poss[len(poss)//2:],printme=False)
        if printme:
            print(lettre,a[0]+b[0],a[1]+b[1]+1)
        return (a[0]+b[0],a[1]+b[1]+1)


lettres="abcdefghijklmnopqrstuvwxyz"
lettres+=lettres.upper()
lettres+="1234567890"


def testatc(s):
    print("?", s)
    sys.stdout.flush()
    ans=int(input())
    return ans

def maxrepresentee(s):
    d=defaultdict(int)
    for k in s:
        d[k]+=1
    return(max(d.values()))

def reps(s):
    d=defaultdict(int)
    for k in s:
        d[k]+=1
    return(d.values())

def testlocal(s):
    print(s,ldist(s,sb))
    return ldist(s,sb)

nbcall=0
def wheretotest(s):
    global nbcall
    nbcall+=1
    return testatc(s)

nb_methodes=4

dd=defaultdict(int)
nb_simus=1


drbest=defaultdict(int)



for sb in ["AtCod3rIsGreat"]:
    lestrdef=False
    lenstr=128
    minpresence=lenstr
    moinspresente=None
    #methode 4 : on place chaque lettre
    dp={} #determiner chaque lettre
    tr=0
    for i in lettres:
        nbi=lenstr-wheretotest(i*lenstr)
        #print(i,nbi)
        if nbi and not lestrdef:
            lenstr=wheretotest(i*nbi)+nbi
            lestrdef=True
       # print("testing",i*lenstr)
        tr+=1
        #if nbi:
        #    print(i, "y est ",nbi)
        if nbi:
            dp[i]=nbi
        if nbi<minpresence:
            minpresence=nbi
            moinspresente=i
        if sum(dp.values())==lenstr: #2.4 soumissions en moyenne de gain
            break
        if tr==len(lettres)-1: #on connait le dernier après les 61 faits. ca devrait rapporter 0.4 soumissions en moyenne.
            dp[lettres[-1]]=lenstr-sum(dp.values())
            """if lenstr-sum(dp.values()):
                print(lettres[-1], "y est ",nbi)"""
            break
    
    #determiner une fakestring
    realpresence=set()
    fs=moinspresente*lenstr
    if minpresence:
        fs=moinspresente*lenstr
        bfs=lenstr-dp[moinspresente]
        for i in range(lenstr):
            ffs="".join([fs[k] if k!=i else ("b" if moinspresente!="b" else "c") for k in range(lenstr)])
            ans=wheretotest(ffs)
            if ans>bfs:
                realpresence.add(i)
    assert(minpresence==len(realpresence))
    ss=[None]*lenstr
    for i in realpresence:
        ss[i]=moinspresente
    poss=list(range(lenstr))
    keysleft=len(dp)- (1 if minpresence else 0)
    keyss=sorted(dp.keys(), key=lambda x:-dp[x])
    for ii in range(len(keyss)):
        i=keyss[ii]
        if i!=moinspresente:
            if keysleft!=2 or dp[keyss[ii]]+dp[keyss[ii+1]]!=2:
                p=placer(i,dp[i],poss,False)
                tr+=p[1]
                for k in p[0]:
                    ss[k]=i
                    poss=[j for j in poss if j!=k]
                if keysleft==1:
                    s="".join(ss)
            else:
                ss1=ss[:]
                ss2=ss[:]
                poss=[keyss[ii],keyss[ii+1]]
                p1,p2=[k for k in range(lenstr) if ss[k] is None]
                ss1[p1]=i
                ss2[p2]=i
                ss1[p2]=keyss[ii+1]
                ss2[p1]=keyss[ii+1]
                if wheretotest("".join(ss1)):
                    tr+=1
                    assert(wheretotest("".join(ss2)))==0
                    s="".join(ss2)
                else:
                    s="".join(ss1)
                break
            keysleft-=1
    print("!",s)
    sys.stdout.flush()

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
t = int(input())
ans = []
for i in range(t):
    n,a,b,c,d=map(int, input().split())
    INF = 10**18
    cost = [INF]*(n+1)
    cost[1] = d
    que = [(1, d)]

    while que:
        val, cos = heappop(que)
        if cost[val] < cos and cost[n] < cos:
            continue
        if n < val:
            k = val - n
            cost[n] = min(cost[n], cos +(d*k))
        if val * 2 < n+1:
            if cost[val*2] > cos+a:
                cost[val*2] = min(cost[val*2], cos+a)
                heappush(que, (val * 2, cost[val*2]))
        if val * 3 < n+1:
            if cost[val*3] > cos+b:
                cost[val*3] = min(cost[val*3], cos+b)
                heappush(que, (val * 3, cost[val*3]))
        if val * 5 < n+1:
            if cost[val*5] > cos+c:
                cost[val*5] = min(cost[val*5], cos+c)
                heappush(que, (val * 5, cost[val*5]))
        if val + 1 < n+1:
            if cost[val+1] > cos+d:
                cost[val+1] = min(cost[val+1], cos+d)
                heappush(que, (val + 1, cost[val+1]))
    ans.append(cost[n])

for s in ans:
   print(s)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    P = [int(i)-1 for i in input().split(' ')]
    seat = [[1 for j in range(N)] for i in range(N)]
    score = 0
    for i in range(len(P)):
        left = sum(seat[P[i]//N][:P[i]%N])
        right = sum(seat[P[i]//N][P[i]%N:])-1 if sum(seat[P[i]//N][P[i]%N:])-1>=0 else 0
        top = 0
        j = P[i]//N-1
        while True:
            if j >= 0:
                top += seat[j][P[i]%N]
            else:
                break
            j -= 1
        bottom = 0
        j = P[i]//N+1
        while True:
            if j < N:
                bottom += seat[j][P[i]%N]
            else:
                break
            j += 1
        score_direction = [left, right, top, bottom]
        score += min(score_direction)
        seat[P[i]//N][(P[i])%N] = 0
    print(score)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
t = int(input())
for _ in range(t):
  N, A, B, C, D  = map(int, input().split())
  dp = [1000000007] * 100000
  dp[0] = 0
  dp[1] = D

  next = 1
  for i in range(1, 21):
    next += 1
    dp[next] = dp[next-1] + D

  next2 = 1
  next3 = 1
  next5 = 1
  for i in range(1, 100):
    next = i
    next2 = i*2
    next3 = i*3
    next5 = i*5

    if next2 > 1000000000000:
      break
    dp[next2] = min(dp[next]+A, dp[next2])
    dp[next2-1] = min(dp[next2]+D, dp[next2-1])
    dp[next2+1] = min(dp[next2]+D, dp[next2+1])

    if next3 > 1000000000000:
      break
    dp[next3] = min(dp[next]+B, dp[next3])
    dp[next3-1] = min(dp[next3]+D, dp[next3-1])
    dp[next3+1] = min(dp[next3]+D, dp[next3+1])

    if next5 > 1000000000000:
      break
    dp[next5] = min(dp[next]+C, dp[next5])
    dp[next5-1] = min(dp[next5]+D, dp[next5-1])
    dp[next5+1] = min(dp[next5]+D, dp[next5+1])

    dp[next] = min(dp[next-1]+D, dp[next])
  print(dp[N])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
t = int(input())
for _ in range(t):
  N, A, B, C, D  = map(int, input().split())
  dp = [1000000007] * 100000000
  dp[0] = 0
  dp[1] = D

  next = 1
  for i in range(1, 21):
    next += 1
    dp[next] = dp[next-1] + D

  next2 = 1
  next3 = 1
  next5 = 1
  for i in range(1, 100):
    next = i
    next2 = i*2
    next3 = i*3
    next5 = i*5

    if next2 > 1000000000000:
      break
    dp[next2] = min(dp[next]+A, dp[next2])
    dp[next2-1] = min(dp[next2]+D, dp[next2-1])
    dp[next2+1] = min(dp[next2]+D, dp[next2+1])

    if next3 > 1000000000000:
      break
    dp[next3] = min(dp[next]+B, dp[next3])
    dp[next3-1] = min(dp[next3]+D, dp[next3-1])
    dp[next3+1] = min(dp[next3]+D, dp[next3+1])

    if next5 > 1000000000000:
      break
    dp[next5] = min(dp[next]+C, dp[next5])
    dp[next5-1] = min(dp[next5]+D, dp[next5-1])
    dp[next5+1] = min(dp[next5]+D, dp[next5+1])

    dp[next] = min(dp[next-1]+D, dp[next])
  print(dp[N])

Submission status: Runtime Error

Solution code:
hello free rating plz

Submission status: Runtime Error

Solution code:



def min_coins(arr):

    N = arr[0]
    A = arr[1]
    B = arr[2]
    C = arr[3]
    D = arr[4]

    dp = [float("inf")] * (N + 1)
    dp[1] = D

    for i in range(2, N+1):

        op1 = float("inf")
        op2 = float("inf")
        op3 = float("inf")
        op4 = float("inf")
        op5 = float("inf")
        op6 = float("inf")


        if i % 2 == 0:
            op1 = dp[i//2] + A

        if i % 3 == 0:
            op2 = dp[i//3] + B

        if i % 5 == 0:
            op3 = dp[i//5] + C

        if (i + 1)% 2 == 0:
            op4 = dp[(i + 1)//2] + D + A

        if (i + 1)% 3 == 0:
            op5 = dp[(i + 1)//3] + D + B

        if (i + 1)% 5 == 0:
            op6 = dp[(i + 1)//5] + D + C

        dp[i] = min(op1, op2, op3, dp[i - 1] + D, dp[i], op4, op5, op6)



    # print(dp)
    return dp[N]


t = int(input())


for _ in range(t):
    arr = list(map(int, input().split()))
    print(min_coins(arr))