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:

from collections import defaultdict

N, Ma, Mb = map(int, input().split())

A,B,C = [0]*N,[0]*N,[0]*N

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

MAX = sum(C)+1

table = defaultdict(lambda: MAX)
table[(0,0)] = 0

for a,b,c in zip(A,B,C):
  
  content = list(table.keys())
  for e in content:
    ne = (e[0]+a, e[1]+b)
    table[ne] = min(table[ne], table[e] + c)

max_iter = min(sum(A)//Ma, sum(B)//Mb)

try:
  cost = min(table[(Ma*i,Mb*i)] for i in range(1,max_iter))
except ValueError:
  cost = MAX

if cost == MAX:
  print(-1)
else:
  print(cost)

Submission status: Wrong Answer

Solution code:
n, ma, mb = map(int, raw_input().split())
abc = []
suma = 1
sumb = 1

for i in range(n):
    a,b,c = map(int, raw_input().split())
    suma += a
    sumb += b
    abc.append((a,b,c))

dp = [ [ [float('inf')] * sumb for j in range(suma)] for i in range(n+1)]
for i in range(n+1):
    dp[i][0][0] = 0

for i in range(n):
    a,b,c = abc[i]
    for ai in range(suma):
        for bi in range(sumb):
            if ai - a >= 0 and bi - b >= 0:
                dp[i+1][ai][bi] = min(dp[i][ai][bi], dp[i+1][ai][bi], dp[i][ai-a][bi-b]+c)

ans = float('inf')
i = 1
while i*ma < suma and i*mb < sumb:
    ans = min(ans, dp[n][i*ma][i*mb])
    i += 1

if ans == float('inf'):
    print '-1'
else:
    print ans

Submission status: Wrong Answer

Solution code:
def checker(d, ds, p):
    if len(ds) == 0:
        return (False, 0)
    b = ds[0]
    d2 = d[:]
    # use b
    d[0] += b[0]
    d[1] += b[1]
    d[2] += b[2]
    c = 0
    res = False
    if d[0] / d[1] != p:
        res, c = checker(d, ds[1:], p)
    else:
        res = True
        c = d[2]
    # no use
    res2, c2 = checker(d2, ds[1:], p)

    if res and res2:
        if d[2] < d2[2]:
            return (True, c)
        else:
            return (True, c2)
    elif res:
        return (True, c)
    elif res2:
        return (True, c2)
    return (False, 0)


n = list(map(int, input().split()))

p = n[1] / n[2]
n = n[0]

ds = []
for i in range(0, n):
    ds.append(list(map(int, input().split())))

arg = [0, 0, 0]
res, c = checker(arg, ds, p)

if res:
    print(str(c))
else:
    print("-1")

Submission status: Wrong Answer

Solution code:
n, ma, mb = map(int, raw_input().split())
abc = []
suma = 1
sumb = 1

for i in range(n):
    a,b,c = map(int, raw_input().split())
    suma += a
    sumb += b
    abc.append((a,b,c))

dp = [ [ [float('inf')] * sumb for j in range(suma)] for i in range(n+1)]
dp[0][0][0] = 0

for i in range(n):
    a,b,c = abc[i]
    for ai in range(suma):
        for bi in range(sumb):
            if ai - a >= 0 and bi - b >= 0:
                dp[i+1][ai][bi] = min(dp[i][ai][bi], dp[i+1][ai][bi], dp[i][ai-a][bi-b]+c)

ans = float('inf')
i = 1
while i*ma < suma and i*mb < sumb:
    ans = min(ans, dp[n][i*ma][i*mb])
    i += 1

if ans == float('inf'):
    print '-1'
else:
    print ans

Submission status: Wrong Answer

Solution code:
n, ma, mb = map(int, raw_input().split())
abc = []
suma = 1
sumb = 1

for i in range(n):
    a,b,c = map(int, raw_input().split())
    suma += a
    sumb += b
    abc.append((a,b,c))

dp = [ [ [float('inf')] * sumb for j in range(suma)] for i in range(n+1)]
dp[0][0][0] = 0

for i in range(n):
    a,b,c = abc[i]
    for ai in range(suma):
        for bi in range(sumb):
            if ai - a >= 0 and bi - b >= 0:
                dp[i+1][ai][bi] = min(dp[i][ai][bi], dp[i][ai-a][bi-b]+c)

ans = float('inf')
i = 1
while i*ma < suma and i*mb < sumb:
    ans = min(ans, dp[n][i*ma][i*mb])
    i += 1

if ans == float('inf'):
    print '-1'
else:
    print ans

Submission status: Wrong Answer

Solution code:
n, ma, mb = map(int, raw_input().split())
abc = []
suma = 1
sumb = 1

for i in range(n):
    a,b,c = map(int, raw_input().split())
    suma += a
    sumb += b
    abc.append((a,b,c))

dp = [ [ [float('inf')] * sumb for j in range(suma)] for i in range(n+1)]
dp[0][0][0] = 0

for i in range(n):
    a,b,c = abc[i]
    for ai in range(suma):
        for bi in range(sumb):
            if ai - a >= 0 and bi - b >= 0:
                dp[i+1][ai][bi] = min(dp[i][ai][bi], dp[i][ai-a][bi-b]+c)

ans = float('inf')
i = 1
while i*ma < suma and i*mb < sumb:
    print i*ma, i*mb, dp[n][i*ma][i*mb]
    ans = min(ans, dp[n][i*ma][i*mb])
    i += 1

if ans == float('inf'):
    print '-1'
else:
    print ans

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from fractions import Fraction

INF = int(1e14)


def same_ratio(a1: int, b1: int, a2: int, b2: int):
    assert a1 > 0 and b1 > 0 and a2 > 0 and b2 > 0
    r = max(a1, a2) / min(a1, a2)
    return (a1 * r == a2 and b1 * r == b2) or (a1 == a2 * r and b1 == b2 * r)


def main():
    N, Ma, Mb = map(int, input().split())
    l = []
    for _ in range(N):
        l.append(tuple(map(int, input().split())))

    ans = INF
    dp = [[[INF] * 401 for i in range(401)] for j in range(N + 1)]
    dp[0][0][0] = 0

    max_a, max_b = 1, 1
    for i in range(N):

        for a in range(max_a, -1, -1):
            for b in range(max_b, -1, -1):
                if dp[i][a][b] != INF:
                    dp[i + 1][a + l[i][0]][b + l[i][1]] = min(dp[i + 1][a + l[i][0]][b + l[i][1]], dp[i][a][b] + l[i][2])
                    dp[i + 1][a][b] = min(dp[i + 1][a][b], dp[i][a][b])

                    max_a = max(max_a, a + l[i][0])
                    max_b = max(max_b, b + l[i][1])

                c = dp[i][a][b]
                if a != 0 and b != 0 and c < ans and same_ratio(a, b, Ma, Mb):
                    ans = min(ans, c)

    print((-1 if ans == INF else ans))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from fractions import Fraction

INF = 1e14


def same_ratio(a1: int, b1: int, a2: int, b2: int):
    assert a1 > 0 and b1 > 0 and a2 > 0 and b2 > 0
    r = max(a1, a2) / min(a1, a2)
    return (a1 * r == a2 and b1 * r == b2) or (a1 == a2 * r and b1 == b2 * r)



def main():
    N, Ma, Mb = map(int, input().split())
    l = []
    for _ in range(N):
        l.append(tuple(map(int, input().split())))

    ans = INF
    dp = [[[INF] * 401 for i in range(401)] for j in range(N + 1)]
    dp[0][0][0] = 0

    for i in range(N):

        for a in range(len(dp[0])):
            for b in range(len(dp[0][0])):
                if dp[i][a][b] != INF:
                    dp[i + 1][a + l[i][0]][b + l[i][1]] = min(dp[i + 1][a + l[i][0]][b + l[i][1]], dp[i][a][b] + l[i][2])
                    dp[i + 1][a][b] = min(dp[i + 1][a][b], dp[i][a][b])

                c = dp[i][a][b]
                if a != 0 and b != 0 and c < ans and same_ratio(a, b, Ma, Mb):
                    ans = min(ans, c)

    print((-1 if ans == INF else ans))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy

if __name__=="__main__":
    inputs_number  = lambda : [int(x) for x in input().split()]
    N, Ma, Mb = inputs_number()
    drugs = [inputs_number() for i in range(N)]
    inf = 100*N + 1
    dp = np.ones((2,N*10+1,N*10+1)).astype(np.int32) * inf
    dp = dp.tolist()
    dp[0][0][0] = 0.0

    for i in range(N):
        for ca in range(10*i+1):
            for cb in range(10*i+1):
                if(dp[0][ca][cb]==inf):
                    continue
                dp[1][ca][cb]=min([dp[1][ca][cb], dp[0][ca][cb]])
                dp[1][ca+drugs[i][0]][cb+drugs[i][1]]=min([dp[1][ca+drugs[i][0]][cb+drugs[i][1]], dp[0][ca][cb]+drugs[i][2]])
        dp[0] = copy.copy(dp[1])
        dp[1] = (np.ones((N*10+1,N*10+1)).astype(np.int32) * inf).tolist()
    print(np.array(dp).shape)
    ans = inf
    for ca in range(1, N*10+1):
        for cb in range(1, N*10+1):
            if(Ma*cb==Mb*ca and dp[0][ca][cb]<ans):
                ans = dp[0][ca][cb]
    if(ans==inf):
        ans = -1
    print(int(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np

if __name__=="__main__":
    inputs_number  = lambda : [int(x) for x in input().split()]
    N, Ma, Mb = inputs_number()
    drugs = [inputs_number() for i in range(N)]
    inf = 100*N + 1
    dp = np.ones((N+1,N*10+1,N*10+1)).astype(np.int32) * inf
    dp = dp.tolist()
    print(type(dp[0][0][0]))
    dp[0][0][0] = 0.0

    for i in range(N):
        for ca in range(N*10+1):
            for cb in range(N*10+1):
                if(dp[i][ca][cb]==inf):
                    continue
                dp[i+1][ca][cb]=min([dp[i+1][ca][cb], dp[i][ca][cb]])
                dp[i+1][ca+drugs[i][0]][cb+drugs[i][1]]=min([dp[i+1][ca+drugs[i][0]][cb+drugs[i][1]], dp[i][ca][cb]+drugs[i][2]])
    ans = inf
    for ca in range(1, N*10+1):
        for cb in range(1, N*10+1):
            if(Ma*cb==Mb*ca and dp[N][ca][cb]<ans):
                ans = dp[N][ca][cb]
    if(ans==inf):
        ans = -1
    print(int(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np

if __name__=="__main__":
    inputs_number  = lambda : [int(x) for x in input().split()]
    N, Ma, Mb = inputs_number()
    drugs = [inputs_number() for i in range(N)]
    inf = 100*N + 1
    dp = np.ones((N+1,N*10+1,N*10+1)) * inf
    dp[0,0,0] = 0.0

Submission status: Wrong Answer

Solution code:
import numpy as np

if __name__=="__main__":
    inputs_number  = lambda : [int(x) for x in input().split()]
    N, Ma, Mb = inputs_number()
    drugs = np.array([inputs_number() for i in range(N)])
    print(-1)

Submission status: Wrong Answer

Solution code:
n, ma, mb = input().split()
N = 500
n = int(n)
ma = int(ma)
mb = int(mb)

mat = []
for i in range(N):
  mat.append([])
  for j in range(N):
    mat[i].append(-1)
s = set()
s.add(0)
mat[0][0] = 0
for _ in range(n):
  a, b, c = input().split()
  a = int(a)
  b = int(b)
  c = int(c)
  ss = set()
  for x in s:
    i = x // N
    j = x % N
    cost = mat[i][j]
    i += a
    j += b
    if mat[i][j] == -1 or cost + c < mat[i][j]:
      ss.add(i * N + j)
      mat[i][j] = cost + c
  for x in ss:
    s.add(x)
costs = []
for i in range(1, N):
  aa = ma * i
  bb = mb * i
  if aa >= N or bb >= N:
    break
  cost = mat[aa][bb]
  if cost != -1:
    costs.append(cost)
if costs:
  print(min(costs))
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
N, MA, MB = map(int, raw_input().split())
X = [map(int, raw_input().split()) for _ in range(N)]

DP = [[100000 for _ in range(401)] for _ in range(401)]
DP[0][0] = 0

S = {(0, 0)}
for a, b, c in X:
    DP2 = DP[:]
    for sa, sb in S:
        if DP[sa+a][sb+b] > DP2[sa][sb] + c:
            DP[sa+a][sb+b] = DP2[sa][sb] + c
    T = {(sa+a, sb+b) for sa, sb in S}
    S |= T

a, b = MA, MB
ans = 100000
while a <= 400 and b <= 400:
    ans = min(ans, DP[a][b])
    a += MA
    b += MB

if ans == 100000:
    print -1
else:
    print ans

Submission status: Wrong Answer

Solution code:
n, ma, mb = input().split()
N = 500
n = int(n)
ma = int(ma)
mb = int(mb)

mat = []
for i in range(N):
  mat.append([])
  for j in range(N):
    mat[i].append(-1)
s = set() # 可能なi*401+jのリスト
s.add(0)
mat[0][0] = 0
for i in range(n):
  a, b, c = input().split()
  a = int(a)
  b = int(b)
  c = int(c)
  ss = set()
  for x in s:
    i = x // N
    j = x % N
    cost = mat[i][j]
    i += a
    j += b
    ss.add(i * N + j)
    if mat[i][j] == -1 or cost + c < mat[i][j]:
      mat[i][j] = cost + c
  for x in ss:
    s.add(x)
costs = []
for i in range(1, N):
  aa = ma * i
  bb = mb * i
  if aa >= N or bb >= N:
    break
  cost = mat[aa][bb]
  if cost != -1:
    costs.append(cost)
if costs:
  print(min(costs))
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
n, ma, mb = input().split()
n = int(n)
ma = int(ma)
mb = int(mb)

mat = []
for i in range(401):
  mat.append([])
  for j in range(401):
    mat[i].append(-1)
s = set() # 可能なi*401+jのリスト
s.add(0)
mat[0][0] = 0
for i in range(n):
  a, b, c = input().split()
  a = int(a)
  b = int(b)
  c = int(c)
  ss = set()
  for x in s:
    i = x // 401
    j = x % 401
    cost = mat[i][j]
    i += a
    j += b
    ss.add(i*401+j)
    if mat[i][j] == -1 or cost + c < mat[i][j]:
      mat[i][j] = cost + c
  for x in ss:
    s.add(x)
costs = []
for i in range(1, 401):
  aa = ma * i
  bb = mb * i
  if aa > 400 or bb > 400:
    break
  cost = mat[aa][bb]
  if cost != -1:
    costs.append(cost)
if costs:
  print(min(costs))
else:
  print(-1)

Submission status: Wrong Answer

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

def ratio(a, b):
    if a == 0 or b == 0:
        return False
    return a*Mb == Ma*b

budget = -1
def search(s, i, a, b):
    if i >= N:
        return
    global budget
    if s > budget and not budget == -1:
        return
    if ratio(a, b):
        budget = s
        return
    search(s+C[i], i+1, a+A[i], b+B[i])
    search(s, i+1, a, b)

search(0, 0, 0, 0)
print(budget)

Submission status: Wrong Answer

Solution code:
n, aa, bb = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(n) ]
print(lis)
ans = -1
for i in range(1,2**n):
    i = list(str(bin(i)))
    madea = 0
    madeb = 0
    c = 0
    for j in range(2,len(i)):
        if int(i[j]) == 1:
            madea = madea + lis[j-2][0]
            madeb = madeb + lis[j-2][1]
            c = c + lis[j-2][2]
    if madea*bb == madeb*aa and ans == -1 :
        ans = c
    if madea*bb == madeb*aa and ans > c:
        ans = c

print(ans)

Submission status: Wrong Answer

Solution code:
N, MA, MB = map(int, raw_input().split())
X = [map(int, raw_input().split()) for _ in range(N)]

DP = [[100000 for _ in range(401)] for _ in range(401)]
DP[0][0] = 0

for a, b, c in X:
    for sa in range(401 - a):
        for sb in range(401 - b):
            DP[sa+a][sb+b] = min(DP[sa+a][sb+b], DP[sa][sb] + c)

a, b = MA, MB
ans = 100000
while a <= 400 and b <= 400:
    ans = min(ans, DP[a][b])
    a += MA
    b += MB

if ans == 100000:
    print -1
else:
    print ans

Submission status: Wrong Answer

Solution code:
import copy

data = raw_input()
n,ma,mb = map(int,data.split(" "))

db = []

price = 999999999

for x in range(n):
  data = raw_input()
  a,b,c = map(int,data.split(" "))
  db.append([a,b,c])

def solve(now, data):
  global db
  global price,n,ma,mb
  for x in range(now+1, len(db)):
    if (data[0] + db[x][0]) % ma == 0 and (data[1] + db[x][1]) % mb == 0:
      if price > data[2]+db[x][2]:
        price = data[2]+db[x][2]
      else:
        solve(x, [ data[0] + db[x][0], data[1] + db[x][1], data[2] + db[x][2] ])
  return

for x in range(0,len(db)):
  solve(x,db[x])

if price != 999999999:
  print price
else:
  print -1

Submission status: Wrong Answer

Solution code:
N, Ma, Mb = map(int, raw_input().split())
abc = []
for i in range(N): abc.append(map(float, raw_input().split())) 
abc = sorted(abc, key=lambda x:x[2])
C = float(Ma)/Mb
sums = []
for i in range(N):
	elm = abc.pop()
	org_sums = list(sums)
	for itm in abc:
		sum_i = (elm[0]+itm[0], elm[1]+itm[1], elm[2]+itm[2])
		sums.append(sum_i)
		if sum_i[0]/sum_i[1] == C: 
			print int(sum_i[2]) 
			exit(0)
	sums += org_sums
	sums.append(elm)
	if elm[0]/elm[1] == C: 
		print int(elm[2]) 
		exit(0)
print -1

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from fractions import gcd

def readln():
    _res = list(map(int,str(input()).split(' ')))
    return _res

def push(k,v):
    if k in f:
        f[k] = min(f[k],v)
    else:
        f[k] = v

def add(k,v):
    es = []
    for e in f:
        es.append(e)
    for ee in es:
        push(ee+k,f[ee]+v)
    push(k,v)

a = readln()
n,x,y = a[0],a[1],a[2]
f = {}
for i in range(0,n):
    a = readln()
    add(a[0]*y-a[1]*x,a[2])
if 0 in f:
    print(f[0])
else:
    print('-1')

Submission status: Wrong Answer

Solution code:
Unknown = 1234567
best = Unknown

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

abc = []
for _ in range(N):
    abc.append(list(map(int, input().split())))

def search(choice, a, b, c, start):
    if a % A == b % B == 0 and a // A == b // B:
        global best
        best = min(best, c)
        choice.pop()
        return
    for i in range(start, N):
        if i in choice:
            continue
        if (a / b > A / B and abc[i][0] < abc[i][1]) or (a / b < A / B and abc[i][0] > abc[i][1]):
            if best <= c + abc[i][2]:
                continue
            choice.append(i)
            search(choice, a + abc[i][0], b + abc[i][1], c + abc[i][2], start)
    choice.pop()

for i in range(N):
    search([i], abc[i][0], abc[i][1], abc[i][2], i + 1)

if best == Unknown:
    best = -1

print(best)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from fractions import gcd

def readln():
    _res = list(map(int,str(input()).split(' ')))
    return _res

def push(k,v):
    if k in f:
        f[k] = min(f[k],v)
    else:
        f[k] = v

def add(k,v):
    es = []
    for e in f:
        es.append(e)
    for e in es:
        push(e+k,f[e]+v)
    push(k,v)

a = readln()
n,x,y = a[0],a[1],a[2]
f = {}
for i in range(0,n):
    a = readln()
    add(a[0]*y-a[1]*x,a[2])
if 0 in f:
    print(f[0])
else:
    print('-1')

Submission status: Wrong Answer

Solution code:
import copy

N, Ma, Mb = [int(n) for n in input().split()]
pd = {(0,0):0}
for i in range(N):
    a, b, c = [int(n) for n in input().split()]
    pdcopy = copy.deepcopy(pd)
    for k, v in pdcopy.items():
        nk = (k[0]+a, k[1]+b)
        if nk in pd:
            if pd[nk] > pd[k] + c :
                pd[nk] = pd[k] + c
        else:
            pd[nk] = pd[k] + c

mp = 1000000
for i in range(1,401):
    if (Ma*i, Mb*i) in pd:
        mp = min(pd[(Ma*i, Mb*i)], mp)

if mp == 1000000:
    print(-1)
else:
    print(mp)

Submission status: Wrong Answer

Solution code:
Unknown = 1234567
best = Unknown

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

abc = []
for _ in range(N):
    abc.append(list(map(int, input().split())))

def search(choice, a, b, c):
    if a % A == b % B == 0 and a // A == b // B:
        global best
        best = min(best, c)
        choice.pop()
        return
    for i in range(N):
        if i in choice:
            continue
        if (a / b > A / B and abc[i][0] < abc[i][1]) or (a / b < A / B and abc[i][0] > abc[i][1]):
            if best <= c + abc[i][2]:
                continue
            choice.append(i)
            search(choice, a + abc[i][0], b + abc[i][1], c + abc[i][2])
    choice.pop()

for i in range(N):
    search([i], abc[i][0], abc[i][1], abc[i][2])            

if best == Unknown:
    best = -1

print(best)

Submission status: Wrong Answer

Solution code:
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, Ma, Mb = map(int, input().split())
    a_w = []
    b_w = []
    costs = []

    for i in range(N):
        a, b, c = map(int, input().split())
        a_w.append(a)
        b_w.append(b)
        costs.append(c)

    dp = [[[-1]*(10*N + 1) for j in range(10*N + 1)]
            for k in range(2)]

    dp[0][0][0] = 0
    dp[1][0][0] = 0

    for i in range(N):
        for a in range(10*N + 1):
            for b in range(10*N + 1):
                if a - a_w[i] >= 0 and b - b_w[i] >= 0:
                    if dp[0][a - a_w[i]][b - b_w[i]] >= 0:
                        if dp[1][a][b] == -1:
                            dp[1][a][b]= dp[0][a - a_w[i]][b - b_w[i]] + costs[i]
                        else:
                            min_ = min(dp[1][a][b],
                                       dp[0][a - a_w[i]][b - b_w[i]] + costs[i])
                            dp[1][a][b] = min_
        dp[0] = dp[1][:]

    # debug(dp, locals())
    min_cost = float('inf')

    for a in range(10*N + 1):
        for b in range(10*N + 1):
            if a != 0 and b != 0:
                if a * Mb == b * Ma and dp[1][a][b] > 0:
                    min_cost = min(min_cost, dp[1][a][b])

    if min_cost == float('inf'):
        ans = -1
    else:
        ans = min_cost

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
n,ma,mb = list(map(int,input().split()))
G=[]
for i in range(n):
    G.append(list(map(int,input().split())))

DP = [[10000 for _ in range(500)] for _ in range(500)]
DP[0][0]=0
for i in range(n):
    for j in range(400):
        for k in range(400):
            if DP[j][k]==10000:continue
            DP[j+G[i][0]][k+G[i][1]] = min(DP[j][k]+G[i][2],DP[j+G[i][0]][k+G[i][1]])

ans=10000
for i in range(1,min(400//ma,400//mb)+1):
    ans=min(ans,DP[ma*i][mb*i])

if ans==10000:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N, Ma, Mb = map(int, raw_input().split())
abc = []
for i in range(N): abc.append(map(float, raw_input().split())) 
#abc = sorted(abc, key=lambda x:x[2])
C = float(Ma)/Mb
sums = []
want = []
for i in range(N):
	elm = abc.pop()
	org_sums = list(sums)
	for itm in abc:
		sum_i = (elm[0]+itm[0], elm[1]+itm[1], elm[2]+itm[2])
		sums.append(sum_i)
		if sum_i[0]/sum_i[1] == C: want.append(sum_i)
	sums += org_sums
	sums.append(elm)
	if elm[0]/elm[1] == C: want.append(elm)
if len(want) == 0: print -1
else: print int(min(want, key=lambda x:x[2])[2])

Submission status: Wrong Answer

Solution code:
import copy

N, Ma, Mb = [int(n) for n in input().split()]
pd = {(0,0):0}
for i in range(N):
    a, b, c = [int(n) for n in input().split()]
    pdcopy = copy.deepcopy(pd)
    for k, v in pdcopy.items():
        nk = (k[0]+a, k[1]+b)
        if nk in pd:
            if pd[nk] > c :
                pd[nk] = c
        else:
            pd[nk] = c

mp = 1000000
for i in range(1,401):
    if (Ma*i, Mb*i) in pd:
        mp = min(pd[(Ma*i, Mb*i)], mp)

if mp == 1000000:
    print(-1)
else:
    print(mp)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from fractions import gcd

def readln():
    _res = list(map(int,str(input()).split(' ')))
    return _res

def push(k,v):
    if k in f:
        f[k] = min(f[k],v)
    else:
        f[k] = v

def add(k,v):
    es = []
    for e in f:
        es.append(e)
    for e in es:
        push(e+k,f[e]+v)
    push(k,v)

a = readln()
n,x,y = a[0],a[1],a[2]
f = {}
for i in range(0,n):
    a = readln()
    add(a[0]*y-a[1]*x,a[2])
print(f)
if 0 in f:
    print(f[0])
else:
    print('-1')

Submission status: Wrong Answer

Solution code:
from collections import Counter

N, MA, MB = map(int, raw_input().split())
X = [map(int, raw_input().split()) for _ in range(N)]

DP = [[100000 for _ in range(401)] for _ in range(401)]
DP[0][0] = 0

S = {(0, 0)}
for a, b, c in X:
    for sa, sb in S:
        if DP[sa+a][sb+b] > DP[sa][sb] + c:
            DP[sa+a][sb+b] = DP[sa][sb] + c
    T = {(sa+a, sb+b) for sa, sb in S}
    S |= T

a, b = MA, MB
ans = 100000
while a <= 400 and b <= 400:
    ans = min(ans, DP[a][b])
    a += MA
    b += MB

if ans == 100000:
    print -1
else:
    print ans

Submission status: Wrong Answer

Solution code:
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, Ma, Mb = map(int, input().split())
    a_w = []
    b_w = []
    costs = []

    for i in range(N):
        a, b, c = map(int, input().split())
        a_w.append(a)
        b_w.append(b)
        costs.append(c)

    dp = [[[-1]*(10*N + 1) for j in range(10*N + 1)]
            for k in range(2)]

    dp[0][0][0] = 0
    dp[1][0][0] = 0

    for i in range(N):
        for a in range(10*N + 1):
            for b in range(10*N + 1):
                if a - a_w[i] >= 0 and b - b_w[i] >= 0:
                    if dp[0][a - a_w[i]][b - b_w[i]] >= 0:
                        dp[1][a][b]= dp[0][a - a_w[i]][b - b_w[i]] + costs[i]
        dp[0] = dp[1][:]

    # debug(dp, locals())
    min_cost = float('inf')

    for a in range(10*N + 1):
        for b in range(10*N + 1):
            if a != 0 and b != 0:
                if a * Mb == b * Ma and dp[1][a][b] >= 0:
                    min_cost = min(min_cost, dp[1][a][b])

    if min_cost == float('inf'):
        ans = -1
    else:
        ans = min_cost

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from fractions import gcd

def readln():
    _res = list(map(int,str(input()).split(' ')))
    return _res

def push(k,v):
    if k in f:
        f[k] = min(f[k],v)
    else:
        f[k] = v

def add(k,v):
    push(k,v)
    es = []
    for e in f:
        es.append(e)
    for e in es:
        push(e+k,f[e]+v)

a = readln()
n,x,y = a[0],a[1],a[2]
f = {}
for i in range(0,n):
    a = readln()
    add(a[0]*y-a[1]*x,a[2])
if 0 in f:
    print(f[0])
else:
    print('-1')

Submission status: Wrong Answer

Solution code:
n,ma,mb=map(int,raw_input().split())
abc=[map(int,raw_input().split()) for  _ in xrange(n)]
dp=[[[10**5]*(n*10+1) for _ in xrange(n*10+1)] for _ in xrange(n+1)]
for i in xrange(n):
    dp[i][0][0]=0
for i in xrange(n):
    for j in range(n*10+1):
        for k in xrange(n*10+1):
            a,b,c=abc[i][0],abc[i][1],abc[i][2]
            if j-a<0 or k-b<0:
                dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k])
            else:
                dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j-a][k-b]+c)
i=1
ans=10**5
while ma*i<=n*10 and mb*i<=n*10:
    if dp[n][ma*i][mb*i]!=10**5:
        ans=min(ans,dp[n][ma*i][mb*i])
    i+=1
if ans==10**5:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, Ma, Mb = map(int, input().split())
    a_w = []
    b_w = []
    costs = []

    for i in range(N):
        a, b, c = map(int, input().split())
        a_w.append(a)
        b_w.append(b)
        costs.append(c)

    dp = [[[-1]*(10*N + 1) for j in range(10*N + 1)]
            for k in range(2)]

    dp[0][0][0] = 0

    for i in range(N):
        for a in range(10*N + 1):
            for b in range(10*N + 1):
                if a - a_w[i] >= 0 and b - b_w[i] >= 0:
                    if dp[0][a - a_w[i]][b - b_w[i]] >= 0:
                        dp[1][a][b]= dp[0][a - a_w[i]][b - b_w[i]] + costs[i]
        dp[0] = dp[1][:]

    # debug(dp, locals())
    min_cost = float('inf')

    for a in range(10*N + 1):
        for b in range(10*N + 1):
            if a != 0 and b != 0:
                if a * Mb == b * Ma:
                    if dp[1][a][b] != -1:
                        min_cost = min(min_cost, dp[1][a][b])

    if min_cost == float('inf'):
        ans = -1
    else:
        ans = min_cost

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, Ma, Mb = map(int, input().split())
    a_w = []
    b_w = []
    costs = []

    for i in range(N):
        a, b, c = map(int, input().split())
        a_w.append(a)
        b_w.append(b)
        costs.append(c)

    dp = [[[-1]*(10*N + 1) for j in range(10*N + 1)]
            for k in range(2)]

    dp[0][0][0] = 0

    for i in range(N):
        for a in range(10*N + 1):
            for b in range(10*N + 1):
                if a - a_w[i] >= 0 and b - b_w[i] >= 0:
                    if dp[0][a - a_w[i]][b - b_w[i]] >= 0:
                        dp[1][a][b]= dp[0][a - a_w[i]][b - b_w[i]] + costs[i]
        dp[0] = dp[1][:]

    # debug(dp, locals())
    min_cost = float('inf')

    for a in range(10*N + 1):
        for b in range(10*N + 1):
            if a * Mb == b * Ma:
                if dp[1][a][b] != -1:
                    min_cost = min(min_cost, dp[1][a][b])

    if min_cost == float('inf'):
        ans = -1
    else:
        ans = min_cost

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from fractions import gcd

def readln():
    _res = list(map(int,str(input()).split(' ')))
    return _res

def dp(a):
    res = [1000000 for i in range(0,5000)]
    res[0] = 0
    for e in a:
        for i in range(e[0],5000):
            res[i] = min(res[i], e[1] + res[i - e[0]])
    return res

a = readln()
n,x,y = a[0],a[1],a[2]
up = []
down = []
ans = 1000000
for i in range(0,n):
    a = readln()
    s = [a[0]*y-a[1]*x,a[2]]
    if s[0] > 0:
        up.append(s)
    elif s[0] < 0:
        down.append([-s[0],s[1]])
    elif s[0] == 0:
        ans = min(ans,s[1])

fup = dp(up)
fdown = dp(down)
for i in range(1,5000):
    ans = min(ans,fup[i]+fdown[i])
if ans < 1000000 : print(ans)
else : print('-1')

Submission status: Wrong Answer

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

import operator

N, Ma, Mb = map(int, input().split())
M_rate = Ma / (Ma + Mb)

a_small = []
a_large = []
a_same = []

objs = []
ans = 1e10    
for n in range(N):
    a, b, c = map(int, input().split())

    if a * (Ma + Mb) == Ma * (a + b):
        ans = min(ans, c)
    else:
        objs.append((a,b,c))

for i in range(len(objs)-1):
    for j in range(i+1, len(objs)):
        a, b, c = tuple(map(operator.add, objs[i], objs[j]))
        if a * (Ma + Mb) == Ma * (a + b):
            ans = min(ans, c)

if ans == 1e10:
    print(-1)
else:
    print(ans)