Problem: 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.

Submission attempts (in order):
N, Ma, Mb = map(int, input().split())
Med = [tuple(map(int, input().split())) for _ in range(N)]
N *= 100
import numpy as np
dp = np.full((N+1,N+1),np.inf) 
dp[0,0] = 0
from itertools import product
R = lambda x:reversed(range(x,N+1))
for a,b,c in Med:
    for i,j in product(R(a),R(b)):
        dp[i,j] = min(dp[i,j], dp[i-a,j-b]+c)
        
ans = np.inf
for n in range(1,min(N//Ma, N//Mb)):
    ans = min(ans, dp[n*Ma, n*Mb])
print(ans if ans != np.inf else -1)

import math
nmax = 40
abmax = 10
INF = 10000


N, Ma, Mb = map(int, input().split())
medichine = []
for i in range(N):
    Lst = [int(x) for x in input().split()]
    medichine.append(Lst)

dp = {}

for i in range(N+1):
    for ca in range(nmax*abmax+1):
        for cb in range(nmax*abmax+1):
            dp[i,ca,cb] = INF
dp[0,0,0] = 0

for i in range(N):
    for ca in range(nmax*abmax+1):
        for cb in range(nmax*abmax+1):
            if dp[i,ca,cb] != INF:
                dp[i+1,ca,cb] = min(dp[i+1,ca,cb],dp[i,ca,cb])
                dp[i+1,ca+medichine[i][0],cb+medichine[i][1]] = min(dp[i+1,ca+medichine[i][0],cb+medichine[i][1]], dp[i,ca,cb]+medichine[i][2])

ans = INF
for ca in range(nmax*abmax+1):
        for cb in range(nmax*abmax+1):
            if ca*Mb == cb*Ma:
                ans = min(ans,dp[N,ca,cb])

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


INF = 5000

def dp(n, medichine, Ma, Mb):
    INF =  5000
    if n == 0: 
        List = [[0, 0, 0], medichine[n]]
        if medichine[n][0] * Mb == medichine[n][1] * Ma:
            cost = medichine[n][2]
        else:
            cost = INF
    else: 
        previous = dp(n-1, medichine, Ma, Mb)
        List = previous[0].copy()
        cost = previous[1]
        if medichine[n][2] > cost:
            for x in previous[0]:
                C = x[2] + medichine[n][2]
                if C > cost:
                    continue
                A = x[0] + medichine[n][0]
                B = x[1] + medichine[n][1]
                List.append([A, B, C])
                if A * Mb == B * Ma:
                    cost = C         
    return List, cost



N, Ma, Mb = map(int, input().split())
medichine = []
for i in range(N):
    Lst = [int(x) for x in input().split()]
    medichine.append(Lst)
ans = dp(N-1, medichine, Ma, Mb)
cost = ans[1]
if cost != INF:
    print(cost)
else:
    print(-1)

import math
nmax = 40
abmax = 10
INF = 10000


N, Ma, Mb = map(int, input().split())
medichine = []
for i in range(N):
    Lst = [int(x) for x in input().split()]
    medichine.append(Lst)

dp = {}

for i in range(N+1):
    for ca in range(nmax*abmax+1):
        for cb in range(nmax*abmax+1):
            dp[i,ca,cb] = INF
dp[0,0,0] = 0

for i in range(N):
    for ca in range(nmax*abmax+1):
        for cb in range(nmax*abmax+1):
            if dp[i,ca,cb] != INF:
                dp[i+1,ca,cb] = min(dp[i+1,ca,cb],dp[i,ca,cb])
                dp[i+1,ca+medichine[i][0],cb+medichine[i][1]] = min(dp[i+1,ca+medichine[i][0],cb+medichine[i][1]], dp[i,ca,cb]+medichine[i][2])

ans = INF
for ca in range(nmax*abmax+1):
        for cb in range(nmax*abmax+1):
            if ca*Mb == cb*Ma:
                ans = min(ans,dp[N,ca,cb])

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

N, Ma, Mb = map(int, input().split())
Med = [tuple(map(int, input().split())) for _ in range(N)]
INF = 100000
from collections import defaultdict as dd
dp =  [dd(lambda:INF) for _ in range(N+1)]
for n in range(1,N+1):
    a,b,c = Med[n-1]
    dp[n-1][0,0] = 0
    for (i,j),value in dp[n-1].items():
        dp[n][i+a,j+b] = min(dp[n-1][i+a,j+b],value+c)

ans = INF
for (i,j),value in dp[N].items():
    if i == j == 0:
        continue
    if i*Mb == j*Ma:
        ans = min(ans, value)
print(ans if ans != INF else -1)

N, Ma, Mb = map(int, input().split())
Med = [tuple(map(int, input().split())) for _ in range(N)]
N *= 100
INF = 100000
dp = [[INF]*N+1 for _ in range(N+1)] 
dp[0][0] = 0 
from itertools import product as prd
R = lambda x:reversed(range(x,N+1))
for a,b,c in Med:
    for i,j in prd(R(a),R(b)):
        dp[i][j] = min(dp[i][j], dp[i-a][j-b]+c)

ans = INF
for i,j in prd(R(1),R(1)):
    if i*Mb == j*Ma:
        ans = min(ans, dp[i][j])
print(ans if ans != INF else -1)

import collections
import copy
INF = 10000


N, Ma, Mb = map(int, input().split())
medichine = [tuple(map(int, input().split())) for _ in range(N)]

dp = {}

dp = collections.defaultdict(lambda:INF)
dp[0,0] = 0

for a, b, c in medichine:
    dp_ = copy.copy(dp)
    for ca,cb in dp.keys():
        dp_[ca+a, cb+b] = min(dp_[ca+a, cb+b], dp[ca,cb]+c)
    dp = dp_    

ans = INF
for ca,cb in dp.keys():
    if ca == cb == 0: continue
    if ca*Mb == cb*Ma:
        ans = min(ans, dp[ca,cb])
        
print(-1 if ans == INF else ans)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Runtime Error

Accepted