Problem p03008 (python)

Fixed submission:
import math
import sys

N = int(input())
GA, SA, BA = list(map(int, input().split()))
GB, SB, BB = list(map(int, input().split()))

def knapsack(n, ga, sa, ba, gb, sb, bb):
    values = []
    weights = []
    if gb / ga > 1:
        values.append(gb - ga)
        weights.append(ga)
    if sb / sa > 1:
        values.append(sb - sa)
        weights.append(sa)
    if bb / ba > 1:
        values.append(bb - ba)
        weights.append(ba)
    if len(values) == 3:
        # dp[i]: 重さ i 以下で選ぶのの価値の最大値
        dp = [0] * (n + 1)
        dp[0] = n
        for i in range(1, n + 1):
            x = dp[i - 1]
            for w, v in zip(weights, values):
                if i - w >= 0:
                    x = max(x, dp[i - w] + v)
            dp[i] = x
        return dp[n]
    if len(values) == 2:
        w1, w2 = weights
        v1, v2 = values
        if (v1 + w1) / w1 < (v2 + w2) / w2:
            v1, v2 = v2, v1
            w1, w2 = w2, w1
        c1 = n // w1
        c2 = (n - w1 * c1) // w2
        ret = n + v1 * c1 + v2 * c2
        while c1 >= 0:
            a = n - w1 * c1 - w2 * c2
            c1 -= max(1, math.ceil((w2 - a) / w1))
            c2 = (n - w1 * c1) // w2
            ret = max(ret, n + v1 * c1 + v2 * c2)
            if w1 * c1 + w2 * c2 == n:
                break
        return ret
    if len(values) == 1:
        return n + n // weights[0] * values[0]
    return n

ans = knapsack(N, GA, SA, BA, GB, SB, BB)
ans = knapsack(ans, GB, SB, BB, GA, SA, BA)
print(int(ans))

Buggy submission (verdict: Runtime Error):
 from collections import deque


def transaction(N, r):
    x = r[0]
    n = int(N / x[1])
    if N % x[1] == 0:
        return n * x[2]
    if len(r) == 1:
        return n * x[2] + N - n * x[1]
    r.popleft()
    s = N
    for i in range(n + 1):
        tmp = i * x[2] + transaction(N - i * x[1], r)
        if tmp > s:
            s = tmp
    return s

N = int(input())
A = [int(e) for e in input().split()]
B = [int(e) for e in input().split()]

r = []
for i in range(3):
    (a, b) = (A[i], B[i])
    if b > a:
        r.append((b / a, a, b))

if len(r) > 0:
    r.sort(reverse=True)
    dr = deque(maxlen=3)
    for x in r:
        dr.append(x)
    N = transaction(N, dr)

r = []
for i in range(3):
    (a, b) = (A[i], B[i])
    if a > b:
        r.append((a / b, b, a))

if len(r) > 0:
    r.sort(reverse=True)
    dr = deque(maxlen=3)
    for x in r:
        dr.append(x)
    N = transaction(N, dr)

print(N)

Buggy submission (verdict: Runtime Error):
from collections import deque


def transaction(N, r):
    x = r[0]
    n = int(N / x[1])
    if N % x[1] == 0:
        return n * x[2]
    if len(r) == 1:
        return n * x[2] + N - n * x[1]
    r.popleft()
    s = N
    for i in range(n + 1):
        tmp = i * x[2] + transaction(N - i * x[1], r)
        if tmp > s:
            s = tmp
    return s

N = int(input())
A = [int(e) for e in input().split()]
B = [int(e) for e in input().split()]

r = []
for i in range(3):
    (a, b) = (A[i], B[i])
    if b > a:
        r.append((b / a, a, b))

if len(r) > 0:
    r.sort(reverse=True)
    dr = deque(maxlen=3)
    for x in r:
        dr.append(x)
    N = transaction(N, dr)

r = []
for i in range(3):
    (a, b) = (A[i], B[i])
    if a > b:
        r.append((a / b, b, a))

if len(r) > 0:
    r.sort(reverse=True)
    dr.clear()
    for x in r:
        dr.append(x)
    N = transaction(N, dr)

print(N)

Buggy submission (verdict: Runtime Error):
from collections import deque


def transaction(N, r):
    if len(r) == 0:
        return N
    x = r[0]
    n = int(N / x[1])
    if N % x[1] == 0 or len(r) == 1:
        return n * x[2]
    r.popleft()
    s = N
    for i in range(n + 1):
        tmp = i * x[2] + transaction(N - i * x[1], r)
        if tmp > s:
            s = tmp
    return s

N = int(input())
A = [int(e) for e in input().split()]
B = [int(e) for e in input().split()]

r = []
for i in range(3):
    (a, b) = (A[i], B[i])
    if b > a:
        r.append((b / a, a, b))

r.sort(reverse=True)
dr = deque(maxlen=3)
for x in r:
    dr.append(x)
N = transaction(N, dr)

r = []
for i in range(3):
    (a, b) = (A[i], B[i])
    if a > b:
        r.append((a / b, b, a))

r.sort(reverse=True)
dr.clear()
for x in r:
    dr.append(x)

print(transaction(N, r))