Problem p03329 (python)

Fixed submission:
n = int(input())

dp = [0 for i in range(max(n+1, 36))]

for i in range(35):
    j = i // 9
    cand = []
    for k in range(j+1):
       _i = i
       _i -= 9*k
       l = _i // 6
       for m in range(l+1):
           __i = _i
           __i -= 6*m
           cand.append(k+m+__i)
    dp[i] = min(cand)
nine_list = [pow(9, i) for i in range(1, 6)]
six_list = [pow(6, i) for i in range(1, 7)]
for i in range(35, n+1):
    max_nine = nine_list[len(nine_list) - 1]
    max_six = six_list[len(six_list) - 1]
    for j in range(len(nine_list)):
        if nine_list[j] > i:
            max_nine = nine_list[j-1]
            break
    for j in range(len(six_list)):
        if six_list[j] > i:
            max_six = six_list[j-1]
            break
    dp[i] = min(dp[i-max_nine]+1, dp[i-max_six]+1)

print(dp[n])

Buggy submission (verdict: Runtime Error):
n = int(input())

dp = [0 for i in range(n+1)]

for i in range(35):
    j = i // 9
    cand = []
    for k in range(j+1):
       _i = i
       _i -= 9*k
       l = _i // 6
       for m in range(l+1):
           __i = _i
           __i -= 6*m
           cand.append(k+m+__i)
    dp[i] = min(cand)
nine_list = [pow(9, i) for i in range(1, 6)]
six_list = [pow(6, i) for i in range(1, 7)]
for i in range(35, n+1):
    for j in range(len(nine_list)):
        if nine_list[j] > i:
            max_nine = nine_list[j-1]
            break
    for j in range(len(six_list)):
        if six_list[j] > i:
            max_six = six_list[j-1]
            break
    dp[i] = min(dp[i-max_nine]+1, dp[i-max_six]+1)

print(dp[n])

Buggy submission (verdict: Runtime Error):
n = int(input())

dp = [0 for i in range(n+1)]

for i in range(35):
    j = i // 9
    cand = []
    for k in range(j+1):
       _i = i
       _i -= 9*k
       l = _i // 6
       for m in range(l+1):
           __i = _i
           __i -= 6*m
           cand.append(k+m+__i)
    dp[i] = min(cand)
nine_list = [pow(9, i) for i in range(1, 6)]
six_list = [pow(6, i) for i in range(1, 7)]
for i in range(36, n+1):
    for j in range(len(nine_list)):
        if nine_list[j] > i:
            max_nine = nine_list[j-1]
            break
    for j in range(len(six_list)):
        if six_list[j] > i:
            max_six = six_list[j-1]
            break
    dp[i] = min(dp[i-max_nine]+1, dp[i-max_six]+1)

print(dp[n])

Buggy submission (verdict: Runtime Error):
n = int(input())


def get_smallest_under_35(_n):
    j = _n // 9
    cand = []
    for k in range(1, j + 1):
        __n = _n
        __n -= 9 * k
        l = __n // 6
        __n -= l * 6
        cand.append(k + l + __n)
    return min(cand)

def get_smallest_under_215(_n):
    j = _n//81
    _n -= 81*j
    k = _n // 36
    _n -= 36 * k
    return get_smallest_under_35(_n)+j+k

def get_smallest_under_728(_n):
    j = _n // 216
    if j == 0:
        return get_smallest_under_215(_n)

    cand = []
    for k in range(1, j + 1):
        __n = _n
        __n -= 216 * k
        _cnt = k
        if _n <= 215:
            cand.append(get_smallest_under_215(__n) + _cnt)
        else:
            cand.append(get_smallest_under_728(__n) + _cnt)
    return min(cand)


num_list = []

for i in range(1, 7):
    num_list.append(pow(6, i))
    if i <= 5:
        num_list.append(pow(9, i))
num_list = sorted(num_list)
cnt = 0
is_break = True
while is_break :
    for i in range(len(num_list)-1, -1, -1):
        if n <= 728:
            is_break = False
            break
        if num_list[i] < n:
            n -= num_list[i]
            cnt += 1
            break
print(get_smallest_under_728(n)+cnt)