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 -*-
"""
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()

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:
#D問題
N = int(input())
GSB1 = list(map(int,input().split()))
GSB2 = list(map(int,input().split()))

X = [N for i in range(7)]

x = X[0]
n1 = x//GSB1[0]
x-=n1
n2 = x//GSB1[1]
x-=n2
n3 = x//GSB1[2]
x+=n3*GSB2[2]
x+=n2*GSB2[1]
x+=n1*GSB2[0]
X[0] = x

x = X[1]
n1 = x//GSB1[0]
x-=n1
n2 = x//GSB1[2]
x-=n2
n3 = x//GSB1[1]
x+=n3*GSB2[1]
x+=n2*GSB2[2]
x+=n1*GSB2[0]
X[1] = x

x = X[2]
n1 = x//GSB1[1]
x-=n1
n2 = x//GSB1[0]
x-=n2
n3 = x//GSB1[2]
x+=n3*GSB2[2]
x+=n2*GSB2[0]
x+=n1*GSB2[1]
X[2] = x

x = X[3]
n1 = x//GSB1[1]
x-=n1
n2 = x//GSB1[2]
x-=n2
n3 = x//GSB1[0]
x+=n3*GSB2[0]
x+=n2*GSB2[2]
x+=n1*GSB2[1]
X[3] = x

x = X[4]
n1 = x//GSB1[2]
x-=n1
n2 = x//GSB1[0]
x-=n2
n3 = x//GSB1[1]
x+=n3*GSB2[1]
x+=n2*GSB2[0]
x+=n1*GSB2[2]
X[4] = x

x = X[5]
n1 = x//GSB1[2]
x-=n1
n2 = x//GSB1[1]
x-=n2
n3 = x//GSB1[0]
x+=n3*GSB2[0]
x+=n2*GSB2[1]
x+=n1*GSB2[2]
X[5] = x

N = max(X)

X = [N for i in range(7)]

x = X[0]
n1 = x//GSB2[0]
x-=n1
n2 = x//GSB2[1]
x-=n2
n3 = x//GSB2[2]
x+=n3*GSB1[2]
x+=n2*GSB1[1]
x+=n1*GSB1[0]
X[0] = x

x = X[1]
n1 = x//GSB2[0]
x-=n1
n2 = x//GSB2[2]
x-=n2
n3 = x//GSB2[1]
x+=n3*GSB1[1]
x+=n2*GSB1[2]
x+=n1*GSB1[0]
X[1] = x

x = X[2]
n1 = x//GSB2[1]
x-=n1
n2 = x//GSB2[0]
x-=n2
n3 = x//GSB2[2]
x+=n3*GSB1[2]
x+=n2*GSB1[0]
x+=n1*GSB1[1]
X[2] = x

x = X[3]
n1 = x//GSB2[1]
x-=n1
n2 = x//GSB2[2]
x-=n2
n3 = x//GSB2[0]
x+=n3*GSB1[0]
x+=n2*GSB1[2]
x+=n1*GSB1[1]
X[3] = x

x = X[4]
n1 = x//GSB2[2]
x-=n1
n2 = x//GSB2[0]
x-=n2
n3 = x//GSB2[1]
x+=n3*GSB1[1]
x+=n2*GSB1[0]
x+=n1*GSB1[2]
X[4] = x

x = X[5]
n1 = x//GSB2[2]
x-=n1
n2 = x//GSB2[1]
x-=n2
n3 = x//GSB2[0]
x+=n3*GSB1[0]
x+=n2*GSB1[1]
x+=n1*GSB1[2]
X[5] = x

print(max(X))

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]
    r = sorted(rate, key=lambda r: float(r[0]) / float(r[1]))[0]
    p = n - 2500000
    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)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
#rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

N = ri()
ga,sa,ba = rl()
gb,sb,bb = rl()
G = int(ga>=gb)
S = int(sa>=sb)
B = int(ba>=bb)
GSB =G+S+B
xa,xb,ya,yb,za,zb=ga,gb,sa,sb,ba,bb
mode = 0
if GSB==3:
    mode = 1
elif GSB==2:
    mode = 1
    if G==0:
        None
    elif S==0:
        xa,xb,ya,yb = sa,sb,ga,gb
    elif B==0:
        xa,xy,za,zb = ba,bb,ga,gb
elif GSB==1:
    mode = 0
    if G==1:
        None
    elif S==1:
        xa,xb,ya,yb = sa,sb,ga,gb
    elif B==1:
        xa,xy,za,zb = ba,bb,ga,gb
elif GSB==0:
    mode = 0

ans = 0
if GSB==0 or GSB==3:
    xa,xb,ya,yb,za,zb=min(xa,xb),max(xa,xb),min(ya,yb),max(ya,yb),min(za,zb),max(za,zb)
    if za > ya:
        ya,yb,za,zb = za,zb,ya,yb
    for x in range(N//xa+1):
        n0 = N - x*xa
        for y in range(n0//ya+1):
            n1 = n0 - y*ya
            z = n1//za
            n1 = n1 - z*za
            ans = max(ans,n1+x*xb+y*yb+z*zb)
elif GSB==1:
    if za > ya:
        ya,yb,za,zb = za,zb,ya,yb
    for y in range(N//ya+1):
        n = N - y*ya
        z = n//za
        n = n - z*za
        n = n + y*yb + z*zb
        x = n//xb
        n = n - x*xb
        ans = max(ans,n+x*xa)
elif GSB==2:
    if zb > yb:
        ya,yb,za,zb = za,zb,ya,yb
    for x in range(N//xa+1):
        n0 = N - x*xa + x*xb
        for y in range(n0//yb+1):
            n1 = n0 - y*yb
            z = n1//zb
            n1 = n1 - z*zb
            ans = max(ans,n1+y*ya+z*za)
else:
    assert (False)
if ans == 0:
    assert (False)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
gsba = list(map(int, input().split()))
gsbb = list(map(int, input().split()))
diff1 = [(N // gsba[i]) * gsbb[i] + N % gsba[i] if gsbb[i] - gsba[i] > 0 else 0 for i in range(3)]
diff2 = [(N // gsbb[i]) * gsba[i] + N % gsbb[i] if gsba[i] - gsbb[i] > 0 else 0 for i in range(3)]
maxi = max(diff1+diff2)
if maxi == 0:
    print(N)
    exit()
f = 0
index = -1
if f == 0:
    for i in range(3):
        if diff1[i] == maxi:
            f = 1
            index = i
            break
if f == 0:
    for i in range(3):
        if diff2[i] == maxi:
            f = 2
            index = i
            break

ans = 0
if f == 1:
    ans += (N // gsba[index]) * gsbb[index]
    N = N % gsba[index]
else:
    ans += (N // gsbb[index]) * gsba[index]
    N = N % gsbb[index]
tmp = 0
if f == 1:
    for i in range(3):
        if diff2[i] > 0:
            tmp = max(tmp, (N // gsbb[i]) * gsba[i])
else:
    for i in range(3):
        if diff1[i] > 0:
            tmp = max(tmp, (N // gsba[i]) * gsbb[i])
ans += tmp
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
gsbA = list(map(int,input().split()))
gsbB = list(map(int,input().split()))
ans = N
for i,j,k in ((0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0)):
    tmp = [0,0,0,N]
    if gsbA[i]<gsbB[i]:
        tmp[i] = tmp[3] // gsbA[i]
        tmp[3] -= tmp[i] * gsbA[i]
    if gsbA[j]<gsbB[j]:
        tmp[j] = tmp[3] // gsbA[j]
        tmp[3] -= tmp[j] * gsbA[j]
    if gsbA[k]<gsbB[k]:
        tmp[k] = tmp[3] // gsbA[k]
        tmp[3] -= tmp[k] * gsbA[k]
    ans = max(ans,tmp[3]+sum(tmp[l]*(gsbB[l]) for l in range(3)))
M = ans
for i,j,k in ((0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0)):
    tmp = [0,0,0,M]
    if gsbA[i]>gsbB[i]:
        tmp[i] = tmp[3] // gsbB[i]
        tmp[3] -= tmp[i] * gsbB[i]
    if gsbA[j]>gsbB[j]:
        tmp[j] = tmp[3] // gsbB[j]
        tmp[3] -= tmp[j] * gsbB[j]
    if gsbA[k]>gsbB[k]:
        tmp[k] = tmp[3] // gsbB[k]
        tmp[3] -= tmp[k] * gsbB[k]
    ans = max(ans,tmp[3]+sum(tmp[l]*(gsbA[l]) for l in range(3)))
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())

ans = 0
if (ga < gb) and (sa < sb) and (ba < bb):
    for G in range(5001):
        for S in range(5001):
            if ga * G + sa * S > N:
                continue
            B = (N - (ga * G + sa * S)) // ba
            tmp_ans = (N - (ga + G + sa * S + ba * B))
            tmp_ans += (G * gb) + (S * sb) + (B * bb)
            ans = max(ans, tmp_ans)

elif (ga < gb) and (sa < sb) and (ba >= bb):
    for G in range(5001):
        for S in range(5001):
            if ga * G + sa * S > N:
                continue
            tmp_ans = (N - (ga + G + sa * S))

            NB = tmp_ans // bb
            tmp_ans = tmp_ans % bb

            tmp_ans += (G * gb) + (S * sb) + (NB * ba)
            ans = max(ans, tmp_ans)

elif (ga < gb) and (sa >= sb) and (ba < bb):
    for G in range(5001):
        for B in range(5001):
            if ga * G + ba * B > N:
                continue
            tmp_ans = (N - (ga + G + ba * B))

            NS = tmp_ans // sb
            tmp_ans = tmp_ans % sb

            tmp_ans += (G * gb) + (NS * sa) + (B * bb)
            ans = max(ans, tmp_ans)

elif (ga >= gb) and (sa < sb) and (ba < bb):
    for S in range(5001):
        for B in range(5001):
            if sa * S + ba * B > N:
                continue
            tmp_ans = (N - (sa + S + ba * B))

            NG = tmp_ans // gb
            tmp_ans = tmp_ans % gb

            tmp_ans += (NG * ga) + (S * sb) + (B * bb)
            ans = max(ans, tmp_ans)

elif (ga >= gb) and (sa >= sb) and (ba < bb):
    for B in range(5001):
        if ba * B > N:
            continue
        remain = (N - ba * B)
        for NG in range(5001):
            if NG * gb > remain:
                continue
            NS = (remain - NG * gb) // sb
            tmp_ans = remain % sb

            tmp_ans += (NG * ga) + (NS * sa) + (B * bb)
            ans = max(ans, tmp_ans)

elif (ga >= gb) and (sa < sb) and (ba >= bb):
    for S in range(5001):
        if sa * S > N:
            continue
        remain = (N - sa * S)
        for NG in range(5001):
            if NG * gb > remain:
                continue
            NB = (remain - NG * gb) // bb
            tmp_ans = remain % bb

            tmp_ans += (NG * ga) + (S * sb) + (NB * ba)
            ans = max(ans, tmp_ans)

elif (ga < gb) and (sa >= sb) and (ba >= bb):
    for G in range(5001):
        if ga * G > N:
            continue
        remain = (N - ga * G)
        for NS in range(5001):
            if NS * sb > remain:
                continue
            NB = (remain - NS * sb) // bb
            tmp_ans = remain % bb

            tmp_ans += (G * gb) + (NS * sa) + (NB * ba)
            ans = max(ans, tmp_ans)

else:
    for G in range(5001):
        for S in range(5001):
            if gb * G + sb * S > N:
                continue
            B = (N - (gb * G + sb * S)) // bb
            tmp_ans = (N - (gb + G + sb * S + bb * B))
            tmp_ans += (G * ga) + (S * sa) + (B * ba)
            ans = max(ans, tmp_ans)

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())

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
            if k > 0 and s > 0 and ja > 0:
                ans = max(ans, i*gmax + s*smax + ja* bmax)
    print(ans)

Submission status: Wrong Answer

Solution code:
# Enter your code here. Read input from STDIN. Print output to STDOUT

def find3(N,a,b,c,A,B,C):
    MAX=N
    for x in xrange(5001):
        for y in xrange(5001):
            temp=N-(a*x+b*y)
            if temp>=0:
                z=temp//c
                MAX=max(MAX,N-(a*x+b*y+c*z)+(A*x+B*y+C*z))
            else:
                break
    return MAX

def find2(N,a,b,A,B):
    MAX=N
    for x in xrange(5001):
        temp=N-a*x
        if temp>=0:
            y=temp//b
            MAX=max(MAX,N-(a*x+b*y)+(A*x+B*y))
    
    if (B-b)>(A-a):
        a,A,b,B=b,B,a,A 
    x=N//a 
    y=(N-a*x)//b 
    return max(MAX,N+(A-a)*x+(B-b)*y)
    

def find1(N,a,A):
    MAX=N
    num=N//a
    return N-num*a+num*A

N=int(raw_input())
X=list(map(int,raw_input().strip().split(' ')))
Y=list(map(int,raw_input().strip().split(' ')))

##stage1
index=[0]*3

for i in xrange(3):
    if X[i]<Y[i]:
        index[i]=1
post_1=[]
post_2=[]
for i in xrange(len(index)):
    if index[i]>0:
        post_1+=[i]    
    else:
        post_2+=[i]
number=sum(index)
if number==0:
    print(find3(N,Y[0],Y[1],Y[2],X[0],X[1],X[2]))
elif number==1:
    N=find1(N,X[post_1[0]],Y[post_1[0]])
    N=find2(N,Y[post_2[0]],Y[post_2[1]],X[post_2[0]],X[post_2[1]])
    print(N)
elif number==2:
    N=find2(N,X[post_1[0]],X[post_1[1]],Y[post_1[0]],Y[post_1[1]])
    N=find1(N,Y[post_2[0]],X[post_2[0]])
    print(N)
else:
    N=find3(N,X[0],X[1],X[2],Y[0],Y[1],Y[2])
    print(N)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())

def x(n,d,ans,b,a):
    while True:
        if max(d.values()) <= 1 or n < min(a):
            break
        maxkey = max(d, key=d.get)
        tmp = n // a[maxkey]
        ans += tmp * b[maxkey]
        n -= tmp * a[maxkey]
        d[maxkey] = 0
    return ans+n


n=int(input())
a=list(intinput())
b=list(intinput())
ba={i:b[i]/a[i] for i in range(3)}
ab={i:a[i]/b[i] for i in range(3)}
a_b=x(n,ba,0,b,a)
ans=x(a_b,ab,0,a,b)
print(ans)

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 * tmp[i][0] + 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 * tmp[i][1] + 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:
import itertools
N=int(input())
ga,sa,ba=[int(i) for i in input().split(" ")]
gb,sb,bb=[int(i) for i in input().split(" ")]
cmd=["getgold","paygold","getsilver","paysilver","getbronze","paybronze","fin"]
cmds=[]
for g in ("getgold","paygold","fin"):
    for s in ("getsilver","paysilver","fin"):
        for b in ("getbronze","paybronze","fin"):
            cmds.append((g,s,b))
            cmds.append((g,b,s))
            cmds.append((s,g,b))
            cmds.append((s,b,g))
            cmds.append((b,g,s))
            cmds.append((b,s,g))



def award(donguri,gold,silver,bronze,cmd,X):
    if X=="A":
        g,s,b=ga,sa,ba
    else:
        g,s,b=gb,sb,bb
    for c in cmd:
        if c=="fin":
            return donguri,gold,silver,bronze
        elif c=="getgold":
            gold+=donguri//g
            donguri=donguri%g
        elif c=="paygold":
            donguri+=gold*g
            gold=0
        elif c=="getsilver":
            silver+=donguri//s
            donguri=donguri%s
        elif c=="paysilver":
            donguri+=silver*s
            silver=0
        elif c=="getbronze":
            bronze+=donguri//b
            donguri=donguri%b
        elif c=="paybronze":
            donguri+=bronze*b
            bronze=0
    return donguri,gold,silver,bronze


retval=0
for cmd1 in cmds:
    for cmd2 in cmds:
        donguri=N
        gold=0
        silver=0
        bronze=0
        donguri,gold,silver,bronze=award(donguri,gold,silver,bronze,cmd1,"A")
        donguri,gold,silver,bronze=award(donguri,gold,silver,bronze,cmd2,"B")
        donguri+=ga*gold+sa*silver+ba*bronze
        retval=max(retval,donguri)

print(retval)

Submission status: Wrong Answer

Solution code:
n = int(input())
g = []
g0 = list(map(int, input().split()))
g1 = list(map(int, input().split()))
for i in range(3):
    g += [[g0[i], g1[i]]]

best = n

for i in range(3):
    for j in range(2):
        current_g = n // g[i][j]
        current_n = n % g[i][j]
        
        current_n += current_g * g[i][1-j]
        best = max(best, current_n)
print(best)

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]
    r = sorted(rate, key=lambda r: float(r[0]) / float(r[1]))[0]
    p = n - 500000
    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)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

def main():
    n = int(input())
    gsb_a = list(map(int, input().split(' ')))
    gsb_b = list(map(int, input().split(' ')))

    r = np.zeros([3], dtype=int)
    for i in range(len(r)):
        r[i] = get_don(n, i, gsb_a, gsb_b)
    print(np.max(r))

def get_don(dnum, t, gsb_a, gsb_b):
    can = dnum // gsb_a[t]
    if can == 0: return 0
    am = dnum % gsb_a[t]
    rate = gsb_b[t] / gsb_a[t]
    treaded = can * rate
    return treaded + max(get_don(am, 0, gsb_a, gsb_b), get_don(am, 1, gsb_a, gsb_b), get_don(am, 2, gsb_a, gsb_b))

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 = tmp

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][0]-downs[0][1]
        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][0]-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())
ca = list(map(int,input().split()))
cb = list(map(int,input().split()))

ab = [a-b for a,b in zip(ca,cb)]
ba = [b-a for a,b in zip(ca,cb)] 

def cal(array,init):
    a,b,c = array
    if a <= 0:
        r0 = 0
    else:
        r0 = init // a
        init -= a*r0
    if b <= 0:
        r1 = 0
    else:
        r1 = init // b
        init -= b*r1
    if c <= 0:
        r2 = 0
    else:
        r2 = init // c
        init -= c*r2
    res = 0
    for k in range(r0+1):
        for l in range(r1+1):
            for m in range(r2+1):
                score = k*a + l*b + m*c
                if score > res:
                    res = score

    global N
    N += res

cal(ba,N)
cal(ab,N)

print(N)

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()))+[1]
    prices_b=list(map(int,inp().split()))+[1]
    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)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
gsb_A = LIST()
gsb_B = LIST()
gsb_delta = {}
for i in range(3):
		if min(gsb_A[i], gsb_B[i]) in gsb_delta:
			gsb_delta[min(gsb_A[i], gsb_B[i])] = max(max(gsb_A[i], gsb_B[i]), gsb_delta[min(gsb_A[i], gsb_B[i])])
		else:
			gsb_delta[min(gsb_A[i], gsb_B[i])] = max(gsb_A[i], gsb_B[i])
# print(gsb_delta)
if N < min(gsb_delta.values()):
	print(N)
else:
	dp = [0] * (N+1)
	for i in range(N+1):
		for j in gsb_delta:
			if i-j >= 0:
				dp[i] = max(dp[i], dp[i-j] + gsb_delta[j])
	# print(dp)
	print(dp[N])

Submission status: Wrong Answer

Solution code:
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=0
        
        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=0

        t=N//ga
        for i in range(t+1):
            M=i*gb
            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))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
res = n
for x in range(n + 1):
    for y in range(n - x + 1):
        z = n - x - y
        ans = 0
        ans += (x // a[0]) * b[0]
        ans += (y // a[1]) * b[1]
        ans += (z // a[2]) * b[2]
        res = max(res, ans)
n = res
a, b = b, a
for x in range(n + 1):
    for y in range(n - x + 1):
        z = n - x - y
        ans = 0
        ans += (x // a[0]) * b[0]
        ans += (y // a[1]) * b[1]
        ans += (z // a[2]) * b[2]
        res = max(res, ans)
print(res)

Submission status: Wrong Answer

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

g_ratio = gb / ga
s_ratio = sb / sa
b_ratio = bb / ba

lst = []
lst.append([0, ga, g_ratio])
lst.append([1, sa, s_ratio])
lst.append([2, ba, b_ratio])

lst2 = sorted(lst, key=lambda x:-x[2])
outs = [0, 0, 0]
n = N
for i in range(3):
    #print(lst2[i])
    a0 = lst2[i][1]
    ratio0 = lst2[i][2]
    n0 = (n // a0) * a0
    #print(n0, a0)
    n -= n0
    outs[i] = int(n0 * ratio0)
out = sum(outs)
print(out)

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)
    tmp=N
    tmp=times(tmp,b[seq[1]],a[seq[1]])
    ans=max(ans,tmp)
    tmp=N
    tmp=times(tmp,a[seq[0]],b[seq[0]])
    ans=max(ans,tmp)
    
print(ans)

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 (n // ga - 1) > 0 and 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 (n // sa - 1) > 0 and 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 (n // ba - 1) > 0 and 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 (a_result // gb - 1) > 0 and 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 (a_result // sb - 1) > 0 and 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 (a_result // bb - 1) > 0 and 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())
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][0]-downs[0][1]
        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][0]-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)