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.



Sample input:
23
1 1 1
2 1 1


Sample output:
46

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import math

def main():
    n = int(raw_input())
    ga, sa, ba = map(float, raw_input().split())
    gb, sb, bb = map(float, raw_input().split())

    tmpN = n
    cG = 0.0
    cS = 0.0
    cB = 0.0
    if gb/ga >= sb/sa and gb/ga >= bb/ba:
        if gb/ga > 1:
            cG = int(tmpN)/int(ga)
            tmpN = tmpN - cG * ga
            if sb/sa >= bb/ba and sb/sa > 1:
                cS = int(tmpN)/int(sa)
                tmpN = tmpN - cS * sa
                if bb/ba > 1:
                    cB = int(tmpN)/int(ba)
                    tmpN = tmpN - cB * ba
            else:
                if bb/ba > 1:
                    cB = int(tmpN)/int(ba)
                    tmpN = tmpN - cB * ba
                    if sb/sa > 1:
                        cS = int(tmpN)/int(sa)
                        tmpN = tmpN - cS * sa
    elif sb/sa >= gb/ga and sb/sa >= bb/ba:
        if sb/sa > 1:
            cS = int(tmpN)/int(sa)
            tmpN = tmpN - cS * sa
            if gb/ga >= bb/ba and gb/ga > 1:
                cG = int(tmpN)/int(ga)
                tmpN = tmpN - cG * ga
                if bb/ba > 1:
                    cB = int(tmpN)/int(ba)
                    tmpN = tmpN - cB * ba
            else:
                if bb/ba > 1:
                    cB = int(tmpN)/int(ba)
                    tmpN = tmpN - cB * ba
                    if gb/ga > 1:
                        cG = int(tmpN)/int(ga)
                        tmpN = tmpN - cG * ga
    else:
        if bb/ba > 1:
            cB = int(tmpN)/int(ba)
            tmpN = tmpN - cB * ba
            if gb/ga >= sb/sa and gb/ga > 1:
                cG = int(tmpN)/int(ga)
                tmpN = tmpN - cG * ga
                if sb/sa > 1:
                    cS = int(tmpN)/int(sa)
                    tmpN = tmpN - cS * sa
            else:
                if sb/sa > 1:
                    cS = int(tmpN)/int(sa)
                    tmpN = tmpN - cS * sa
                    if gb/ga > 1:
                        cG = int(tmpN)/int(ga)
                        tmpN = tmpN - cG * ga
    n = tmpN + cG * gb + cS * sb + cB * bb
    tmpN = n
    cG = 0.0
    cS = 0.0
    cB = 0.0
    if ga/gb >= sa/sb and ga/gb >= ba/bb:
        if ga/gb > 1:
            cG = int(tmpN)/int(gb)
            tmpN = tmpN - cG * gb
            if sa/sb >= ba/bb and sa/sb > 1:
                cS = int(tmpN)/int(sb)
                tmpN = tmpN - cS * sb
                if ba/bb > 1:
                    cB = int(tmpN)/int(bb)
                    tmpN = tmpN - cB * bb
            else:
                if ba/bb > 1:
                    cB = int(tmpN)/int(bb)
                    tmpN = tmpN - cB * bb
                    if sa/sb > 1:
                        cS = int(tmpN)/int(sb)
                        tmpN = tmpN - cS * sb
    elif sa/sb >= ga/gb and sa/sb >= ba/bb:
        if sa/sb > 1:
            cS = int(tmpN)/int(sb)
            tmpN = tmpN - cS * sb
            if ga/gb >= ba/bb and ga/gb > 1:
                cG = int(tmpN)/int(gb)
                tmpN = tmpN - cG * gb
                if ba/bb > 1:
                    cB = int(tmpN)/int(bb)
                    tmpN = tmpN - cB * bb
            else:
                if ba/bb > 1:
                    cB = int(tmpN)/int(bb)
                    tmpN = tmpN - cB * bb
                    if ga/gb > 1:
                        cG = int(tmpN)/int(gb)
                        tmpN = tmpN - cG * gb
    else:
        if ba/bb > 1:
            cB = int(tmpN)/int(bb)
            tmpN = tmpN - cB * bb
            if ga/gb >= sa/sb and ga/gb > 1:
                cG = int(tmpN)/int(gb)
                tmpN = tmpN - cG * gb
                if sa/sb > 1:
                    cS = int(tmpN)/int(sb)
                    tmpN = tmpN - cS * sb
            else:
                if sa/sb > 1:
                    cS = int(tmpN)/int(sb)
                    tmpN = tmpN - cS * sb
                    if ga/gb > 1:
                        cG = int(tmpN)/int(gb)
                        tmpN = tmpN - cG * gb
    n = tmpN + cG * ga + cS * sa + cB * ba
    print int(n)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, ga: int, sa: int, ba: int, gb: int, sb: int, bb: int):
    #if ga > gb:
    #    ga, gb = gb, ga
    #if sa > sb:
    #    sa, sb = sb, sa
    #if ba > bb:
    #    ba, bb = bb, ba
    #tmp = [[gb / ga, ga, gb], [sb / sa, sa, sb], [bb / ba, ba, bb]]
    #tmp.sort(reverse=True, key=lambda x: x[0])
    #print(tmp)

    tmp = [[ga, gb], [sa, sb], [ba, bb]]
    tmp.sort(reverse=True, key=lambda x: (x[1] / x[0]))
    ret = N
    rest = N
    for i in range(3):
        if tmp[i][0] < tmp[i][1] and rest >= tmp[i][0]:
            cnt = rest // tmp[i][0]
            ret = ret - cnt + cnt * tmp[i][1]
            rest -= cnt * tmp[i][0]

    rest = ret
    tmp.sort(reverse=True, key=lambda x: (x[0] / x[1]))
    for i in range(3):
        if tmp[i][1] < tmp[i][0] and rest >= tmp[i][1]:
            cnt = rest // tmp[i][1]
            ret = ret - cnt + cnt * tmp[i][0]
            rest -= cnt * tmp[i][1]
            print(ret, cnt, rest)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    g_A = int(next(tokens))  # type: int
    s_A = int(next(tokens))  # type: int
    b_A = int(next(tokens))  # type: int
    g_B = int(next(tokens))  # type: int
    s_B = int(next(tokens))  # type: int
    b_B = int(next(tokens))  # type: int
    solve(N, g_A, s_A, b_A, g_B, s_B, b_B)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def trade(n, rate):
    dp = [0]
    rate = sorted(rate, key=lambda r: float(r[0]) / float(r[1]))
    p = n - 200000
    if p // rate[0][0] > 0:
        d = p // rate[0][0]
        dp = [d * rate[0][1]]
        n -= d * rate[0][0]
    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)

Submission status: Wrong Answer

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

gmin = min(ga,gb)
gmax = max(ga,gb)
smin = min(sa,sb)
smax = max(sa,sb)
bmin = min(ba,bb)
bmax = max(ba,bb)

if min(gmin,smin,bmin) > n:
    print(n)
else:
    ans = 0
    for i in range( (n//gmin) + 1):
        k = n - gmin*i
        for s in range( (k//smin) +1 ):
            ba = k - s*smin
            ja = ba//bmin
            ans = max(ans, i*gmax + s*smax + ja* bmax)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.readline
from sys import setrecursionlimit
setrecursionlimit(10**9)

def inpl(): return list(map(int, input().split()))
N = int(input())
GA = inpl()
GB = inpl()

typ = [GA[i] <= GB[i] for i in range(3)]

if sum(typ) == 3:
    ans = 0
    for g in range(N//GA[0] + 1):
        D = N - GA[0]*g
        for s in range(D//GA[1] + 1):
            b, D2 = divmod(D - GA[1]*s, GA[2])
            ans = max(ans, D2 + g*GB[0] + s*GB[1] + b*GB[2])

elif sum(typ) == 2:
    ans = 0
    x, y = [i for i in range(3) if typ[i]]
    z = [i for i in range(3) if not typ[i]][0]
    for a in range(N//GA[x] + 1):
        b, D = divmod(N - GA[x]*a, GA[y])
        c, D2 = divmod(D + GB[x]*a + GB[y]*b, GB[z])
        ans = max(ans, D2 + c*GA[z])

elif sum(typ) == 1:
    ans = 0
    x, y = [i for i in range(3) if not typ[i]]
    z = [i for i in range(3) if  typ[i]][0]
    c, D = divmod(N, GA[z])
    D += GB[z]*c

    for a in range(D//GB[x] + 1):
        b, D2 = divmod(D-GB[x]*a, GB[y])
        ans = max(ans, D2 + GA[x]*a + GB[y]*b)

else:
    ans = 0
    for g in range(N//GB[0] + 1):
        D = N - GB[0]*g
        for s in range(D//GB[1] + 1):
            b, D2 = divmod(D - GB[1]*s, GB[2])
            ans = max(ans, D2 + g*GA[0] + s*GA[1] + b*GA[2])

print(ans)

Submission status: Wrong Answer

Solution code:
def knapsack_123(values,weights,capacity):
    work = [0 for i in range(capacity+1)]
    for c in range(1, capacity+1):
        candidates = [val + work[c-weight]
                      for val,weight in zip(values,weights) if weight <= c]
        work[c] = max(candidates) if candidates != [] else 0
    return work[-1]
def sol(inp=input):
    n=int(inp())
    prices_a=list(map(int,inp().split()))
    prices_b=list(map(int,inp().split()))
    valA=knapsack_123(values=prices_b,weights=prices_a,capacity=n)
    valB=knapsack_123(values=prices_a,weights=prices_b,capacity=valA)
    return '{}'.format(valB)
print(sol())

Submission status: Wrong Answer

Solution code:
n = int(input())

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

changes.sort(key=lambda x: x[1] / x[0], reverse=True)

new_n = 0

if changes[0][1] < changes[0][0]:
    pass
elif changes[1][1] < changes[1][0]:
    new_n += (n // changes[0][0]) * changes[0][1]
    n %= changes[0][0]
else:
    x1, y1 = changes[0]
    x2, y2 = changes[1]
    x3, y3 = changes[2]
    new_curr_n = 0
    for i in range(1 + n // x1):
        curr = i * y1
        curr_n = n - x1 * i
        plus = (curr_n // x2) * y2
        curr_n %= x2

        if y3 > x3:
            plus += (curr_n // x3) * y3
            curr_n %= x3

        if curr + plus > new_n:
            new_n = curr + plus
            new_curr_n = curr_n
        elif curr + plus == new_n:
            new_curr_n = max(new_curr_n, curr_n)
    n = new_curr_n

n += new_n

changes = [(gb, ga), (sb, sa), (bb, ba)]

changes.sort(key=lambda x: x[1] / x[0], reverse=True)

new_n = 0

if changes[0][1] < changes[0][0]:
    pass
elif changes[1][1] < changes[1][0]:
    new_n += (n // changes[0][0]) * changes[0][1]
    n %= changes[0][0]
else:
    x1, y1 = changes[0]
    x2, y2 = changes[1]
    x3, y3 = changes[2]
    new_curr_n = 0
    for i in range(1 + n // x1):
        curr = i * y1
        curr_n = n - x1 * i
        plus = (curr_n // x2) * y2
        curr_n %= x2

        if y3 > x3:
            plus += (curr_n // x3) * y3
            curr_n %= x3

        if curr + plus > new_n:
            new_n = curr + plus
            new_curr_n = curr_n
        elif curr + plus == new_n:
            new_curr_n = max(new_curr_n, curr_n)
    n = new_curr_n

n += new_n

print(n)

Submission status: Wrong Answer

Solution code:
import numpy
import itertools


def main():
  n = int(input())
  a = numpy.array(list(map(int, input().split())))
  b = numpy.array(list(map(int, input().split())))
  y = 0

  va = a / b
  vb = b / a

  v = [(va[i], a[i], b[i]) for i in range(3)] + [(vb[i], b[i], a[i]) for i in range(3)]
  v.sort(key=lambda x: x[0], reverse=True)
  v = v[:3]

  for s in itertools.permutations(range(3)):
    r = n
    x = 0

    for i in s:
      _, t, f = v[i]
      x += (r // f) * t
      r = r % f

    x += r
    y = max(x, y)

  print(y)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

up = 0
ups = []
down = 0
downs = []
eq = 0
eqs = []
for i in range(3):
    if A[i] < B[i]:
        ups.append((A[i], B[i]))
    elif A[i] == B[i]:
        eqs.append((A[i], B[i]))
    else:
        downs.append((A[i], B[i]))
ans = N

if len(eqs) == 3:
    print(N)
    exit()
if len(ups) == 0:
    tmp = A
    A = B
    B = tmp
    tmp = ups
    ups = downs
    downs = ups

if len(ups) == 3:
    gold_diff = B[0]-A[0]
    silver_diff = B[1]-A[1]
    cupper_diff = B[2]-A[2]
    for gold in range(N//A[0]+1):
        left = N - gold*A[0]
        for silver in range(left//A[1]):
            cupper = (left - silver*A[1])//A[2]
            tmp_ans = (N
                       + gold*gold_diff
                       + silver*silver_diff
                       + cupper*cupper_diff)
            ans = max(ans, tmp_ans)
    print(ans)
elif len(ups) == 2:
    gold_diff = ups[0][1]-ups[0][0]
    silver_diff = ups[1][1]-ups[1][0]
    for gold in range(N//ups[0][0]+1):
        left = N - gold*ups[0][0]
        silver = left // ups[1][0]
        tmp_ans = (N
                   + gold*gold_diff
                   + silver*silver_diff)
        ans = max(ans, tmp_ans)
    if down == 1:
        diff = downs[0][1]-downs[0][0]
        ans += (ans // downs[0][1]) * diff
    print(ans)
elif len(ups) == 1:
    ans += (ans//ups[0][0])*(ups[0][1]-ups[0][0])
    if down == 2:
        gold_diff = downs[0][0]-downs[0][1]
        silver_diff = downs[1][1]-downs[1][1]
        for gold in range(N//downs[0][1]+1):
            left = N - gold*downs[0][1]
            silver = left // downs[1][1]
            tmp_ans = (N
                       + gold*gold_diff
                       + silver*silver_diff)
            ans = max(ans, tmp_ans)
    elif down == 1:
        ans += (ans//downs[0][1])*(downs[0][0]-downs[0][1])
    print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
def nap(N,goods):
    dp=[-1*float('inf')]*(N+1)
    dp[0]=0
    for i in range(N):
        for w,v in goods:
            if i+w<=N:
                dp[i+w]=max(dp[i+w],dp[i]+v)
    return max([dp[i]+N-i for i in range(N+1)])
goods1=[(a,b) for a,b in zip(A,B) if a<b]
goods2=[(b,a) for a,b in zip(A,B) if a>b]
if len(goods1)>0:
    N=nap(N,[(a,b) for a,b in zip(A,B)])
if len(goods2)==0:
    print(N)
elif len(goods2)==1:
    print(N%goods2[0][0]+(N//goods2[0][0])*goods2[0][1])
elif len(goods2)==3:
    print(nap(N,goods2))
else:
    a,b,c,d=goods2[0][0],goods2[0][1],goods2[1][0],goods2[1][1]
    if b-a<d-c:
        a,b=c,d
    elif b-a==d-c and a>c:
        a,b=c,d
    bord=(N//a)*b+((N%a)//c)*d+(N%a)%c
    x=N//a
    ans=bord
    for i in range(1,1+x):
        now=(x-i)*b+((N-(x-i)*a)//c)*d+(N-(x-i)*a)%c
        #if now+d<bord:
            #break
        #else:
        ans=max(ans,now)
    print(ans)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000


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

ag,a_s,ab = A
bg,bs,bb = B
dp = [0 for i in range(N+1)]
g_v = bg - ag
s_v = bs - a_s
b_v = bb - ab
for i in range(N+1):
    if g_v > 0 and ag <= i:
        dp[i] = max(dp[i],dp[i-ag] + g_v)
    if s_v > 0 and a_s <= i:
        dp[i] = max(dp[i],dp[i-a_s] + s_v)
    if b_v > 0 and ab <= i:
        dp[i] = max(dp[i],dp[i-ab] + b_v)

N += max(dp)
dp = [0 for i in range(N+1)]
g_v = -bg + ag
s_v = -bs + a_s
b_v = -bb + ab
for i in range(N+1):
    if g_v > 0 and ag <= i:
        dp[i] = max(dp[i],dp[i-ag] + g_v)
    if s_v > 0 and a_s <= i:
        dp[i] = max(dp[i],dp[i-a_s] + s_v)
    if b_v > 0 and ab <= i:
        dp[i] = max(dp[i],dp[i-ab] + b_v)

N += max(dp)
print(N)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
x = [b[0]/a[0], b[1]/a[1], b[2]/a[2], a[0]/b[0], a[1]/b[1], a[2]/b[2]]
mv = max(x)
mi = x.index(max(x))

import numpy as np
smv = sorted(x)[-2]
smi = np.array(x).argsort()[-2]

tmv = sorted(x)[0]
tmi = np.array(x).argsort()[0]

if mi <= 2:
	p = (N // a[mi]) * b[mi]
	if smi <= 2:
		q = ((N % a[mi]) // a[smi]) * b[smi]
		if tmi <= 2:
			r = (((N % a[mi]) % a[smi]) // a[tmi]) * b[tmi]
		else:
			r = (((N % a[mi]) % a[smi]) // b[tmi-3]) * a[tmi-3]
	else:
		q = ((N % a[mi]) // b[smi-3]) * a[smi-3]
		if tmi <= 2:
			r = (((N % a[mi]) % b[smi-3]) // a[tmi]) * b[tmi]
		else:
			r = (((N % a[mi]) % b[smi-3]) // b[tmi-3]) * a[tmi-3]
    
else:
	p = (N // b[mi-3]) * a[mi-3]
	if smi <= 2:
		q = ((N % b[mi-3]) // a[smi]) * b[smi]
		if tmi <= 2:
			r = (((N % b[mi-3]) % a[smi]) // a[tmi]) * b[tmi]
		else:
			r = (((N % b[mi-3]) % a[smi]) // b[tmi-3]) * a[tmi-3]
	else:
		q = ((N % b[mi-3]) // b[smi-3]) * a[smi-3]
		if tmi <= 2:
			r = (((N % b[mi-3]) % b[smi-3]) // a[tmi]) * b[tmi]
		else:
			r = (((N % b[mi-3]) % b[smi-3]) // b[tmi-3]) * a[tmi-3]


print(p+q+r)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

ans2 = n

for a in range(3):
    for b in range(3):
        for c in range(3):
            ans1 = 0
            for i in range(n + 1 if a == 1 else 1):
                d = n
                d += (B[0] - A[0]) * (i // A[0])
                for j in range(n + 1 - i if b == 1 else 1):
                    d += (B[1] - A[1]) * (j // A[1])
                    k = n - i - j if c == 1 else 0
                    # assert k >= 0
                    d += (B[2] - A[2]) * (k // A[2])
                
                ans1 = max(ans1, d)

            for i in range(ans1 + 1 if a == 2 else 1):
                d = ans1
                d += (A[0] - B[0]) * (i // B[0])
                for j in range(ans1 + 1 - i if b == 2 else 1):
                    d += (A[1] - B[1]) * (j // B[1])
                    k = ans1 - i - j if c == 2 else 0
                    # assert k >= 0
                    d += (A[2] - B[2]) * (k // B[2])
                
                ans2 = max(ans2, d)

print(ans2)

Submission status: Wrong Answer

Solution code:
import itertools
N=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
def times(M,a,b):
    tmp=M
    tmp-=a*(M//a)
    tmp+=b*(M//a)
    return tmp
L=[0,0,0]
for i in range(3):
    if a[i]<b[i]:
        L[i]=-1
    elif a[i]==b[i]:
        L[i]=0
    else:
        L[i]=1
ans=N
for seq in itertools.permutations(range(3),2):
    tmp=N
    tmp=times(tmp,a[seq[0]],b[seq[0]])
    tmp=times(tmp,b[seq[1]],a[seq[1]])
    ans=max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ra = [ int(v) for v in input().split() ]
rb = [ int(v) for v in input().split() ]
ab_rate = [ (rb[i] / ra[i],i,ra[i],rb[i]) for i in range(3)]
ba_rate = [ (ra[i] / rb[i],i,rb[i],ra[i]) for i in range(3)]




def excange(r,x):

    if r[0] <= 1:
        return x, 0
    else:
        y = (x // r[2]) * r[3]
        x = x % r[2]
        return x, y


comb = [[0,1,2],[1,2,0],[2,0,1],[2,1,0],[1,0,2],[0,2,1]]

profmax = n
for k in comb:
    prof,amari = 0, n
    for i in k:
        res = excange(ab_rate[i],amari)
        amari = res[0]
        prof += res[1]
    profmax = max(profmax, prof+amari)

harfprofmax = profmax
for k in comb:
    prof,amari = 0, harfprofmax
    for i in k:
        res = excange(ba_rate[i],amari)
        amari = res[0]
        prof += res[1]
    profmax = max(profmax, prof+amari)
    
print(profmax)

Submission status: Wrong Answer

Solution code:
def li():
    return list(map(int, input().split()))


if __name__ == "__main__":
    n = int(input())
    [ga, sa, ba] = li()
    [gb, sb, bb] = li()

    # A->Bでのトレード成果
    # ga, sa, baの中で最大効率を探して、割り切れる範囲で先に進めてしまう
    # gaが最大効率なら(n//ga - 1)*gaまではgを買ったことにすればいい
    r_g = gb / ga
    r_s = sb / sa
    r_b = bb / ba
    if r_g >= 1 and r_g >= r_s and r_g >= r_b:
        skip = (n // ga - 1) * ga
        dp = [gb * skip] * (n + 1 - skip)
    elif r_s >= 1 and r_s >= r_g and r_s >= r_b:
        skip = (n // sa - 1) * sa
        dp = [sb * skip] * (n + 1 - skip)
    elif r_b >= 1 and r_b >= r_g and r_b >= r_s:
        skip = (n // ba - 1) * ba
        dp = [bb * skip] * (n + 1 - skip)
    else:
        skip = n - 1
        dp = [n - 1] * 2

    for i in range(1, len(dp)):
        g_trade = dp[i - ga] + gb if i - ga >= 0 else dp[i - 1]
        s_trade = dp[i - sa] + sb if i - sa >= 0 else dp[i - 1]
        b_trade = dp[i - ba] + bb if i - ba >= 0 else dp[i - 1]
        dp[i] = max(dp[i - 1] + 1, g_trade, s_trade, b_trade)
    # print(dp)
    a_result = dp[-1]

    # B->Aでのトレード成果
    r_g = ga / gb
    r_s = sa / sb
    r_b = ba / bb
    if r_g >= 1 and r_g >= r_s and r_g >= r_b:
        skip = (a_result // gb - 1) * gb
        dp = [ga * skip] * (a_result + 1 - skip)
    elif r_s >= 1 and r_s >= r_g and r_s >= r_b:
        skip = (a_result // sb - 1) * sb
        dp = [sa * skip] * (a_result + 1 - skip)
    elif r_b >= 1 and r_b >= r_g and r_b >= r_s:
        skip = (a_result // bb - 1) * bb
        dp = [ba * skip] * (a_result + 1 - skip)
    else:
        skip = a_result - 1
        dp = [a_result - 1] * 2

    for i in range(1, len(dp)):
        g_trade = dp[i - gb] + ga if i - gb >= 0 else dp[i - 1]
        s_trade = dp[i - sb] + sa if i - sb >= 0 else dp[i - 1]
        b_trade = dp[i - bb] + ba if i - bb >= 0 else dp[i - 1]
        dp[i] = max(dp[i - 1] + 1, g_trade, s_trade, b_trade)
    # print(dp)
    print(dp[-1])

# n+1個のドングリを取引にかけたときに得られるドングリポテンシャルは
# n個までの最適+1, n-gA個までの最適+gB, n-sA個までの最適+sB, n-bA個までの最適+bBで一番大きくなる値

# AでBより安く金属を手に入れる
# Bでドングリに戻して、Aより安く金属を手に入れる
# Aでドングリに戻して帰る

Submission status: Wrong Answer

Solution code:
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+5050) 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):

            dp[i+1][j] = max(dp[i][j], dp[i+1][j-ai]+bi)
    print(max(dp[3]))
    #print(dp[3][:30])
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)
        #print("a")
    else:
        ans = 0
        (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)

Submission status: Wrong Answer

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

def arbitrage(g1, s1, b1, g2, s2, b2, n):
    before = [g1, s1, b1]
    after = [g2, s2, b2]
    dp = []
    for i in range(4):
        dp_plus = [0] * (n + 1)
        dp.append(dp_plus)
    for i in range(3):
        for j in range(n + 1):
            if j < before[i]:
                dp[i + 1][j] = dp[i][j]
            else:
                dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - before[i]] + after[i])
    return max(max(dp[i][n] for i in range(4)), n)

trade1 = arbitrage(ga, sa, ba, gb, sb, bb, n)
trade2 = arbitrage(gb, sb, bb, ga, sa, ba, trade1)
print(trade2)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

y = max(b[0]-a[0], b[1]-a[1], b[2]-a[2])
z = max(a[0]-b[0], a[1]-b[1],a[2]-b[2])
if y >= 1:
    n += n*y
if z >= 1:
    n += n*z
print(n)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
n = int(input())
ga, sa, ba = [int(item) for item in input().split()]
gb, sb, bb = [int(item) for item in input().split()]

p = [n]
for perm in permutations(["g", "s", "b"]):
    val = n
    after = 0
    for c in perm:
        if c == "g":
            cnt = val // ga
            val %= ga 
            after += cnt * gb
            p.append(after + val)
        if c == "s":
            cnt = val // sa
            val %= sa 
            after += cnt * sb
            p.append(after + val)
        if c == "b":
            cnt = val // ba
            val %= ba 
            after += cnt * bb
    p.append(after+val)
p = [max(p)]
for perm in permutations(["g", "s", "b"]):
    val = p[0]
    after = 0
    for c in perm:
        if c == "g":
            cnt = val // gb
            val %= gb 
            after += cnt * ga
            p.append(after + val)
        if c == "s":
            cnt = val // sb
            val %= sb 
            after += cnt * sa
            p.append(after + val)
        if c == "b":
            cnt = val // bb
            val %= bb 
            after += cnt * ba
    after += val
    p.append(after)
print(max(p))

Submission status: Wrong Answer

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

gmin = min(ga,gb)
gmax = max(ga,gb)
smin = min(sa,sb)
smax = max(sa,sb)
bmin = min(ba,bb)
bmax = max(ba,bb)


ans = 0
for i in range( (n//gmin) + 1):
    k = n - gmin*i
    for s in range( (k//smin) +1 ):
        ba = k - s*smin
        ja = ba//bmin
        ans = max(ans, i*gmax + s*smax + ja* bmax)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

ans2 = n

for a in range(3):
    for b in range(3):
        for c in range(3):
            ans1 = n
            for i in range(n + 1 if a == 1 else 1):
                d = n
                d += (B[0] - A[0]) * (i // A[0])
                for j in range(n + 1 - i if b == 1 else 1):
                    d += (B[1] - A[1]) * (j // A[1])
                    k = n - i - j if c == 1 else 0
                    # assert k >= 0
                    d += (B[2] - A[2]) * (k // A[2])
                
                ans1 = max(ans1, d)

            for i in range(ans1 + 1 if a == 2 else 1):
                d = ans1
                d += (A[0] - B[0]) * (i // B[0])
                for j in range(ans1 + 1 - i if b == 2 else 1):
                    d += (A[1] - B[1]) * (j // B[1])
                    k = ans1 - i - j if c == 2 else 0
                    # assert k >= 0
                    d += (A[2] - B[2]) * (k // B[2])
                
                ans2 = max(ans2, d)

print(ans2)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 20:54:40 2019

@author: Yamazaki Kenichi
"""

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

A_B = [B[0] / A[0], B[1] / A[1], B[2] / A[2]]
a, b =[], []
if A_B[0] > 1:
    a.append([A_B[0],0])
else:
    b.append([A_B[0],0])
if A_B[1] > 1:
    a.append([A_B[1],1])
else:
    b.append([A_B[1],1])
if A_B[2] > 1:
    a.append([A_B[2],2])
else:
    b.append([A_B[2],2])

a.sort(reverse=True)
b.sort(reverse=True)

ans = [0, 0, 0, N]

for c in a:
    ans[c[1]] = ans[3] // A[c[1]]
    ans[3] -= ans[c[1]] * A[c[1]]
#print(ans)
for i in range(3):
    ans[3] += ans[i] * B[i]
    ans[i] = 0
#print(ans)
for c in b:
    ans[c[1]] = ans[3] // B[c[1]]
    ans[3] -= ans[c[1]] * B[c[1]]
#print(ans)
for i in range(3):
    ans[3] += ans[i] * A[i]
    ans[i] = 0
#print(ans)
print(ans[3])

Submission status: Wrong Answer

Solution code:
import sys

cin = sys.stdin
N, = map(int, cin.readline().split())
xa = list(map(int, cin.readline().split()))
xb = list(map(int, cin.readline().split()))


from itertools import permutations


def step(xa, xb, ttl):
    a2b = list(filter(lambda i:xb[i] - xa[i]>0, (i for i in range(3))))
    maxN_a2b = ttl
    if a2b:
        n = len(a2b)
        dp = [[-0x7fff7fff] * (ttl + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        for j in range(n):
            i = a2b[j]
            for k in range(0, ttl+1):
                for li, l in enumerate(range(k, ttl+1, xa[i])):
                    dp[j+1][l] = max(dp[j+1][l], dp[0][k] + li * xb[i])
        maxN_a2b = max(dp[n])
    return maxN_a2b


N1 = step(xa, xb, N)
N2 = step(xb, xa, N1)
print(N2)

Submission status: Wrong Answer

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

Achange = []
Bchange = []

for i in range(3):
  if A[i] > B[i]:
    Bchange.append(i)
  elif A[i] < B[i]:
    Achange.append(i)

#print(Achange, Bchange)

# 最初のA交換所→B交換所
Dmax1 = N
if Achange:
  if len(Achange)==3:
    i = Achange[0]
    j = Achange[1]
    k = Achange[2]
    for x in range(5001):
      for y in range(5001):
        if A[i]*x+B[j]*y <= N:
          Dmax1 = max(Dmax1, (N-A[i]*x-B[j]*y)%A[k] + (N-A[i]*x-B[j]*y)//A[k] * B[k])
    
  if len(Achange)==2:
    i = Achange[0]
    j = Achange[1]
    for x in range(5001):
      if A[i]*x <= N:
          Dmax1 = max(Dmax1, (N-A[i]*x)%A[j] + (N-A[i]*x)//A[j] * B[j])
    
  if len(Achange)==1:
    i = Achange[0]
    Dmax1 = max(Dmax1, N%A[i] + (N//A[i] * B[i]))
    
#print(Dmax1)    

#次のB交換所→A交換所
Achange = Bchange
Dmax2 = Dmax1

if Achange:
  if len(Achange)==3:
    i = Achange[0]
    j = Achange[1]
    k = Achange[2]
    for x in range(5001):
      for y in range(5001):
        if A[i]*x+B[j]*y <= Dmax1:
          Dmax2 = max(Dmax2, (Dmax1-A[i]*x-B[j]*y)%A[k] + (Dmax1-A[i]*x-B[j]*y)//A[k] * B[k])
    
  if len(Achange)==2:
    i = Achange[0]
    j = Achange[1]
    for x in range(5001):
      if A[i]*x <= Dmax1:
          Dmax2 = max(Dmax2, (Dmax1-A[i]*x)%A[j] + (Dmax1-A[i]*x)//A[j] * B[j])
    
  if len(Achange)==1:
    i = Achange[0]
    Dmax2 = max(Dmax2, Dmax1%A[i] + (Dmax1//A[i] * B[i]))
    
print(Dmax2)