Problem:
 Score : 600 points    Problem Statement The squirrel Chokudai has N acorns.
One day, he decides to do some trades in multiple precious metal exchanges to make more acorns.  His plan is as follows:   Get out of the nest with N acorns in his hands.  Go to Exchange A and do some trades.  Go to Exchange B and do some trades.  Go to Exchange A and do some trades.  Go back to the nest.   In Exchange X  (X = A, B) , he can perform the following operations any integer number of times (possibly zero) in any order:   Lose g_{X} acorns and gain 1 gram of gold.  Gain g_{X} acorns and lose 1 gram of gold.  Lose s_{X} acorns and gain 1 gram of silver.  Gain s_{X} acorns and lose 1 gram of silver.  Lose b_{X} acorns and gain 1 gram of bronze.  Gain b_{X} acorns and lose 1 gram of bronze.   Naturally, he cannot perform an operation that would leave him with a negative amount of acorns, gold, silver, or bronze.  What is the maximum number of acorns that he can bring to the nest?
Note that gold, silver, or bronze brought to the nest would be worthless because he is just a squirrel.      Constraints  1 \leq N \leq 5000  1 \leq g_{X} \leq 5000  1 \leq s_{X} \leq 5000  1 \leq b_{X} \leq 5000  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  g_A  s_A  b_A  g_B  s_B  b_B       Output Print the maximum number of acorns that Chokudai can bring to the nest.        Sample Input 1 23
1 1 1
2 1 1      Sample Output 1 46  He can bring 46 acorns to the nest, as follows:   In Exchange A , trade 23 acorns for 23 grams of gold. {acorns, gold, silver, bronze}={ 0,23,0,0 }  In Exchange B , trade 23 grams of gold for 46 acorns. {acorns, gold, silver, bronze}={ 46,0,0,0 }  In Exchange A , trade nothing. {acorns, gold, silver, bronze}={ 46,0,0,0 }   He cannot have 47 or more acorns, so the answer is 46 .

Solution (Python):

from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import random
import collections
import math
import itertools

def real_main():
    n = read_int()
    aprice = read_int_array()
    bprice = read_int_array()

    print(solve(n, aprice, bprice))


def solve(n, aprice, bprice):
    ab, ba = [], []
    for i in range(3):
        if aprice[i] < bprice[i]:
            ab.append((aprice[i], bprice[i]))
        elif aprice[i] > bprice[i]:
            ba.append((bprice[i], aprice[i]))

    return aux(ba, aux(ab, n))

def aux(ab, n):
    dp = [0] * (n + 1)
    for w, c in ab:
        for i in range(w, len(dp)):
            dp[i] = max(dp[i], dp[i - w] + c)
    new_n = n
    for i in range(len(dp)):
        new_n = max(new_n, n - i + dp[i])
    return new_n


def main():
    if False and 'PYCHARM_HOSTED' in os.environ:
        main_pycharm()
    else:
        real_main()


from copy import deepcopy
def main_pycharm():
    solution = solve

    test_inputs = None
    test_outputs = None
    judge = None
    slow_solution = None
    if solution is not None:
        if test_outputs is not None:
            test_with_answers(solution, test_inputs, test_outputs)
        if judge is not None:
            test_with_judge(solution, test_inputs, judge)
        if slow_solution is not None:
            test_with_slow_solution(solution, test_inputs, slow_solution)


def test_with_answers(solution, inputs_answers):
    total, wrong = 0, 0
    for args, test_ans in inputs_answers:
        ans = solution(*args.copy())
        if ans != test_ans:
            print('WRONG! ans=%s, test_ans=%s, args=%s' % (ans, test_ans, args))
            wrong += 1
        else:
            print('GOOD')
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_judge(solution, inputs_gen, judge):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        if not judge(deepcopy(ans), *deepcopy(args)):
            print('WRONG! ans=%s, args=%s' % (ans, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_slow_solution(solution, inputs_gen, solution_slow):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        slow = solution_slow(*deepcopy(args))
        if ans != slow:
            print('WRONG! ans=%s, slow=%s, args=%s' % (ans, slow, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

read = input
read_int = lambda: int(input())
read_array = lambda sep=None, maxsplit=-1: input().split(sep, maxsplit)
read_int_array = lambda: [int(a) for a in read_array()]



if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
a1, a2, a3 = map(int, input().split())
b1, b2, b3 = map(int, input().split())
A = [a1, a2, a3]
B = [b1, b2, b3]
if (a1<=b1 and a2<=b2 and a3<=b3) or (a1>=b1 and a2>=b2 and a3>=b3):
    if a1>b1 or a2>b2 or a3>b3:
        A, B = B, A
    dp = [[-float("inf")]*(N+1) for _ in range(4)]
    dp[0][0] = 0
    for i in range(3):
        ai = A[i]
        bi = B[i]
        for j in range(N+1):
            if j-ai>=0:
                dp[i+1][j] = max(dp[i][j], dp[i+1][j-ai]+bi)
            else:
                dp[i+1][j] = dp[i][j]
    ans = 0
    for i, v in enumerate(dp[3]):
        ans = max(ans, v+(N-i))
    print(ans)

    
else:
    C, D = [], []
    for a, b in zip(A, B):
        if a <= b:
            C.append([a, b])
        else:
            D.append([b, a])

    if len(C)==1:
        a, b = C[0]
        q, n = divmod(N, a)
        N_ = q*b + n
    else:
        N_ = N
        (a1, b1), (a2, b2) = C
        for i in range(N + 1):
            j = N - i
            q1, n1 = divmod(i, a1)
            q2, n2 = divmod(j, a2)
            N_ = max(N_, q1 * b1 + q2 * b2 + n1 + n2)

    if len(D)==1:
        a, b = D[0]
        q, n = divmod(N_, a)
        print(q*b + n)
        
    else:
        ans = N_
        (a1, b1), (a2, b2) = D
        for i in range(N_+1):
            j = N_ - i
            q1, n1 = divmod(i, a1)
            q2, n2 = divmod(j, a2)
            ans = max(ans, q1*b1+q2*b2+n1+n2)
        print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

N=int(input())

ga,sa,ba=map(int,input().split())
gb,sb,bb=map(int,input().split())

ANS=N

def acorns(N,ga,sa,ba,gb,sb,bb):
    X=[]
    if ga<gb:
        X.append((ga,gb))
    if sa<sb:
        X.append((sa,sb))
    if ba<bb:
        X.append((ba,bb))

    if len(X)==0:
        return N
    
    if len(X)==1:
        ga,gb=X[0][0],X[0][1]
        t=N//ga
        return N-t*ga+t*gb
    
    if len(X)==2:
        ga,gb=X[0][0],X[0][1]
        sa,sb=X[1][0],X[1][1]
        ANS=N
        
        t=N//ga
        for i in range(t+1):
            M=i*gb
            R=N-i*ga
            u=R//sa

            ANS=max(ANS,M+R+u*(sb-sa))
        return ANS
    
    if len(X)==3:
        ga,gb=X[0][0],X[0][1]
        sa,sb=X[1][0],X[1][1]
        ba,bb=X[2][0],X[2][1]
        ANS=N

        t=N//ga
        for i in range(t+1):

            R=N-i*ga
            u=R//sa
            
            for j in range(u+1):
                R2=R-j*sa

                ANS=max(ANS,i*gb+j*sb+R2+R2//ba*(bb-ba))

        return ANS

N2=acorns(N,ga,sa,ba,gb,sb,bb)
print(acorns(N2,gb,sb,bb,ga,sa,ba))

Solution (Python):
N = int(input())
gA, sA, bA = map(int, input().split())
gB, sB, bB = map(int, input().split())


lstAB_2 = [[gA, gB-gA], [sA, sB-sA], [bA, bB-bA]]
lstBA_2 = [[gB, gA-gB], [sB, sA-sB], [bB, bA-bB]]
lstAB = []
for i in range(3):
    if lstAB_2[i][1] > 0:
        lstAB += [lstAB_2[i]]  

lstBA = []
for i in range(3):
    if lstBA_2[i][1] > 0:
        lstBA += [lstBA_2[i]]

dp = [[0] * (N+1) for _ in range(len(lstAB)+1)]
for i in range(len(lstAB)):
    for j in range(N+1):
        if j < lstAB[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-lstAB[i][0]]+lstAB[i][1])

N += dp[len(lstAB)][N]


dp2 = [[0] * (N+1) for _ in range(len(lstBA)+1)]
for i in range(len(lstBA)):
    for j in range(N+1):
        if j < lstBA[i][0]:
            dp2[i+1][j] = dp2[i][j]
        else:
            dp2[i+1][j] = max(dp2[i][j], dp2[i+1][j-lstBA[i][0]]+lstBA[i][1])
print (N + dp2[len(lstBA)][N])

Solution (Python):
n = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())

def trade(n, rate):
    dp = [0]
    r = sorted(rate, key=lambda r: float(r[0]) / float(r[1]))[0]
    p = n - 10000000
    if p // r[0] > 0:
        d = p // r[0]
        n -= d * r[0]
        dp = [d * r[1]]
    for i in range(n):
        v = dp[i] + 1
        for ra, rb in rate:
            if i + 1 >= ra:
                v = max(v, dp[i + 1 - ra] + rb)
        dp.append(v)
    return dp[-1]

n = trade(n, [(ga, gb), (sa, sb), (ba, bb)])
n = trade(n, [(gb, ga), (sb, sa), (bb, ba)])
print(n)

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op



inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    
    n = get_int()
    ga, sa, ba = get_li()
    gb, sb, bb = get_li()
    dp1 = [0] * (n + 1)
    dp1[0] = n
    for i in range(1, n + 1):
        _max = dp1[i-1]
        if i - ga >= 0:
            _max = max(_max, dp1[i-ga] + gb - ga)
        if i - sa >= 0:
            _max = max(_max, dp1[i-sa] + sb - sa)
        if i - ba >= 0:
            _max = max(_max, dp1[i-ba] + bb - ba)
        dp1[i] = _max
    n = dp1[n]
    dp2 = [0] * (n + 1)
    dp2[0] = n
    for i in range(1, n + 1):
        _max = dp2[i-1]
        if i - gb >= 0:
            _max = max(_max, dp2[i-gb] + ga - gb)
        if i - sb >= 0:
            _max = max(_max, dp2[i-sb] + sa - sb)
        if i - bb >= 0:
            _max = max(_max, dp2[i-bb] + ba - bb)
        dp2[i] = _max
    print(dp2[n])
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
ga, sa, ba = list(map(int, input().split()))
gb, sb, bb = list(map(int, input().split()))

w_ab = []
v_ab = []

if ga < gb:
    w_ab.append(ga)
    v_ab.append(gb)
if sa < sb:
    w_ab.append(sa)
    v_ab.append(sb)
if ba < bb:
    w_ab.append(ba)
    v_ab.append(bb)

num = (n+1)*(len(w_ab)+1)
dp = [0]*num
for i in range(len(w_ab)):
    for j in range(n+1):
        if j < w_ab[i]:
            dp[(i+1)*(n+1) + j] = dp[i*(n+1) + j]
        else:
            dp[(i+1)*(n+1) + j] = max(dp[i*(n+1) + j], dp[(i+1)*(n+1) + j - w_ab[i]] + v_ab[i])
ans = 0
length = len(w_ab)
for j in range(n+1):
    ans = max(ans, dp[length*(n+1) + j] + n-j)
n = ans

w_ab = []
v_ab = []

if ga > gb:
    w_ab.append(gb)
    v_ab.append(ga)
if sa > sb:
    w_ab.append(sb)
    v_ab.append(sa)
if ba > bb:
    w_ab.append(bb)
    v_ab.append(ba)

num = (n+1)*(len(w_ab)+1)
dp = [0]*num
for i in range(len(w_ab)):
    for j in range(n+1):
        if j < w_ab[i]:
            dp[(i+1)*(n+1) + j] = dp[i*(n+1) + j]
        else:
            dp[(i+1)*(n+1) + j] = max(dp[i*(n+1) + j], dp[(i+1)*(n+1) + j - w_ab[i]] + v_ab[i])

length = len(w_ab)
ans = 0
for j in range(n+1):
    ans = max(ans, dp[length*(n+1) + j] + n-j)
print(ans)

Solution (Python):
def main():
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))

    ab = []
    ba = []
    for i in range(3):
        if a[i]-b[i] < 0:
            ab.append((a[i],b[i]))
        elif a[i]-b[i] > 0:
            ba.append((a[i],b[i]))

    dp = [0]*(n+1)
    if len(ab) > 0:
        for i in range(n+1):
            dp[i] = i
            for x,y in ab:
                if i >= x:
                    dp[i] = max(dp[i],dp[i-x]+y)
    p = max(n,dp[n])

    dp2 = [0]*(p+1)

    if len(ba) > 0:
        for i in range(p+1):
            dp2[i] = i
            for y,x in ba:
                if i >= x:
                    dp2[i] = max(dp2[i],dp2[i-x]+y)
    print(max(p,dp2[-1]))
if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
Ga, Sa, Ba = map(int, input().split())
Gb, Sb, Bb = map(int, input().split())

dp = [0]
for i in range(1, N+1):
  tmp = dp[-1] + 1
  if Ga <= i:
    t2 = dp[-Ga] + Gb
    tmp = tmp if tmp > t2 else t2
  if Sa <= i:
    t2 = dp[-Sa] + Sb
    tmp = tmp if tmp > t2 else t2
  if Ba <= i:
    t2 = dp[-Ba] + Bb
    tmp = tmp if tmp > t2 else t2
  dp.append(tmp)
N2 = dp[-1]

dp = [0]
for i in range(1, N2+1):
  tmp = dp[-1] + 1
  if Gb <= i:
    t2 = dp[-Gb] + Ga
    tmp = tmp if tmp > t2 else t2
  if Sb <= i:
    t2 = dp[-Sb] + Sa
    tmp = tmp if tmp > t2 else t2
  if Bb <= i:
    t2 = dp[-Bb] + Ba
    tmp = tmp if tmp > t2 else t2
  dp.append(tmp)
print(dp[-1])

Solution (Python):
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
C=[(B[i]-A[i],A[i],B[i]) for i in range(3)]
C.sort()
ans=0

if C[2][0]<=0:
  for i in range(3):
    C[i]=(A[i]-B[i],B[i],A[i])
  C.sort()
  A,B=B,A


if C[0][0]>=0:
  for p in range(N+1):
    for q in range(N+1):
      if p*A[0]+q*A[1]<=N:
        r=(N-p*A[0]-q*A[1])//A[2]
        s=N-(p*A[0]+q*A[1]+r*A[2])
        ans=max(ans,p*B[0]+q*B[1]+r*B[2]+s)
elif C[0][0]<0 and C[1][0]>=0:
  for p in range(N+1):
    if p*C[1][1]<=N:
      q=(N-C[1][1]*p)//C[2][1]
      s=N-(p*C[1][1]+q*C[2][1])
      n=p*C[1][2]+q*C[2][2]+s
      r,m=n//C[0][2],n-C[0][2]*(n//C[0][2])
      n=m+C[0][1]*r
      ans=max(ans,n)
else:
  r,m=N//C[2][1],N-C[2][1]*(N//C[2][1])
  N_=m+C[2][2]*r
  for p in range(N_+1):
    if p*C[0][2]<=N_:
      q=(N_-C[0][2]*p)//C[1][2]
      s=N_-(p*C[0][2]+q*C[1][2])
      n=p*C[0][1]+q*C[1][1]+s
      
      ans=max(ans,n)
        
  
    
print(ans)

Solution (Python):
N = int(input())
A_array = map(int, input().split())
B_array = map(int, input().split())

AB_use = []
BA_use = []
for a, b in zip(A_array, B_array):

    if a > b:
        BA_use.append((b, a))

    elif b > a:
        AB_use.append((a, b))

ans = N

if len(AB_use):
    if len(AB_use) == 1:
        w, v = AB_use[0]
        ans = v * (ans//w) + (ans % w)
    else:
        ans_array = [0] * (ans + 1)
        for i in range(1, ans + 1):
            ans_max = ans_array[i - 1] + 1
            for j in AB_use:
                w, v = j
                if w <= i:
                    ans_max = max(ans_max, ans_array[i - w] + v)
            ans_array[i] = ans_max
        
        ans = ans_array[ans]


if len(BA_use):
    if len(BA_use) == 1:
        w, v = BA_use[0]
        ans = v * (ans//w) + (ans % w)
    else:
        ans_array = [0] * (ans + 1)
        for i in range(1, ans + 1):
            ans_max = ans_array[i - 1] + 1
            for j in BA_use:
                w, v = j
                if w <= i:
                    ans_max = max(ans_max, ans_array[i - w] + v)
            ans_array[i] = ans_max
        ans = ans_array[ans]
        
print(ans)

Solution (Python):
N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]

def calc(n, X, Y):
    Z = [(X[i], Y[i]) for i in range(3) if Y[i] > X[i]]
    k = len(Z)
    if k == 0:
        return n
    if k == 1:
        a = n//Z[0][0]
        return n + a*(Z[0][1]-Z[0][0])
    if k == 2:
        ma = 0
        for a in range(n+1):
            b = (n-a*Z[0][0])//Z[1][0]
            if b >= 0:
                ma = max(ma, n + a*(Z[0][1]-Z[0][0]) + b*(Z[1][1]-Z[1][0]))
        return ma
    ma = 0
    for a in range(n+1):
        for b in range(n+1-a):
            c = (n-a*Z[0][0]-b*Z[1][0])//Z[2][0]
            if c >= 0:
                ma = max(ma, n + a*(Z[0][1]-Z[0][0]) + b*(Z[1][1]-Z[1][0]) + c*(Z[2][1]-Z[2][0]))
    return ma

print(calc(calc(N, A, B), B, A))

Solution (Python):
def solve(n, ga, sa, ba, gb, sb, bb):
    ans = n
    for g in range(1 if ga >= gb else n // ga + 1):
        n2 = n - g * ga
        tmp1 = g * gb
        if ba >= bb:
            s = n2 // sa
            ans = max(ans, n2 + tmp1, n2 - s * sa + tmp1 + s * sb)
        elif sa >= sb:
            b = n2 // ba
            ans = max(ans, n2 + tmp1, n2 - b * ba + tmp1 + b * bb)
        else:
            for s in range(n2 // sa + 1):
                b = (n2 - s * sa) // ba
                ans = max(ans, n2 - s * sa - b * ba + tmp1 + s * sb + b * bb)
    return ans


n = int(input())
ga, sa, ba = list(map(int, input().split()))
gb, sb, bb = list(map(int, input().split()))
n2 = solve(n, ga, sa, ba, gb, sb, bb)
n3 = solve(n2, gb, sb, bb, ga, sa, ba)
print(n3)

Solution (Python):


def F(N, A, B):
  
  
  dp = [0] * (N+1)
  for n in range(N+1):
    x = n
    for j in range(3):
      if n >= A[j]:
        y = dp[n-A[j]] + B[j]
        if x < y:
          x = y
    dp[n] = x
  return dp[N]

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

answer = F(F(N,A,B),B,A)
print(answer)

Solution (Python):
import sys
range = xrange
input = raw_input

n = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]


DP = [0]*(n+1)
DP[n] = n
for j in range(3):
    sell = A[j]
    get_back = B[j]
    if get_back > sell:
        for i in reversed(range(sell,len(DP))):
            val1 = DP[i - sell]
            val2 = DP[i] + get_back - sell
            if val2 > val1:
                DP[i-sell] = val2
n = max(DP)
A,B = B,A

DP = [0]*(n+1)
DP[n] = n
for j in range(3):
    sell = A[j]
    get_back = B[j]
    if get_back > sell:
        for i in reversed(range(sell,len(DP))):
            val1 = DP[i - sell]
            val2 = DP[i] + get_back - sell
            if val2 > val1:
                DP[i-sell] = val2

print(max(DP))