Problem:
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.**

Incorrect submission (verdict: Wrong Answer):





import math

def calc_cost(n, ans_dict):

    min_cost = n * d

    inc_2 = int(math.ceil(n / 2))
    if inc_2 not in ans_dict:
        ans_dict[inc_2] = calc_cost(inc_2, ans_dict)
    min_cost = min(min_cost, d * (inc_2 * 2 - n) + a + ans_dict[inc_2])

    dec_2 = int(math.floor(n / 2))
    if dec_2 not in ans_dict:
        ans_dict[dec_2] = calc_cost(dec_2, ans_dict)
    min_cost = min(min_cost, d * (- dec_2 * 2 + n) + a + ans_dict[dec_2])

    inc_3 = int(math.ceil(n / 3))
    if inc_3 not in ans_dict:
        ans_dict[inc_3] = calc_cost(inc_3, ans_dict)
    min_cost = min(min_cost, d * (inc_3 * 3 - n) + b + ans_dict[inc_3])

    dec_3 = int(math.floor(n / 3))
    if dec_3 not in ans_dict:
        ans_dict[dec_3] = calc_cost(dec_3, ans_dict)
    min_cost = min(min_cost, d * (- dec_3 * 3 + n) + b + ans_dict[dec_3])

    inc_5 = int(math.ceil(n / 5))
    if inc_5 not in ans_dict:
        ans_dict[inc_5] = calc_cost(inc_5, ans_dict)
    min_cost = min(min_cost, d * (inc_5 * 5 - n) + c + ans_dict[inc_5])

    dec_5 = int(math.floor(n / 5))
    if dec_5 not in ans_dict:
        ans_dict[dec_5] = calc_cost(dec_5, ans_dict)
    min_cost = min(min_cost, d * (- dec_5 * 5 + n) + c + ans_dict[dec_5])

    ans_dict[n] = min_cost
    return min_cost

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

    
    ans_dict = {}

    ans_dict[0] = 0
    ans_dict[1] = d  

    ans = calc_cost(n, ans_dict)
    print(ans)
    # print(ans_dict)


Fixed, accepted submission:





def calc_cost(n, ans_dict):

    min_cost = n * d

    inc_2 = (n + 2 - 1) // 2
    if inc_2 not in ans_dict:
        ans_dict[inc_2] = calc_cost(inc_2, ans_dict)
    min_cost = min(min_cost, d * (inc_2 * 2 - n) + a + ans_dict[inc_2])

    dec_2 = n // 2
    if dec_2 not in ans_dict:
        ans_dict[dec_2] = calc_cost(dec_2, ans_dict)
    min_cost = min(min_cost, d * (- dec_2 * 2 + n) + a + ans_dict[dec_2])

    inc_3 = (n + 3 - 1) // 3
    if inc_3 not in ans_dict:
        ans_dict[inc_3] = calc_cost(inc_3, ans_dict)
    min_cost = min(min_cost, d * (inc_3 * 3 - n) + b + ans_dict[inc_3])

    dec_3 = n // 3
    if dec_3 not in ans_dict:
        ans_dict[dec_3] = calc_cost(dec_3, ans_dict)
    min_cost = min(min_cost, d * (- dec_3 * 3 + n) + b + ans_dict[dec_3])

    inc_5 = (n + 5 - 1) // 5
    if inc_5 not in ans_dict:
        ans_dict[inc_5] = calc_cost(inc_5, ans_dict)
    min_cost = min(min_cost, d * (inc_5 * 5 - n) + c + ans_dict[inc_5])

    dec_5 = n // 5
    if dec_5 not in ans_dict:
        ans_dict[dec_5] = calc_cost(dec_5, ans_dict)
    min_cost = min(min_cost, d * (- dec_5 * 5 + n) + c + ans_dict[dec_5])

    ans_dict[n] = min_cost
    return min_cost

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

    
    ans_dict = {}

    ans_dict[0] = 0
    ans_dict[1] = d  

    ans = calc_cost(n, ans_dict)
    print(ans)
    # print(ans_dict)