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: Runtime Error

Solution code:
from sys import stdin, stdout
def readLine_int_list():return list(map(int, stdin.readline().split()))
def readAll_int(): return list(list(map(int,i.split())) for i in stdin.read().split("\n"))
 
 
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def ratio(a,b):
    return (a//gcd(a,b), b//gcd(a,b))
 
def add_ratio(a,b):
    if a != 0:
        sum_a = sum(a)
        sum_b = sum(b)
        _a = a[0]*sum_b + b[0]*sum_a
        _b = b[1]*sum_a + a[1]*sum_b
        return ratio(_a, _b)
    else:
        return(b)
 
def dfs(i, v, r,ans):
    if i == n:
        if r == (Ma,Mb):
            ans.append(v)
        return 0

    if dfs(i+1, v, r,ans):
        return 0
    
    if dfs(i+1, v+D[i][2], add_ratio(r,ratio(D[i][0],D[i][1])), ans):
        return 0
 
    return 0
ans = []
n, Ma, Mb = readLine_int_list()
D = readAll_int()
e=0
for i in D:
    e += i[2]

def main():
    dfs(0,0,0,ans)
    if ans:
        print(min(ans))
    else:
        print(-1)
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
def readLine_int_list():return list(map(int, stdin.readline().split()))
def readAll_int(): return list(list(map(int,i.split())) for i in stdin.read().split("\n"))
 
 
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
	
def ratio(a,b):
    return (a//gcd(a,b), b//gcd(a,b))
 
def add_ratio(a,b):
    if a != 0:
        sum_a = sum(a)
        sum_b = sum(b)
        _a = a[0]*sum_b + b[0]*sum_a
        _b = b[1]*sum_a + a[1]*sum_b
        return ratio(_a, _b)
    else:
        return(b)
 
def dfs(i, v, r,ans):
    if i == n:
        if r == (Ma,Mb):
            ans.append(v)
        return 0

    if dfs(i+1, v, r,ans):
        return 0
    
    if dfs(i+1, v+D[i][2], add_ratio(r,ratio(D[i][0],D[i][1])), ans):
        return 0
 
    return 0
ans = []
n, Ma, Mb = readLine_int_list()
D = readAll_int()
e=0
for i in D:
    e += i[2]

def main():
    dfs(0,0,0,ans)
    if ans:
        print(min(ans))
    else:
        print(-1)
 
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
from pprint import pprint
def readLine_int_list():return list(map(int, stdin.readline().split()))
def readAll_int(): return list(list(map(int,i.split())) for i in stdin.read().split("\n"))


def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
	
def ratio(a,b):
    return (a//gcd(a,b), b//gcd(a,b))

def add_ratio(a,b):
    if a != 0:
        sum_a = sum(a)
        sum_b = sum(b)
        _a = a[0]*sum_b + b[0]*sum_a
        _b = b[1]*sum_a + a[1]*sum_b
        return ratio(_a, _b)
    else:
        return(b)

def dfs(i, v, r,ans):
    if i == n:
        if r ==(Ma,Mb):
            ans.append(v)
        return 0
        
    if dfs(i+1, v, r,ans):
        return 0
   
    if dfs(i+1, v+D[i][2], add_ratio(r,ratio(D[i][0],D[i][1])),ans):
        return 0

    return 0
    
ans = []
n, Ma, Mb = readLine_int_list()
D = readAll_int()
e=0
for i in D:
    e += i[2]
    
def main():
    dfs(0,0,0,ans)
    if ans:
        print(min(ans))
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
def readLine_int_list():return list(map(int, stdin.readline().split()))
def readAll_int(): return list(list(map(int,i.split())) for i in stdin.read().split("\n"))

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def ratio(a,b):
    return (a//gcd(a,b), b//gcd(a,b))

def add_ratio(a,b):
    if a != 0:
        sum_a = sum(a)
        sum_b = sum(b)
        _a = a[0]*sum_b + b[0]*sum_a
        _b = b[1]*sum_a + a[1]*sum_b
        return ratio(_a, _b)
    else:
        return(b)

def dfs(i, v, r,ans):
    if i == n:
        if r ==(Ma,Mb):
            ans.append(v)
        return 0
        
    if dfs(i+1, v, r,ans):
        return 0
   
    if dfs(i+1, v+D[i][2], add_ratio(r,ratio(D[i][0],D[i][1])),ans):
        return 0


ans = []
n, Ma, Mb = readLine_int_list()
D = readAll_int()
e=0
for i in D:
    e += i[2]
    
def main():
    
    dfs(0,0,0,ans)
    if ans:
        print(min(ans))
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
from pprint import pprint
def readLine_int_list():return list(map(int, stdin.readline().split()))
def readAll_int(): return list(list(map(int,i.split())) for i in stdin.read().split("\n"))


def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
	
def ratio(a,b):
    return (a//gcd(a,b), b//gcd(a,b))

def add_ratio(a,b):
    if a != 0:
        sum_a = sum(a)
        sum_b = sum(b)
        _a = a[0]*sum_b + b[0]*sum_a
        _b = b[1]*sum_a + a[1]*sum_b
        return ratio(_a, _b)
    else:
        return(b)

def dfs(i, v, r,ans):
    if i == n:
        if r ==(Ma,Mb):
            ans.append(v)
        return 0
        
    if dfs(i+1, v, r,ans):
        return 0
   
    if dfs(i+1, v+D[i][2], add_ratio(r,ratio(D[i][0],D[i][1])),ans):
        return 0


ans = []
n, Ma, Mb = readLine_int_list()
D = readAll_int()
e=0
for i in D:
    e += i[2]
    
def main():
    
    dfs(0,0,0,ans)
    if ans:
        print(min(ans))
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def solve():
    
    INF = float('inf')
    
    N, Ma, Mb = map(int, input().split())
    
    l = []
    for _ in range(N):
        a,b,c = map(int, input().split())
        l.append((a,b,c))
        
    #dp table: dp[i][ca][cb] 
    dp = [[[INF] * 401 for _ in range(401)] for _ in range(N+1)]
    dp[0][0][0] = 0
    
    for i in range(N):
        for ca in range(401):
            for cb in range(401):
                if dp[i][a][b] != INF:
                    dp[i+1][a][b] = min(dp[i][a][b], dp[i+1][a][b]) #薬品iを加えない場合
                    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]) #薬品iを加える場合
                    
    ans = INF
    for i in range(N):
        for ca in range(401):
            for cb in range(401):
                if dp[i][a][b] != INF:
                    if a * Mb == b * Ma:
                        ans = min(ans, dp[i][a][b])
    
    print(-1 if ans == INF else ans)

if __name__ == '__main'__:
    solve()

Submission status: Runtime Error

Solution code:
# ABC54 D
n,ma,mb = map(int, input().split())
a = []
b = []
c = []
for i in range(N):
    ai,bi,ci = map(int, input().split())
    a.append(ai)
    b.append(bi)
    c.append(ci)
    
max_sum = n * 10
max_cost = 100000000
dp = [[[max_cost for k in range(max_sum+1)] for j in range(max_sum+1)] for i in range(n+1)]

dp[0][0][0] = 0
for i in range(n):
    for ca in range(max_sum+1):
        for cb in range(max_sum+1):
            if(dp[i][ca][cb] == max_cost):
                continue
            dp[i+1][ca][cb] = min(dp[i+1][ca][cb], dp[i][ca][cb])
            dp[i+1][ca+a[i]][cb+b[i]] = min(dp[i+1][ca+a[i]][cb+b[i]], dp[i][ca][cb]+c[i])

ans = max_cost
for ca in range(1,max_sum+1):
    for cb in range(1,max_sum+1):
        if(ca*mb == cb*ma):
            ans = min(ans, dp[n][ca][cb])

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

Submission status: Runtime Error

Solution code:
# ABC54 D
n,ma,mb = map(int, input().split())
a = []
b = []
c = []
for i in range(N):
    ai,bi,ci = map(int, input().split())
    a.append(ai)
    b.append(bi)
    c.append(ci)
    
max_sum = n * 10
max_cost = 100000000
dp = [[[max_cost for k in range(n+1)] for j in range(max_sum+1)] for i in range(max_sum+1)]

dp[0][0][0] = 0
for i in range(n):
    for ca in range(max_sum+1):
        for cb in range(max_sum+1):
            if(dp[i][ca][cb] == max_cost):
                continue
            dp[i+1][ca][cb] = min(dp[i+1][ca][cb], dp[i][ca][cb])
            dp[i+1][ca+a[i]][cb+b[i]] = min(dp[i+1][ca+a[i]][cb+b[i]], dp[i][ca][cb]+c[i])

ans = max_cost
for ca in range(max_sum+1):
    for cb in range(max_sum+1):
        if(ca*mb == cb*ma):
            ans = min(ans, dp[n][ca][cb])

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

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
N,Ma,Mb=map(int,input().split())
yaku=[]
for _ in range(N):
    yaku.append(list(map(int,input().split())))


candi_money=[]

for n in range(N):
    candis=list(itertools.combinations(np.arange(N),n))
    for candi in candis:
        a,b,c=0,0,0
        for num in candi:
            a +=yaku[num][0]
            b +=yaku[num][1]
            c +=yaku[num][2]
		if a/flaot(Ma/Mb)=b:
	    	candi_money.append(c)

if len(candi_money)==0:
	print(-1)
else:
	print(min(candi_money))

Submission status: Runtime Error

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(N*i+1):
            for cb in range(N*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()
    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: Runtime Error

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()
    dp[0][0][0] = 0.0

    for i in range(N):
        for ca in range(N*(i+1)+1):
            for cb in range(N*(i+1)+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]][c\
b+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: Runtime Error

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()
    dp[0][0][0] = 0.0

    for i in range(N):
	for ca in range(N*i+1):
            for cb in range(N*i+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: Runtime Error

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

    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]=np.min([dp[i+1,ca,cb],dp[i,ca,cb]])
                dp[i+1,ca+drugs[i][0],cb+drugs[i][1]]=np.min([dp[i+1,ca+drugs[i][0],cb+drugs[i][1]],dp[i,ca,cb]+drugs[i][2]])

Submission status: Runtime Error

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
    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]=np.min([dp[i+1,ca,cb],dp[i,ca,cb]])
                dp[i+1,ca+drugs[i][0],cb+drugs[i][1]]=np.min([dp[i+1,ca+drugs[i][0],cb+drugs[i][1]],dp[i,ca,cb]+drugs[i][2]])
    print(-1)
    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: Runtime Error

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
    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]=np.min([dp[i+1,ca,cb],dp[i,ca,cb]])
                dp[i+1,ca+drugs[i][0],cb+drugs[i][1]]=np.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: Runtime Error

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
    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]=np.min([dp[i+1,ca,cb],dp[i,ca,cb]]);
		dp[i+1,ca+drugs[i][0],cb+drugs[i][1]]=np.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: Runtime Error

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)]).astype(np.int16)

    inf = 100*N + 1
    dp = np.ones((N+1,N*10+1,N*10+1)) * inf
    dp[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]=np.min([dp[i+1,ca,cb],dp[i,ca,cb]]);
		dp[i+1,ca+drugs[i,0],cb+drugs[i,1]]=np.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: Runtime Error

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

    inf = 100*N + 1
    dp = np.ones((N+1,N*10+1,N*10+1)) * inf
    dp[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]=np.min([dp[i+1,ca,cb],dp[i,ca,cb]]);
		dp[i+1,ca+drugs[i,0],cb+drugs[i,1]]=np.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: Runtime Error

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

    inf = 100*N + 1
    dp = np.ones((N+1,N*10+1,N*10+1)) * inf
    dp[0,0,0] = 0
    for i in range(0, 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]=np.min([dp[i+1,ca,cb],dp[i,ca,cb]]);
		dp[i+1,ca+drugs[i,0],cb+drugs[i,1]]=np.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[i,ca,cb] < ans):
            	ans = dp[i,ca,cb]
    if(ans==inf):
	ans = -1
    print(int(ans))

Submission status: Runtime Error

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

    inf = 100*N + 1
    dp = np.ones((N,N*10,N*10)) * inf
    dp[0,0,0] = 0
    for i in range(0, N-1):
	for ca in range(N*10):
            for cb in range(N*10):
		if(dp[i,ca,cb]==inf):
                    continue
		dp[i+1,ca,cb]=np.min([dp[i+1,ca,cb],dp[i,ca,cb]]);
		dp[i+1,ca+drugs[i,0],cb+drugs[i,1]]=np.min([dp[i+1,ca+drugs[i,0],cb+drugs[i,1]],dp[i,ca,cb]+drugs[i,2]]);

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

Submission status: Runtime Error

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

    inf = 100*N + 1
    dp = np.ones((N,N*10,N*10)) * inf
    dp[0,0,0] = 0
    for i in range(0, N-1):
	for ca in range(N*10):
            for cb in range(N*10):
		if(dp[i,ca,cb]==inf):
                    continue
		dp[i+1,ca,cb]=np.min([dp[i+1,ca,cb],dp[i,ca,cb]]);
		dp[i+1,ca+drugs[i,0],cb+drugs[i,1]]=np.min([dp[i+1,ca+drugs[i,0],cb+drugs[i,1]],dp[i,ca,cb]+drugs[i,2]]);

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

Submission status: Runtime Error

Solution code:
import numpy as np

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

    inf = 100*N + 1
    dp = np.ones((N,N*10,N*10)) * inf
    dp[0,0,0] = 0
    for i in range(0, N-1):
        for ca in range(N*10):
            for cb in range(N*10):
                if(dp[i,ca,cb]==inf):
                    continue
                dp[i+1,ca,cb]=np.min([dp[i+1,ca,cb],dp[i,ca,cb]]);
                dp[i+1,ca+drugs[i,0],cb+drugs[i,1]]=np.min([dp[i+1,ca+drugs[i,0],cb+drugs[i,1]],dp[i,ca,cb]+drugs[i,2]]);

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

Submission status: Runtime Error

Solution code:
import numpy as np

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

    inf = 100*N + 1
    dp = np.ones((N,N*10,N*10)) * inf
    dp[0,0,0] = 0
    for i in range(0, N-1):
        for ca in range(N*10):
            for cb in range(N*10):
                if(dp[i,ca,cb]==inf):
                    continue
                dp[i+1,ca,cb]=np.min([dp[i+1,ca,cb],dp[i,ca,cb]]);
                dp[i+1,ca+drugs[i,0],cb+drugs[i,1]]=np.min([dp[i+1,ca+drugs[i,0],cb+drugs[i,1]],dp[i,ca,cb]+drugs[i,2]]);

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

Submission status: Runtime Error

Solution code:
from copy import deepcopy as dcopy
import fractions
def main():
    global N, ma, mb
    N, ma, mb = map(int, input().split())
    shop = [list(map(int, input().split())) for n in range(N)]

    status = dd(int)
    status[(0,0)] = 0
    minimum = 100000
    for product in shop:
        # buy
        old_status = dcopy(status)
        for s, v in old_status.items():
            key = (s[0]+product[0], s[1]+product[1])
            value = v + product[2]
            if not key in status:
                status[key] = value
                if check(key) and value < minimum:
                    minimum = value
            elif status[key] > value:
                status[key] = value
                if check(key) and value < minimum:
                    minimum = value

    if minimum == 100000:
        print(-1)
    else:
        print(minimum)

def check(key):
    c = fractions.gcd(key[0], key[1])
    if key[0]/c == ma and key[1]/c == mb:
        return True
    else:
        return False

if __name__ == "__main__":# {{{
    try:
        import test
        test.test()
    except:
        main()# }}}

Submission status: Runtime Error

Solution code:
from copy import deepcopy

fin = open('test4.txt')
input = fin.readline


def wfs(tree, root, node_num):
    lost_list = [root]

    def _wfs(tree, root, lost_list) -> int:
        if len(lost_list) == node_num:
            return 1
        counter = 0
        for i in tree[root]:
            if i not in lost_list:
                tmp = deepcopy(lost_list)
                tmp.append(i)
                counter += _wfs(tree, i, tmp)
        return counter

    return _wfs(tree, 0, lost_list)


N, MA, MB = [int(i) for i in input().rstrip().split()]
TGT = MA / MB
med = [[int(i) for i in input().rstrip().split()] for _ in range(N)]
flag_list = [0] * N
amount = [0, 0]
all_list = list()


def solve(amount, flag_list, money, i):
    global TGT
    global all_list
    global med
    global N
    try :
        if amount[0] / amount[1] == TGT:
            all_list.append(money)
    except ZeroDivisionError as e:
        pass
    if i == N:
        return
    solve(amount, flag_list, money, i + 1)
    flag_list[i] = 1
    amount[0] += med[i][0]
    amount[1] += med[i][1]
    solve(amount, flag_list, money + med[i][2], i + 1)
    flag_list[i] = 0
    amount[0] -= med[i][0]
    amount[1] -= med[i][1]

solve(amount, flag_list, 0, 0)

if len(all_list) == 0:
    print(-1)
else:
    print(min(all_list))

Submission status: Runtime Error

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_
        
        for k in range(10*N + 1):
            dp[0][k] = dp[1][k][:]

        for i in range(10*N + 1):
            # print(*dp[0][i], file=sys.stderr)


    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: Runtime Error

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]:
                return
            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: Runtime Error

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

M = 401
INF = 10 ** 15
min_cost = dict()
min_cost[0, 0] = 0

for k in range(n):
    keys = min_cost.keys()
    for i, j in reversed(sorted(keys)):
        if i + a[k] < M and j + b[k] < M:
            cc = min_cost[i][j] + c[k]
            if cc < min_cost[i + a[k]][j + b[k]]:
                min_cost[i + a[k]][j + b[k]] = cc

res = INF
for i in range(1, M):
    for j in range(1, M):
        if i * mb == j * ma:
            if min_cost[i][j] < res:
                res = min_cost[i][j]

if res == INF:
    res = -1
print(res)

Submission status: Runtime Error

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].copy()

    # 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: Runtime Error

Solution code:
from collections import defaultdict
from fractions import Fraction

memo = {}
gl_ans = 10 ** 10

def dfs(i, a, b, c):
    global gl_ans
    if a != 0 and b != 0 and Fraction(a, b) == Fraction(Ma, Mb):
        gl_ans = min(gl_ans, c)
        return c

    if i == N:
        return 10 ** 10

    if (i, a, b, c) in memo:
        return memo[(i, a, b)]

    if c > gl_ans:
        return 10 ** 10

    ans = dfs(i + 1, a + l[i][0], b + l[i][1], c + l[i][2])
    ans = min(ans, dfs(i + 1, a, b, c))

    memo[(i, a, b, c)] = ans

    return ans


if __name__ == '__main__':

    N, Ma, Mb = map(int, input().split())
    l = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        l.append((a, b, c))

    s = dfs(0, 0, 0, 0)
    if s >= 10 ** 10:
        print(-1)
    else:
        print(s)