Problem:


Score : 400 points

Problem Statement

Dolphin is planning to generate a small amount of a certain chemical substance C.

In order to generate the substance C, he must prepare a solution which is a mixture of two substances A and B in the ratio of M_a:M_b.

He does not have any stock of chemicals, however, so he will purchase some chemicals at a local pharmacy.

The pharmacy sells N kinds of chemicals. For each kind of chemical, there is exactly one package of that chemical in stock.

The package of chemical i contains a_i grams of the substance A and b_i grams of the substance B, and is sold for c_i yen (the currency of Japan).

Dolphin will purchase some of these packages. For some reason, he must use all contents of the purchased packages to generate the substance C.

Find the minimum amount of money required to generate the substance C.

If it is not possible to generate the substance C by purchasing any combination of packages at the pharmacy, report that fact.  

Constraints

1≦N≦40 

1≦a_i,b_i≦10 

1≦c_i≦100 

1≦M_a,M_b≦10 

gcd(M_a,M_b)=1

a_i, b_i, c_i, M_a and M_b are integers.

Input

The input is given from Standard Input in the following format:

N M_a M_b  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_N b_N c_N  

Output

Print the minimum amount of money required to generate the substance C. If it is not possible to generate the substance C, print -1 instead.

Sample Input 1

3 1 1
1 2 1
2 1 2
3 3 10

Sample Output 1

3

The amount of money spent will be minimized by purchasing the packages of chemicals 1 and 2.

In this case, the mixture of the purchased chemicals will contain 3 grams of the substance A and 3 grams of the substance B, which are in the desired ratio: 3:3=1:1.

The total price of these packages is 3 yen.  

Sample Input 2

1 1 10
10 10 10

Sample Output 2

-1

The ratio 1:10 of the two substances A and B cannot be satisfied by purchasing any combination of the packages. Thus, the output should be -1.



Sample input:
3 1 1
1 2 1
2 1 2
3 3 10


Sample output:
3

Submission status: Wrong Answer

Solution code:
N, Ma, Mb = map(int, input().split())
A = [0]*N
B = [0]*N
C = [0]*N

for i in range(N):
    A[i], B[i], C[i] = map(int, input().split())

# print(N, Ma, Mb, A, B, C)

A = [Mb * a for a in A]
B = [Ma * b for b in B]
D = []
for i in range(N):
    D.append((A[i] - B[i], C[i]))
# print(N, Ma, Mb, A, B, C, D)

Dp = []
Dn = []
Dz = []
for d in D:
    if d[0] == 0:
        Dz.append(d)
    elif d[0] > 0:
        Dp.append(d)
    else:
        Dn.append(d)

Dp.sort(key=lambda x: x[0])
Dn.sort(key=lambda x: x[0])
Dz.sort(key=lambda x: x[1])
min_c = 100*41
if len(Dz) > 0:
    min_c = Dz[0][1]
# print(Dp, Dn, Dz, min_c)

Ds = []
Dl = []
if len(Dp) < len(Dn):
    Ds, Dl = Dp, Dn
else:
    Ds, Dl = Dn, Dp

if len(Ds) == 0:
    if min_c == 100*41:
        print(-1)
    else:
        print(min_c)
    exit()

def calc(D, l):
    s = 0
    c = 0
    for i in range(len(D)):
        if (l >> i) & 1 != 0:
            s += D[i][0]
            c += D[i][1]
    return (s, c)

Ls = len(Ds)
Ll = len(Dl)
Ds_memo = []
Dl_memo = []

for ls in range(1 << (Ls - 1)):
    Ds_memo.append(calc(Ds, ls + 1))
for ll in range(1 << (Ll - 1)):
    Dl_memo.append(calc(Dl, ll + 1))

Ds_memo.sort(key=lambda x: x[1])
Dl_memo.sort(key=lambda x: x[0])

# print(Ds_memo, Dl_memo)

for ls in Ds_memo:
    s = ls[0]
    c = ls[1]
    # print('ls', ls, s, c)
    if c >= min_c:
        break
    for ll in Dl_memo:
        sl = ll[0]
        cl = ll[1]
        # print('ll', ll, sl, cl)
        if abs(s) < abs(sl):
            break
        if c + cl >= min_c:
            continue
        if s + sl == 0 and c + cl < min_c:
            min_c = c + cl

if min_c == 100*41:
    print(-1)
else:
    print(min_c)

Submission status: Wrong Answer

Solution code:
N, Ma, Mb = map(int, input().split())
A = [0]*N
B = [0]*N
C = [0]*N

for i in range(N):
    A[i], B[i], C[i] = map(int, input().split())

# print(N, Ma, Mb, A, B, C)

A = [Mb * a for a in A]
B = [Ma * b for b in B]
D = []
for i in range(N):
    D.append((A[i] - B[i], C[i]))
# print(N, Ma, Mb, A, B, C, D)

Dp = []
Dn = []
Dz = []
for d in D:
    if d[0] == 0:
        Dz.append(d)
    elif d[0] > 0:
        Dp.append(d)
    else:
        Dn.append(d)

Dp.sort(key=lambda x: x[0])
Dn.sort(key=lambda x: x[0])
Dz.sort(key=lambda x: x[1])
min_c = 100*41
if len(Dz) > 0:
    min_c = Dz[0][1]
# print(Dp, Dn, Dz, min_c)

Ds = []
Dl = []
if len(Dp) < len(Dn):
    Ds, Dl = Dp, Dn
else:
    Ds, Dl = Dn, Dp

if len(Ds) == 0:
    if min_c == 100*41:
        print(-1)
    else:
        print(min_c)
    exit()

def calc(D, l):
    s = 0
    c = 0
    for i in range(len(D)):
        if (l >> i) & 1 != 0:
            s += D[i][0]
            c += D[i][1]
    return (s, c)

Ls = len(Ds)
Ll = len(Dl)
Ds_memo = []
Dl_memo = []

for ls in range(1 << (Ls - 1)):
    Ds_memo.append(calc(Ds, ls + 1))
for ll in range(1 << (Ll - 1)):
    Dl_memo.append(calc(Dl, ll + 1))

Ds_memo.sort(key=lambda x: x[0])
Dl_memo.sort(key=lambda x: x[0])

# print(Ds_memo, Dl_memo)

for ls in Ds_memo:
    s = ls[0]
    c = ls[1]
    # print('ls', ls, s, c)
    if c >= min_c:
        break
    for ll in Dl_memo:
        sl = ll[0]
        cl = ll[1]
        # print('ll', ll, sl, cl)
        if c + cl >= min_c:
            break
        if abs(s) < abs(sl):
            break
        if s + sl == 0:
            min_c = c + cl
            break

if min_c == 100*41:
    print(-1)
else:
    print(min_c)

Submission status: Wrong Answer

Solution code:
N, Ma, Mb = map(int, input().split())
A = [0]*N
B = [0]*N
C = [0]*N

for i in range(N):
    A[i], B[i], C[i] = map(int, input().split())

# print(N, Ma, Mb, A, B, C)

A = [Mb * a for a in A]
B = [Ma * b for b in B]
D = []
for i in range(N):
    D.append((A[i] - B[i], C[i]))
# print(N, Ma, Mb, A, B, C, D)

Dp = []
Dn = []
Dz = []
for d in D:
    if d[0] == 0:
        Dz.append(d)
    elif d[0] > 0:
        Dp.append(d)
    else:
        Dn.append(d)

Dp.sort(key=lambda x: x[0])
Dn.sort(key=lambda x: x[0])
Dz.sort(key=lambda x: x[1])
min_c = 100*41
if len(Dz) > 0:
    min_c = Dz[0][1]
# print(Dp, Dn, Dz, min_c)

Ds = []
Dl = []
if len(Dp) < len(Dn):
    Ds, Dl = Dp, Dn
else:
    Ds, Dl = Dn, Dp

if len(Ds) == 0:
    if min_c == 100*41:
        print(-1)
    else:
        print(min_c)
    exit()

def calc(D, l):
    s = 0
    c = 0
    for i in range(len(D)):
        if (l >> i) & 1 != 0:
            s += D[i][0]
            c += D[i][1]
    return (s, c)

Ls = len(Ds)
Ll = len(Dl)
Ds_memo = []
Dl_memo = []

for ls in range(1 << (Ls - 1)):
    Ds_memo.append(calc(Ds, ls + 1))
for ll in range(1 << (Ll - 1)):
    Dl_memo.append(calc(Dl, ll + 1))

Ds_memo.sort(key=lambda x: x[1])
Dl_memo.sort(key=lambda x: x[1])

for ls in Ds_memo:
    s = ls[0]
    c = ls[1]
    if c >= min_c:
        break
    for ll in Dl_memo:
        sl = ll[0]
        cl = ll[1]
        # print('ll', ll, sl, cl)
        if c + cl >= min_c:
            break
        if s + sl == 0:
            min_c = c + cl
            break

if min_c == 100*41:
    print(-1)
else:
    print(min_c)

Submission status: Wrong Answer

Solution code:
N, Ma, Mb = map(int, input().split())
A = [0]*N
B = [0]*N
C = [0]*N

for i in range(N):
    A[i], B[i], C[i] = map(int, input().split())

# print(N, Ma, Mb, A, B, C)

A = [Mb * a for a in A]
B = [Ma * b for b in B]
D = []
for i in range(N):
    D.append((A[i] - B[i], C[i]))
# print(N, Ma, Mb, A, B, C, D)

Dp = []
Dn = []
Dz = []
for d in D:
    if d[0] == 0:
        Dz.append(d)
    elif d[0] > 0:
        Dp.append(d)
    else:
        Dn.append(d)

Dp.sort(key=lambda x: x[0])
Dn.sort(key=lambda x: x[0])
Dz.sort(key=lambda x: x[1])
min_c = 100*41
if len(Dz) > 0:
    min_c = Dz[0][1]
# print(Dp, Dn, Dz, min_c)

Ds = []
Dl = []
if len(Dp) < len(Dn):
    Ds, Dl = Dp, Dn
else:
    Ds, Dl = Dn, Dp

if len(Ds) == 0:
    if min_c == 100*41:
        print(-1)
    else:
        print(min_c)
    exit()

def calc(D, l):
    s = 0
    c = 0
    for i in range(len(D)):
        if (l >> i) & 1 != 0:
            s += D[i][0]
            c += D[i][1]
    return (s, c)

Ls = len(Ds)
Ll = len(Dl)
Ds_memo = []
Dl_memo = []

for ls in range(1 << (Ls - 1)):
    Ds_memo.append(calc(Ds, ls + 1))
for ll in range(1 << (Ll - 1)):
    Dl_memo.append(calc(Dl, ll + 1))

Ds_memo.sort(key=lambda x: x[1])
Dl_memo.sort(key=lambda x: x[1])

for ls in Ds_memo:
    s = ls[0]
    c = ls[1]
    if c >= min_c:
        break
    for ll in Dl_memo:
        sl = ll[0]
        cl = ll[1]
        # print('ll', ll, sl, cl)
        if c + cl >= min_c:
            break
        if s + sl == 0:
            min_c = c + cl

if min_c == 100*41:
    print(-1)
else:
    print(min_c)

Submission status: Wrong Answer

Solution code:
N, Ma, Mb = map(int, input().split())
A = [0]*N
B = [0]*N
C = [0]*N

for i in range(N):
    A[i], B[i], C[i] = map(int, input().split())

# print(N, Ma, Mb, A, B, C)

A = [Mb * a for a in A]
B = [Ma * b for b in B]
D = []
for i in range(N):
    D.append((A[i] - B[i], C[i]))
# print(N, Ma, Mb, A, B, C, D)

Dp = []
Dn = []
Dz = []
for d in D:
    if d[0] == 0:
        Dz.append(d)
    elif d[0] > 0:
        Dp.append(d)
    else:
        Dn.append(d)

Dp.sort(key=lambda x: x[0])
Dn.sort(key=lambda x: x[0])
Dz.sort(key=lambda x: x[1])
min_c = 100*41
if len(Dz) > 0:
    min_c = Dz[0][1]
# print(Dp, Dn, Dz, min_c)

Ds = []
Dl = []
if len(Dp) < len(Dn):
    Ds, Dl = Dp, Dn
else:
    Ds, Dl = Dn, Dp

if len(Ds) == 0:
    if min_c == 100*41:
        print(-1)
    else:
        print(min_c)
    exit()

def calc(D, l):
    s = 0
    c = 0
    for i in range(len(D)):
        if (l >> i) & 1 != 0:
            s += D[i][0]
            c += D[i][1]
    return s, c

Ls = len(Ds)
Ll = len(Dl)
for ls in range(1 << (Ls - 1)):
    s, c = calc(Ds, ls + 1)
    # print('ls', ls, s, c)
    if c >= min_c:
        continue
    for ll in range(1 << (Ll - 1)):
        sl, cl = calc(Dl, ll + 1)
        # print('ll', ll, sl, cl)
        if c >= min_c:
            continue
        if s + sl == 0:
            min_c = c + cl

if min_c == 100*41:
    print(-1)
else:
    print(min_c)

Submission status: Wrong Answer

Solution code:
N, Ma, Mb = map(int, input().split())
A = [0]*N
B = [0]*N
C = [0]*N

for i in range(N):
    A[i], B[i], C[i] = map(int, input().split())

# print(N, Ma, Mb, A, B, C)

A = [Mb * a for a in A]
B = [Ma * b for b in B]
D = []
for i in range(N):
    D.append((A[i] - B[i], C[i]))
# print(N, Ma, Mb, A, B, C, D)

Dp = []
Dn = []
Dz = []
for d in D:
    if d[0] == 0:
        Dz.append(d)
    elif d[0] > 0:
        Dp.append(d)
    else:
        Dn.append(d)

Dp.sort(key=lambda x: x[0])
Dn.sort(key=lambda x: x[0])
Dz.sort(key=lambda x: x[1])
min_c = 100*41
if len(Dz) > 0:
    min_c = Dz[0][1]
# print(Dp, Dn, Dz, min_c)

Ds = []
Dl = []
if len(Dp) < len(Dn):
    Ds, Dl = Dp, Dn
else:
    Ds, Dl = Dn, Dp

def calc(D, l):
    s = 0
    c = 0
    for i in range(len(D)):
        if (l >> i) & 1 != 0:
            s += D[i][0]
            c += D[i][1]
    return s, c

Ls = len(Ds)
Ll = len(Dl)
for ls in range(Ls):
    s, c = calc(Ds, ls + 1)
    # print('ls', ls, s, c)
    if c >= min_c:
        continue
    for ll in range(Ll):
        sl, cl = calc(Dl, ll + 1)
        # print('ll', ll, sl, cl)
        if c >= min_c:
            continue
        if s + sl == 0:
            min_c = c + cl

if min_c == 100*41:
    print(-1)
else:
    print(min_c)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
N,Ma,Mb = map(int,input().split())
abc = [list(map(int,input().split())) for _ in range(N)]
dp = [[INF]*(10*N+11) for _ in range(10*N+11)]
dp[0][0] = 0

for i in range(N):
    for a1 in range(10*N+1):
        for b1 in range(10*N+1):
            a,b,c = abc[i]
            dp[a1][b1] = min(dp[a1][b1],dp[a1-a][b1-b]+c)

ans = INF
for a1 in range(1,10*N+1):
    for b1 in range(1,10*N+1):
        if a1*Mb == b1*Ma:
            ans = min(ans,dp[a1][b1])

if ans == INF:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
"""
13:56
"""
import os
import sys
from collections import defaultdict
from fractions import Fraction

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, MA, MB = list(map(int, sys.stdin.readline().split()))
A, B, C = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

A = np.array(A)
B = np.array(B)
C = np.array(C)

# 1から10までのLCM
LCM = 2520

# 全部整数にしちゃう
M = MA * LCM // MB
W = A * LCM // B

# diffs をいくつか選んで積が 0 になれば平均が M
diffs = [Fraction(int(w), int(M)) for w in W]

ans = INF
dp = defaultdict(lambda: INF)
dp[M] = 0
for diff, cost in zip(diffs, C):
    for k, v in list(dp.items()):
        dp[k * diff] = min(dp[k * diff], dp[k] + cost)
        if k * diff == M:
            ans = min(ans, dp[k] + cost)
if ans < INF:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n,ma,mb=map(int,input().split())
A=[]
for i in range(n):
  a,b,c=map(int,input().split())
  A.append([a,b,c])
DP=[[[float("inf")]*(10*n+1) for _ in range(10*n+1)] for _ in range(n+1)]
DP[0][0][0]=0
for i in range(n):
  a,b,c=A[i][0],A[i][1],A[i][2]
  for j in range(10*n+1):
    for k in range(10*n+1):
      if j>=a and k>=b:
        DP[i+1][j][k]=min(DP[i][j-a][k-b]+c,DP[i][j][k])
ans=float("inf")
for i in range(10*n+1):
  for j in range(10*n+1):
    if i*mb==j*ma and i*j!=0:
      ans=min(ans,DP[n][i][j])
print(ans if ans!=float("inf") else -1)

Submission status: Wrong Answer

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

item=[]
for i in range(N):
    a,b,c = list(map(int,input().split()))
    item.append([a,b,c])

D = [[10**27 for i in range(401)] for j in range(401)]
D[0][0] = 0
for i in range(N):
    for j in range(401):
        for k in range(401):
            if j+item[i][0]<=400 and k+item[i][1]<=400:
                D[j+item[i][0]][k+item[i][1]] = min(D[j+item[i][0]][k+item[i][1]],D[j][k]+item[i][2])

i=1
min_cost=10**27
while A*i<=400 and B*i<=400:
    min_cost = min(D[A*i][B*i],min_cost)
    i+=1
if min_cost==10**27:
	print(-1)
else:
	print(min_cost)

Submission status: Wrong Answer

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

item=[]
for i in range(N):
    a,b,c = list(map(int,input().split()))
    item.append([a,b,c])

D = [[10**27 for i in range(401)] for j in range(401)]
D[0][0] = 0
for i in range(N):
    for j in range(400):
        for k in range(400):
            if j+item[i][0]<=400 and k+item[i][1]<=400:
                D[j+item[i][0]][k+item[i][1]] = min(D[j+item[i][0]][k+item[i][1]],D[j][k]+item[i][2])

i=1
min_cost=10**27
while A*i<=400 and B*i<=400:
    min_cost = min(D[A*i][B*i],min_cost)
    i+=1
if min_cost==10**27:
	print(-1)
else:
	print(min_cost)

Submission status: Wrong Answer

Solution code:
N,Ma,Mb=map(int,input().split())
abc=[]
INF=float("inf")
for i in range(N):
    a,b,c=map(int,input().split())
    abc.append((a,b,c))
stack=set([(0,0)])
dp=[[INF]*401 for i in range(401)]
dp[0][0]=0
for i in range(N):
    a,b,c=abc[i]
    stack_=set()
    for x,y in stack:
        dp[x+a][y+b]=min(dp[x+a][y+b],dp[x][y]+c)
        stack_.add((x+a,y+b))
        stack_.add((x,y))
    stack=stack_
k=1
ans=INF
while(Ma*k<=400 and Mb*k<=400):
    ans=min(dp[Ma*k][Mb*k],ans)
    k+=1
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N,Ma,Mb = map(int,input().split())
abc = []
for i in range(N):
    abc.append(list(map(int,input().split())))


dp = [  [ [float("inf") for ___ in range(500)] for __ in range(500) ]  for _ in range(N+1)]





dp[0][0][0] = 0
for i in range(N):
    for j in range(401):
        for k in range(401):
            if dp[i][j][k] == float("inf"):
                continue
            dp[i+1][j][k] = min(dp[i+1][j][k] , dp[i][j][k])
            dp[i+1][j+abc[i][0]][k+abc[i][1]] = min(dp[i+1][j+abc[i][0]][k+abc[i][1]] , dp[i][j][k]+abc[i][2])

ans = float("inf")
for j in range(1,500):
    for  k in range(1,500):
        if Ma*k == Mb*j:
            ans = min(ans , dp[N][k][j])
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
inf = float('inf')

N, Ma, Mb = map(int, input().split())
dp = [[inf] * (400 + 1) for _ in range(400 + 1)]
dp[0][0] = 0

max_a = 0
max_b = 0
for i in range(N):
    a, b, c = map(int, input().split())
    max_a += a
    max_b += b
    for j in range(max_a + 1 - a):
        for k in range(max_b + 1 - b):
            if dp[j][k] == inf: continue
            dp[j + a][k + b] = min(dp[j][k] + c, dp[j + a][k + b])

j = Ma
k = Mb
ans = inf
while j < 400 + 1 and k < 400 + 1:
    ans = min(ans, dp[j][k])
    j += Ma
    k += Mb

print(-1 if ans == inf else ans)
# print(dp)

Submission status: Wrong Answer

Solution code:
inf = float('inf')

N, Ma, Mb = map(int, input().split())
dp = [[inf] * (400 + 1) for _ in range(400 + 1)]
dp[0][0] = 0

max_a = 0
max_b = 0
for i in range(N):
    a, b, c = map(int, input().split())
    max_a += a
    max_b += b
    for j in range(max_a + 1 - a):
        for k in range(max_b + 1 - b):
            # if dp[j][k] == inf: continue
            dp[j + a][k + b] = min(dp[j][k] + c, dp[j + a][k + b])

j = Ma
k = Mb
ans = inf
while j < 400 + 1 and k < 400 + 1:
    ans = min(ans, dp[j][k])
    j += Ma
    k += Mb

print(-1 if ans == inf else ans)
# print(dp)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(2*10**5)

# 入力
N, Ma, Mb = map(int, input().split())
a, b, c = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), ())
)


# タイプAがxグラム, タイプBがyグラムの物質の最小生成コストを動的計画法により求める
@lru_cache(maxsize=None)
def f(x, y):
    return (
        10**18 if x < 0 or y < 0 else
        0 if x == 0 and y == 0 else
        min(f(x - u, y - v) + w for u, v, w in zip(a, b, c))
    )


# タイプAとタイプBの物質の比率がMa:Mbとなるような物質の最小コストを求める
opt = min(
    f(x, y)
    for x in range(1, sum(a) + 1) for y in range(1, sum(b) + 1)
    if x * Mb == y * Ma
)
ans = (
    opt if opt < 10**18 else
    -1
)

# 出力
print(ans)

Submission status: Wrong Answer

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


def solve(N: int, M_a: int, M_b: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    c_max = 100
    a_max = 10
    total_max = (N+1) * a_max

    t = np.full((N+1, total_max + 1, total_max + 1), c_max * N, dtype=int)
    t[0][0][0] = 0

    for i in range(N):
        t[i+1] = t[i]
        cheaper = t[i, a[i]:, b[i]:] > t[i, :-a[i], :-b[i]] + c[i]
        t[i+1, a[i]:, b[i]:] = np.where(cheaper, t[i, :-a[i], :-b[i]] + c[i], t[i, a[i]:, b[i]:])
    
    t_a, t_b = M_a, M_b
    cheapest = c_max * N
    while t_a <= total_max and t_b <= total_max:
        total = t[N][t_a][t_b]
        if total < cheapest:
            cheapest = total
        t_a += M_a
        t_b += M_b
    print(cheapest)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    M_a = int(next(tokens))  # type: int
    M_b = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]" 
    b = [int()] * (N)  # type: "List[int]" 
    c = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M_a, M_b, a, b, c)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from collections import deque

N,A,B = map(int,input().split())
info = [list(map(int,input().split())) for _ in range(N)]

d = dict()

def bfs():
    dq = deque()
    a,b,cost,depth = 0,0,0,0
    dq.append((a,b,cost,depth))
    while dq:
        a,b,cost,depth = dq.popleft()
        if depth == N:
            continue
        na,nb = a + info[depth][0],b + info[depth][1]
        G = gcd(na,nb)
        na //= G
        nb //= G
        new_cost = cost + info[depth][2]
        pre_cost = d.get((na,nb))
        if pre_cost is None:
            d[(na,nb)] = new_cost
        elif pre_cost < new_cost:
            continue
        else:
            d[(na,nb)] = new_cost
        dq.append((a,b,cost,depth+1))
        dq.append((na,nb,new_cost,depth+1))

bfs()

ans = d.get((A,B))

if ans is None:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

N,A,B = map(int,input().split())
info = [list(map(int,input().split())) for _ in range(N)]

d = dict()

def bfs(ratio=(0, 0),depth=0,cost=0):
    if depth == N:
        return
    a, b = ratio
    new_ratio = (a + info[depth][0], b + info[depth][1])
    na, nb = new_ratio
    G = gcd(na,nb)
    new_ratio = (na//G, nb//G)
    new_cost = cost + info[depth][2]
    pre_cost = d.get(new_ratio)
    if pre_cost is None:
        d[new_ratio] = new_cost
    elif pre_cost < new_cost:
        return
    else:
        d[new_ratio] = new_cost
    bfs(ratio,depth+1,cost)
    bfs(new_ratio,depth+1,new_cost)
    
bfs()

ans = d.get((A,B))
if ans is None:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
n, ma, mb = map(int,input().split())
INF = 1000000
abmax = 10
nmax = 40
medi = []
sumb = 0
suma = 0
for i in range(n):
    a, b, c = map(int,input().split())
    suma += a
    sumb += b
    medi.append([a,b,c])
dp = [[[INF for k in range(nmax*abmax+1)] for j in range(nmax*abmax+1)] for i in range(nmax+1)]
dp[0][0][0] = 0
for i in range(n):
    for x in range(suma+1):
        for y in range(sumb+1):
            if dp[i][x][y] == INF:
                continue
            dp[i + 1][x][y] = min(dp[i + 1][x][y], dp[i][x][y])
            a, b, c = medi[i]
            if x + a <= abmax and y + b <= abmax:
                dp[i + 1][x + a][y + b] = min(dp[i][x][y] + c, dp[i + 1][x + a][y + b])

t = 1
ok = False
ans = INF
for ca in range(1,nmax*abmax+1):
    for cb in range(1,nmax*abmax+1):
        if ma*cb == mb*ca:
            ans = min(ans, dp[n][ca][cb])
    
print(ans if ans != INF else -1)

Submission status: Wrong Answer

Solution code:
n, ma, mb = map(int,input().split())
INF = 1000000
abmax = 10
nmax = 40
medi = []
for i in range(n):
    a, b, c = map(int,input().split())
    medi.append([a,b,c])
dp = [[[INF for k in range(nmax*abmax+1)] for j in range(nmax*abmax+1)] for i in range(nmax+1)]
dp[0][0][0] = 0
for i in range(n):
    for x in range(nmax*abmax+1):
        for y in range(nmax*abmax+1):
            if dp[i][x][y] == INF:
                continue
            dp[i + 1][x][y] = min(dp[i + 1][x][y], dp[i][x][y])
            a, b, c = medi[i]
            if x + a <= abmax and y + b <= abmax:
                dp[i + 1][x + a][y + b] = min(dp[i][x][y] + c, dp[i + 1][x + a][y + b])

t = 1
ok = False
ans = INF
for ca in range(1,nmax*abmax+1):
    for cb in range(1,nmax*abmax+1):
        if ma*cb == mb*ca:
            ans = min(ans, dp[n][ca][cb])
    
print(ans if ans != INF else -1)

Submission status: Wrong Answer

Solution code:
n, ma, mb = map(int,input().split())
INF = 1000000
abmax = 10
nmax = 40
medi = []
for i in range(n):
    a, b, c = map(int,input().split())
    medi.append([a,b,c])
dp = [[[INF for k in range(nmax*abmax+1)] for j in range(nmax*abmax+1)] for i in range(nmax+1)]
dp[0][0][0] = 0
for i in range(n):
    for x in range(nmax*abmax+1):
        for y in range(nmax*abmax+1):
            if dp[i][x][y] == INF:
                continue
            dp[i + 1][x][y] = min(dp[i + 1][x][y], dp[i][x][y])
            a, b, c = medi[i]
            if x + a <= abmax and y + b <= abmax:
                dp[i + 1][x + a][y + b] = min(dp[i][x][y] + c, dp[i + 1][x + a][y + b])

t = 1
ok = False
ans = INF
for i in range(1,nmax*abmax+1):
    for j in range(1,nmax*abmax+1):
        if dp[n][i][j] < INF and ma*j == mb*i:
            ans = min(ans, dp[n][i][j])
    
print(ans if ans != INF else -1)

Submission status: Wrong Answer

Solution code:
n, ma, mb = map(int,input().split())
INF = 100000
abmax = 10
nmax = 40
medi = []
for i in range(n):
    a, b, c = map(int,input().split())
    medi.append([a,b,c])
dp = [[[INF for k in range(nmax*abmax+1)] for j in range(nmax*abmax+1)] for i in range(nmax+1)]
dp[0][0][0] = 0
for i in range(n):
    for x in range(nmax*abmax+1):
        for y in range(nmax*abmax+1):
            if dp[i][x][y] == INF:
                continue
            dp[i + 1][x][y] = min(dp[i + 1][x][y], dp[i][x][y])
            a, b, c = medi[i]
            if x + a <= abmax and y + b <= abmax:
                dp[i + 1][x + a][y + b] = min(dp[i][x][y] + c, dp[i + 1][x + a][y + b])

t = 1
ok = False
ans = INF
for i in range(1,nmax*abmax+1):
    for j in range(1,nmax*abmax+1):
        if dp[n][i][j] < INF and ma*j == mb*i:
            ans = min(ans, dp[n][i][j])
    
print(ans if ans != INF else -1)

Submission status: Wrong Answer

Solution code:
n, ma, mb = map(int,input().split())
INF = 100000
abmax = 10
nmax = 40
medi = []
for i in range(n):
    a, b, c = map(int,input().split())
    medi.append([a,b,c])
dp = [[[INF for k in range(nmax*abmax+1)] for j in range(nmax*abmax+1)] for i in range(n+1)]
dp[0][0][0] = 0
for i in range(n):
    for x in range(abmax+1):
        for y in range(abmax+1):
            if dp[i][x][y] == INF:
                continue
            dp[i + 1][x][y] = min(dp[i + 1][x][y], dp[i][x][y])
            a, b, c = medi[i]
            if x + a <= abmax and y + b <= abmax:
                dp[i + 1][x + a][y + b] = min(dp[i][x][y] + c, dp[i + 1][x + a][y + b])

t = 1
ok = False
ans = INF
for i in range(1,nmax*abmax+1):
    for j in range(1,nmax*abmax+1):
        if dp[n][i][j] < INF and ma*j == mb*i:
            ans = min(ans, dp[n][i][j])
    
print(ans if ans != INF else -1)

Submission status: Wrong Answer

Solution code:
n, ma, mb = map(int,input().split())
INF = 100000
maxa = 0
maxb = 0
maxc = 0
medi = []
for i in range(n):
    a, b, c = map(int,input().split())
    maxa = max(maxa, a)
    maxb = max(maxb, b)
    maxc = max(maxc, c)
    medi.append([a, b, c])
dp = [[[INF for k in range(n*maxb+1)] for j in range(n*maxa+1)] for i in range(n+1)]
dp[0][0][0] = 0
for i in range(n):
    for x in range(maxa+1):
        for y in range(maxb+1):
            if dp[i][x][y] == INF:
                continue
            dp[i + 1][x][y] = min(dp[i + 1][x][y], dp[i][x][y])
            a, b, c = medi[i]
            if x + a <= maxa and y + b <= maxb:
                dp[i + 1][x + a][y + b] = min(dp[i][x][y] + c, dp[i + 1][x + a][y + b])

t = 1
ok = False
ans = INF
for i in range(1,n*maxa+1):
    for j in range(1,n*maxb+1):
        if dp[n][i][j] < INF and ma*j == mb*i:
            ans = min(ans, dp[n][i][j])
    
print(ans if ans != INF else -1)

Submission status: Wrong Answer

Solution code:
n, ma, mb = map(int,input().split())
INF = 100000
maxa = 0
maxb = 0
maxc = 0
medi = []
for i in range(n):
    a, b, c = map(int,input().split())
    maxa = max(maxa, a)
    maxb = max(maxb, b)
    maxc = max(maxc, c)
    medi.append([a, b, c])
dp = [[[INF for k in range(maxb+1)] for j in range(maxa+1)] for i in range(n+1)]
dp[0][0][0] = 0
for i in range(n):
    for x in range(maxa+1):
        for y in range(maxb+1):
            if dp[i][x][y] == INF:
                continue
            dp[i + 1][x][y] = min(dp[i + 1][x][y], dp[i][x][y])
            a, b, c = medi[i]
            if x + a <= maxa and y + b <= maxb:
                dp[i + 1][x + a][y + b] = min(dp[i][x][y] + c, dp[i + 1][x + a][y + b])

t = 1
ok = False
ans = INF
for i in range(1,maxa+1):
    for j in range(1,maxb+1):
        if dp[n][i][j] < INF and ma*j == mb*i:
            ans = min(ans, dp[n][i][j])
    
print(ans if ans != INF else -1)

Submission status: Wrong Answer

Solution code:
n, ma, mb = map(int,input().split())
INF = 100000
maxa = 0
maxb = 0
maxc = 0
medi = []
for i in range(n):
    a, b, c = map(int,input().split())
    maxa = max(maxa, a)
    maxb = max(maxb, b)
    maxc = max(maxc, c)
    medi.append([a, b, c])
dp = [[[INF for k in range(maxb+1)] for j in range(maxa+1)] for i in range(n+1)]
dp[0][0][0] = 0
for i in range(n):
    for x in range(maxa+1):
        for y in range(maxb+1):
            if dp[i][x][y] == INF:
                continue
            dp[i + 1][x][y] = min(dp[i + 1][x][y], dp[i][x][y])
            a, b, c = medi[i]
            if x + a <= maxa and y + b <= maxb:
                dp[i + 1][x + a][y + b] = min(dp[i][x][y] + c, dp[i + 1][x + a][y + b])

t = 1
ok = False
ans = INF
for i in range(1,maxa+1):
    for j in range(1,maxb+1):
        if dp[n][i][j] < INF and ma*j == mb*i:
            ans = min(ans, dp[n][i][j])
            ok = True
    
print(ans if ok else -1)

Submission status: Wrong Answer

Solution code:
n, ma, mb = map(int,input().split())
INF = 10000
maxa = 0
maxb = 0
maxc = 0
medi = []
for i in range(n):
    a, b, c = map(int,input().split())
    maxa = max(maxa, a)
    maxb = max(maxb, b)
    maxc = max(maxc, c)
    medi.append([a, b, c])
dp = [[[INF for k in range(maxb+1)] for j in range(maxa+1)] for i in range(n+1)]
dp[0][0][0] = 0
for i in range(n):
    for x in range(maxa+1):
        for y in range(maxb+1):
            if dp[i][x][y] == INF:
                continue
            dp[i + 1][x][y] = min(dp[i + 1][x][y], dp[i][x][y])
            a, b, c = medi[i]
            if x + a <= maxa and y + b <= maxb:
                dp[i + 1][x + a][y + b] = min(dp[i][x][y] + c, dp[i + 1][x + a][y + b])

t = 1
ok = False
ans = INF
while t*ma <= maxa and t*mb <= maxb:
    if dp[n][t*ma][t*mb] < INF:
        ans = min(ans, dp[n][t*ma][t*mb])
        ok = True
    t += 1
    
print(ans if ok else -1)

Submission status: Wrong Answer

Solution code:
n, ma, mb = map(int,input().split())
INF = 10000
maxa = 0
maxb = 0
maxc = 0
medi = []
for i in range(n):
    a, b, c = map(int,input().split())
    maxa = max(maxa, a)
    maxb = max(maxb, b)
    maxc = max(maxc, c)
    medi.append([a, b, c])
dp = [[[INF for k in range(maxb+1)] for j in range(maxa+1)] for i in range(n+1)]
dp[0][0][0] = 0
for i in range(n):
    for x in range(maxa+1):
        for y in range(maxb+1):
            if dp[i][x][y] == INF:
                continue
            dp[i + 1][x][y] = min(dp[i + 1][x][y], dp[i][x][y])
            a, b, c = medi[i]
            if x + a <= maxa and y + b <= maxb:
                dp[i + 1][x + a][y + b] = min(dp[i][x][y] + c, dp[i + 1][x + a][y + b])

t = 1
ok = False
ans = INF
while t*ma <= maxa and t*mb <= maxb:
    print(t*ma,maxa,t*mb,maxb)
    if dp[n][t*ma][t*mb] < INF:
        ans = min(ans, dp[n][t*ma][t*mb])
        ok = True
    t += 1
    
print(ans if ok else -1)

Submission status: Wrong Answer

Solution code:
n, ma, mb = map(int,input().split())
INF = 10000
maxa = 0
maxb = 0
maxc = 0
medi = []
for i in range(n):
    a, b, c = map(int,input().split())
    maxa = max(maxa, a)
    maxb = max(maxb, b)
    maxc = max(maxc, c)
    medi.append([a, b, c])
dp = [[[INF for k in range(maxb+1)] for j in range(maxa+1)] for i in range(n+1)]
dp[0][0][0] = 0
for i in range(n):
    for x in range(maxa+1):
        for y in range(maxb+1):
            if dp[i][x][y] == INF:
                continue
            dp[i + 1][x][y] = min(dp[i + 1][x][y], dp[i][x][y])
            a, b, c = medi[i]
            if x + a <= maxa and y + b <= maxb:
                dp[i + 1][x + a][y + b] = min(dp[i][x][y] + c, dp[i + 1][x + a][y + b])

t = 1
ok = False
ans = INF
while t*ma <= maxa and t*mb <= maxb:
    if dp[n][t*ma][t*mb] < INF:
        ans = min(ans, dp[n][t*ma][t*mb])
        ok = True
        break
    else:
        t += 1
    
print(ans if ok else -1)