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: Accepted

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

s = 400

DP = [[0] * (s+1) for i in range(s+1)]
C = [[float("inf")] * (s+1) for i in range(s+1)]
DP[0][0] = 1
C[0][0] = 0

for k in range(n):
    for i in range(s, -1, -1):
        for j in range(s, -1, -1):
            x = i-A[k][0]
            y = j-A[k][1]
            # print(x,y,i,j)
            if x >= 0 and y >= 0 and DP[x][y] == 1 and C[x][y] + A[k][2] < C[i][j]:
                C[i][j] = C[x][y] + A[k][2]
                DP[i][j] = 1
            # print(DP)

ans = float("inf")
ma0 = ma
mb0 = mb
while ma <= s and mb <= s:
    if DP[ma][mb] == 1:
        ans = min(ans, C[ma][mb])
    ma += ma0
    mb += mb0

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

Submission status: Accepted

Solution code:
inf = float("inf")
N, Ma, Mb = map(int, input().split())
ABC = []
for _ in range(N):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
dp = [[inf] * 420 for _ in range(420)]
dp[0][0] = 0
for a, b, c in ABC:
    for i in range(410, -1, -1):
        for j in range(410, -1, -1):
            if dp[i][j] < inf:
                dp[i+a][j+b] = min(dp[i+a][j+b], dp[i][j] + c)
ans = inf
n = 1
while max(Ma * n, Mb * n) < 420:
    ans = min(ans, dp[Ma * n][Mb * n])
    n += 1
print(ans if ans < inf else -1)

Submission status: Accepted

Solution code:
n,ma,mb=map(int,input().split())
ab=[[[10**6]*401 for _ in range(401)] for _ in range(n+1)]
ab[0][0][0]=0

for p in range(1,n+1):
    a,b,c=map(int,input().split())
    for i in range(400):
        for j in range(400):
            ab[p][i][j]=min(ab[p][i][j],ab[p-1][i][j])
            if i+a<=400 and j+b<=400:
                ab[p][i+a][j+b]=min(ab[p][i+a][j+b],ab[p-1][i][j]+c)

ans=10**6-1
for i in range(401):
    for j in range(401):
        if i!=0 and j!=0:
            if i*mb==j*ma:
                ans=min(ans,ab[n][i][j])

if ans==10**6-1:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N, Ma, Mb = map(int, input().split())
dp = [{} for i in range(N+1)]
dp[0][(0, 0)] = 0
for i in range(N):
  a, b, c = map(int, input().split())
  for p, q in dp[i]:
    if (p, q) not in dp[i+1]: dp[i+1][(p, q)] = 100000
    dp[i+1][(p, q)] = min(dp[i+1][(p, q)], dp[i][(p, q)])
    if (p+a, q+b) not in dp[i+1]: dp[i+1][(p+a, q+b)] = 100000
    dp[i+1][(p+a, q+b)] = min(dp[i+1][(p+a, q+b)], dp[i][(p, q)]+c)
#print(dp[N])
rs = []
for k in range(1, 10000):
  if (k*Ma, k*Mb) in dp[N]:
    r = dp[N][(k*Ma, k*Mb)]
    rs.append(r)
if len(rs) == 0:
  print(-1)
else:
  r = min(rs)
  print(r)

Submission status: Accepted

Solution code:
def main():
    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())
    
    dp = [[[float('inf')] * 401 for _ in range(401)] for _ in range(41)]
    dp[0][0][0] = 0
    for i in range(N):
        for j in range(N*10+1):
            for k in range(N*10+1):
                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+a[i]][k+b[i]] = min(dp[i+1][j+a[i]][k+b[i]],dp[i][j][k]+c[i])

    ans = float('inf')
    for i in range(1,N*10+1):
        for j in range(1,N*10+1):
            if Ma * j == Mb * i:
                ans = min(ans,dp[N][i][j])

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

    print(ans)

main()

Submission status: Accepted

Solution code:
def main():

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

    cur = dict()
    cur[(0, 0)] = 0
    for i in range(N):
        temp = cur.copy()
        for p in cur:
            a, b = p[0]+drug[i][0], p[1]+drug[i][1]

            if (a, b) not in temp:
                temp[(a, b)] = cur[p] + drug[i][2]
            else:
                temp[(a, b)] = min(temp[(a, b)], cur[p]+drug[i][2])
        cur = temp

    # print(cur)
    min_c = float('inf')
    for p in cur:
        if p != (0, 0) and p[0]*Mb == p[1]*Ma:
            min_c = min(min_c, cur[p])
    if min_c == float('inf'):
        return -1
    else:
        return min_c

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,ma,mb=map(int,input().split())
med=[]
for i in range(n):
    a,b,c=map(int,input().split())
    med.append((a,b,c))
INF=10000
dp=[[[INF]*401 for j in range(401)] for i in range(n+1)]
dp[0][0][0]=0
for i in range(n):
    for a in range(401):
        for b in range(401):
            if dp[i][a][b]!=INF:
                dp[i+1][a+med[i][0]][b+med[i][1]]=min(dp[i+1][a+med[i][0]][b+med[i][1]],dp[i][a][b]+med[i][2])
                dp[i+1][a][b]=min(dp[i+1][a][b],dp[i][a][b])
minc=INF
for a in range(1,401):
    for b in range(1,401):
        if a*mb==b*ma:
            minc=min(dp[n][a][b],minc)
if minc==INF:
    print(-1)
else:
    print(minc)

Submission status: Accepted

Solution code:
n,ma,mb=map(int,input().split())
abc=[]
for i in range(n):
    abc.append([int(j) for j in input().split()])
from operator import itemgetter
abc.sort(key=itemgetter(2))

dp=[[10**18 for i in range(401)]for j in range(401)]
dp[0][0]=0

p,q=0,0
for a,b,c in abc:
    for j in reversed(range(q+1)):
        for i in range(p+1):
            if dp[i][j]==10**18:
                continue
            else:
                dp[i+a][j+b]=min(dp[i+a][j+b],dp[i][j]+c)
    p+=a
    q+=b

ans=1145141919
i=1
while ma*i<401 and mb*i<401:
    ans=min(ans,dp[ma*i][mb*i])
    i+=1
if ans==1145141919:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
INF = float('inf')
n, ma, mb = map(int, input().split())
cmax = n * 10
t = [[INF] * (cmax + 1) for _ in range(cmax + 1)]
for _ in range(n):
  a, b, c = map(int, input().split())
  for aa in range(cmax, 0, -1):
    for bb in range(cmax, 0, -1):
      if t[aa][bb] == INF:
        continue
      t[aa + a][bb + b] = min(t[aa + a][bb + b], t[aa][bb] + c)
  t[a][b] = min(t[a][b], c)
result = INF
for a in range(1, cmax):
  for b in range(1, cmax):
    if a * mb == b * ma:
      result = min(result, t[a][b])
if result == INF:
  result = -1
print(result)

Submission status: Accepted

Solution code:
INF = float('inf')
n, ma, mb = map(int, input().split())
ccmax = n * 10
t = [[INF] * (ccmax + 1) for _ in range(ccmax + 1)]
for _ in range(n):
  a, b, c = map(int, input().split())
  for aa in range(ccmax, 0, -1):
    taa = t[aa]
    for bb in range(ccmax, 0, -1):
      if taa[bb] == INF:
        continue
      if t[a + aa][b + bb] > c + taa[bb]:
        t[a + aa][b + bb] = c + taa[bb]
  if t[a][b] > c:
    t[a][b] = c
result = INF
for a in range(1, ccmax):
  ta = t[a]
  for b in range(1, ccmax):
    if a * mb == b * ma and ta[b] < result:
      result = ta[b]
if result == INF:
  result = -1
print(result)

Submission status: Accepted

Solution code:
INF = float('inf')
MAXAB = 10
n, ma, mb = map(int, input().split())
t = [[INF] * (n * MAXAB + 1) for _ in range(n * MAXAB + 1)]
t[0][0] = 0
for _ in range(n):
  a, b, c = map(int, input().split())
  for aa in range(n * MAXAB, -1, -1):
    for bb in range(n * MAXAB, -1, -1):
      if t[aa][bb] == INF:
        continue
      if t[a + aa][b + bb] > t[aa][bb] + c:
        t[a + aa][b + bb] = t[aa][bb] + c
result = INF
for a in range(1, n * MAXAB + 1):
  for b in range(1, n * MAXAB + 1):
    if a * mb == b * ma and result > t[a][b]:
      result = t[a][b]
if result == INF:
  result = -1
print(result)

Submission status: Accepted

Solution code:
INF = float('inf')
n, ma, mb = map(int, input().split())
t = [[INF] * 401 for _ in range(401)]
t[0][0] = 0
for _ in range(n):
  a, b, c = map(int, input().split())
  for aa in range(400, -1, -1):
    for bb in range(400, -1, -1):
      if t[aa][bb] == INF:
        continue
      if t[a + aa][b + bb] > t[aa][bb] + c:
        t[a + aa][b + bb] = t[aa][bb] + c
result = INF
for a in range(400, 0, -1):
  for b in range(400, 0, -1):
    if a * mb == b * ma and t[a][b] < result:
      result = t[a][b]
if result == INF:
  result = -1
print(result)

Submission status: Accepted

Solution code:
nmax, abmax, inf = 40, 10, 1000000

dp = [[[inf] * (nmax * abmax + 1) for _ in range(nmax * abmax + 1)] for _ in range(nmax + 1)]

n, ma, mb = map(int, input().split())

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

for i in range(n):
  a, b, c = map(int, input().split())
  dpi = dp[i]
  dpi1 = dp[i + 1]
  for ca in range(0, 401):
    for cb in range(0, 401):
      if dpi[ca][cb] == inf:
        continue
      dpi1[ca][cb] = min(dpi1[ca][cb], dpi[ca][cb])
      dpi1[ca + a][cb + b] = min(dpi1[ca + a][cb + b], dpi[ca][cb] + c)

ans = inf
dpn = dp[n]
for ca in range(1, 401):
  for cb in range(1, 401):
    if ca * mb == cb * ma:
      ans = min(ans, dpn[ca][cb])

if ans == inf:
  ans = -1

print(ans)

Submission status: Accepted

Solution code:
import sys
inf = float('inf')
n, ma, mb = map(int, input().split())
t = [[inf] * 401 for _ in range(401)]
t[0][0] = 0
for _ in range(n):
  a, b, c = map(int, input().split())
  for aa in range(400, -1, -1):
    for bb in range(400, -1, -1):
      if t[aa][bb] == inf:
        continue
      if t[a + aa][b + bb] > c + t[aa][bb]:
        t[a + aa][b + bb] = c + t[aa][bb]
result = inf
for a in range(400, 0, -1):
  for b in range(400, 0, -1):
    if a * mb == b * ma and t[a][b] < result:
      result = t[a][b]
if result == inf:
  print(-1)
else:
  print(result)

Submission status: Accepted

Solution code:
import sys
inf = float('inf')
n, ma, mb = map(int, input().split())
t = [[inf] * 401 for _ in range(401)]
for _ in range(n):
  a, b, c = map(int, input().split())
  for aa in range(400, 0, -1):
    for bb in range(400, 0, -1):
      if t[aa][bb] == inf:
        continue
      if t[a + aa][b + bb] > c + t[aa][bb]:
        t[a + aa][b + bb] = c + t[aa][bb]
  if t[a][b] > c:
    t[a][b] = c
result = inf
for a in range(400, 0, -1):
  for b in range(400, 0, -1):
    if a * mb == b * ma and t[a][b] < result:
      result = t[a][b]
if result == inf:
  print(-1)
else:
  print(result)

Submission status: Accepted

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


def solve(N: int, M_a: int, M_b: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    INF=1000000000
    NMAX=40
    ABMAX=10
    dp = [[[INF for _ in range(NMAX*ABMAX+1)] for _ in range(NMAX*ABMAX+1)] for _ in range(NMAX+1)]
    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:
                    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 = INF
    for i in range(1, NMAX*ABMAX+1):
        for j in range(1, NMAX*ABMAX+1):
            if (i*M_b == j * M_a):
                ans = min(ans, dp[N][i][j])
    
    if ans == INF:
        ans = -1
    
    print(ans)
    return


# Generated by 1.1.5 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: Accepted

Solution code:

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

    INF = 10000000

    dp = [[[INF for _ in range(10*N)] for _ in range(10*N)] for _ in range(N)]

    for i, (a, b, c) in enumerate(ABC):
        a -= 1
        b -= 1
        if i == 0:
            dp[0][a][b] = c
            continue
        for ai in range(10*N):
            for bi in range(10*N):
                if a > ai or b > bi:
                    dp[i][ai][bi] = dp[i-1][ai][bi]
                elif ai == a and bi == b:
                    dp[i][ai][bi] = min(dp[i-1][ai][bi], c)
                else:
                    dp[i][ai][bi] = min(dp[i-1][ai-a-1][bi-b-1]+c, dp[i-1][ai][bi])

    ans = INF
    for i in range(10*N):
        for j in range(10*N):
            if (i+1)*Mb == (j+1)*Ma:
                #print(i, j, dp[N-1][i][j])
                ans = min(dp[N-1][i][j], ans)
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n,ma,mb = map(int,input().split())
    dp = [[[float("inf") for _ in range(401)] for _ in range(401)] for _ in range(n+1)]
    dp[0][0][0]=0

    for i in range(1,n+1):
        a,b,c = map(int,input().split())
        for j in range(401):
            for k in range(401):
                if a<=j and b<=k:
                    dp[i][j][k] = min(dp[i-1][j][k],dp[i-1][j-a][k-b]+c)
                else:
                    dp[i][j][k] = dp[i-1][j][k]
    ans = float("inf")
    for i in range(1,401):
        for j in range(1,401):
            if i*mb == j*ma:
                ans = min(ans,dp[n][i][j])
    if ans==float("inf"):
        print(-1)
    else:
        print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

sz = 401
table = [[99999999]*(sz+1) for _ in range(sz+1)]
table[0][0] = 0
for n in range(N):
  a,b,c = map(int,input().split())
  for i in range(sz,-1,-1):
    for j in range(sz,-1,-1):
      if table[i][j]!=99999999:
        table[i+a][j+b] = min(table[i+a][j+b],table[i][j]+c)
#print(table)

ans = 99999999
i,j = Ma,Mb
while i<=sz and j<=sz:
  ans = min(ans,table[i][j])
  i += Ma
  j += Mb
print(ans if ans!=99999999 else -1)

Submission status: Accepted

Solution code:
N, Ma, Mb = map(int, input().split())
info = []
a_list = [0] * N
b_list = [0] * N
c_list = [0] * N
for i in range(N):
    a, b, c = map(int, input().split())
    a_list[i] = a
    b_list[i] = b
    c_list[i] = c

inf = 10 ** 10
a_sum = sum(a_list)
b_sum = sum(b_list)
dp = [[[inf for _ in range(b_sum + 1)] for _ in range(a_sum + 1)] for _ in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
    a, b, c = a_list[i], b_list[i], c_list[i]
    for j in range(a_sum + 1):
        for k in range(b_sum + 1):
            if j - a >= 0 and k - b >= 0:
                dp[i + 1][j][k] = min(dp[i][j - a][k - b] + c, dp[i][j][k])
            else:
                dp[i + 1][j][k] = dp[i][j][k]

x = 1
ans = inf
while Ma * x <= a_sum and Mb * x <= b_sum:
    ans = min(ans, dp[-1][Ma * x][Mb * x])
    x += 1

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, M_a: int, M_b: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    M = (max(a+b)+1)*N
    DP = [[INF]*(M) for _ in range(M)]
    for aa, bb, cc in zip(a, b, c):
        DP_next = [DP[i][:] for i in range(M)]
        DP_next[aa][bb] = min(cc, DP_next[aa][bb])
        for i in range(1, M):
            if M <= i + aa:
                break
            for j in range(1, M):
                if M <= j+bb:
                    break
                DP_next[i+aa][j+bb] = min(DP[i][j]+cc, DP_next[i+aa][j+bb])
        DP = DP_next

    m = INF
    for i in range(1, M//M_a):
        anum = M_a*i
        bnum = M_b*i
        if anum >= M or bnum >= M:
            break
        m = min(DP[anum][bnum], m)
    if m == INF:
        print(-1)
    else:
        print(m)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    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: Accepted

Solution code:
def sol():
    N, Ma, Mb = map(int, input().split())

    A = []
    B = []
    cost = []
    sumA = 0
    sumB = 0

    for _ in range(N):
        a, b, c = map(int, input().split())
        A.append(a)
        B.append(b)
        cost.append(c)
        sumA += a
        sumB += b

    dp = [[[float('inf') for _ in range(sumB * 2 + 1)] for _ in range(sumA * 2 + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 0

    for index in range(N):
        for sA in range(sumA + 1):
            for sB in range(sumB + 1):
                dp[index + 1][sA][sB] = min(
                    dp[index + 1][sA][sB],
                    dp[index][sA][sB]
                )
                dp[index + 1][sA + A[index]][sB + B[index]] = min(
                    dp[index + 1][sA + A[index]][sB + B[index]],
                    dp[index][sA][sB] + cost[index]
                )

    ans = float('inf')
    for sA in range(1, sumA):
        for sB in range(1, sumB):
            if sA * Mb == sB * Ma:
                ans = min(ans, dp[N][sA][sB])

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

sol()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

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

# 全探索だとTLEなのでDPを用いる

# dp[i][ca][cb] := i-1番目までの組み合わせでAがca,Bがcbとなるときの最小コスト

INF = float('inf')
g_max = 10 * N
dp = [[[INF for cb in range(g_max+1)] for ca in range(g_max+1)] for i in range(N+1)]

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

for i in range(N):
    for ca in range(g_max+1):
        for cb in range(g_max+1):
            if dp[i][ca][cb] == INF:
                continue
            a, b, c = d[i]
            # i番目の薬品を選ばない場合
            dp[i+1][ca][cb] = min(dp[i+1][ca][cb], dp[i][ca][cb])
            # i番目の薬品を選ぶ場合
            dp[i+1][ca+a][cb+b] = min(dp[i+1][ca+a][cb+b], dp[i][ca][cb]+c)

ans = -1
for ca in range(g_max+1):
    for cb in range(g_max+1):
        c = dp[N][ca][cb]
        if c == INF:
            continue
        if ca*Mb == cb*Ma and c > 0:
            if ans < 0 or c < ans:
                ans = c

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    a -= 2
    b -= 2
    a %= 13
    b %= 13
    if a > b:
        print("Alice")
    elif a < b:
        print("Bob")
    else:
        print("Draw")
    return

#B
def B():
    n, m = LI()
    a = SR(n)
    b = SR(m)
    if a == b:
        print("Yes")
        return
    for y in range(n - m):
        for x in range(n - m):
            if a[y][x] == b[0][0]:
                flg = 0
                for yi in range(m):
                    for xi in range(m):
                        if b[yi][xi] == a[y + yi][x + xi]:
                            continue
                        flg = 1
                        break
                    if flg:
                        break
                if flg:
                    continue
                print("Yes")
                return
    print("No")
    return

#C
def C():
    n, m = LI()
    edg = [[] for i in range(n)]
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    def dfs(i, c):
        res = 0
        c[i] = False
        if not (True in c):
            c[i] = True
            return 1
        for e in edg[i]:
            if c[e]:
                res += dfs(e, c)
        c[i] = True
        return res
    print(dfs(0, [True] * n))
    return

#D
def D():
    n, Ma, Mb = LI()
    abc = LIR(n)
    dp = [[inf] * (10 * n + 1) for i in range(10 * n + 1)]
    dp[0][0] = 0
    for a, b, c in abc:
        for i in range(10 * n, a - 1, -1):
            for j in range(10 * n, b - 1, -1):
                dp[i][j] = min(dp[i - a][j - b] + c, dp[i][j])
    ans = inf
    ma = Ma
    mb = Mb
    i = 1
    while 1:
        ans = min(ans, dp[ma * i][mb * i])
        i += 1
        if ma * i > 10 * n or mb * i > 10 * n:
            break
    if ans == inf:
        print(-1)
        return
    
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,A,B = [int(i) for i in readline().split()]
abc = [[int(i) for i in readline().split()] for j in range(n)]

ans = 10**9

d = {0:0}
for i in range(n):
    nd = {}
    a,b,c = abc[i]
    for amari,yen in d.items():
        if amari in nd:
            nd[amari] = min(nd[amari],yen)
        else:
            nd[amari] = yen

        yen += c
        amari += a*B-b*A
        if amari == 0 and yen != 0:
            ans = min(ans,yen)
        elif amari in nd:
            nd[amari] = min(nd[amari],yen)
        else:
            nd[amari] = yen
    d = nd
#    print(d,nd)

if ans == 10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,A,B = [int(i) for i in readline().split()]
abc = [[int(i) for i in readline().split()] for j in range(n)]


res1 = []
res2 = []
eq = 10**9

"""
def dfs(s,g,amari,yen,List):
    global eq
    if s != g:
        a,b,c = abc[s]
        if a*B == A*b:
            eq = min(eq,c)
            dfs(s+1,g,amari,yen,List)
        else: 
            dfs(s+1,g,amari+a*B-b*A,yen+c,List)
            dfs(s+1,g,amari        ,yen,List)
    else:
        if amari != 0:
            List.append((amari,yen))
        else:
            if yen != 0:
                eq = min(eq,yen)
        

dfs(0,n//2,0,0,res1)
dfs(n//2,n,0,0,res2)
"""

def dp(s,g):
    global eq
    d = {0:0}
    for i in range(s,g):
        nd = {}
        a,b,c = abc[i]
#        if a*B == A*b:
#            eq = min(eq,c)
#        else:
        for amari,yen in d.items():
            if amari in nd:
                nd[amari] = min(nd[amari],yen)
            else:
                nd[amari] = yen
            yen += c
            amari += a*B-b*A
            if amari == 0 and yen != 0:
                eq = min(eq,yen)
            elif amari in nd:
                nd[amari] = min(nd[amari],yen)
            else:
                nd[amari] = yen
        d = nd
#        print(d,nd)
    
    return list(d.items())


res1 = dp(0,n//2)
res2 = dp(n//2,n)


#res1.sort()
res2.sort()
#print(res1)
#print(res2)
#print(eq)

from bisect import *

ans = min(10**9,eq)

L = len(res2)
for amari,yen in res1:
    i = bisect(res2,(-amari,-10000000))
    if i < L and res2[i][0] == -amari:
        if 0 < yen+res2[i][1] < ans:
            ans = yen+res2[i][1]


if ans == 10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

# 再帰がやばいとき
# import sys
# sys.setrecursionlimit(10**9)

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e30)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

def main():
    N, Ma, Mb = l_inpl()
    abc = []
    for _ in range(N):
        abci = l_inpl()
        abc.append(abci)

    max_ab = 40*10

    # dp[i][j][k]: i番目までの薬品の組み合わせで，物質aがjグラム，物質bがkグラムのときのコスト
    dp = [[[INF for _ in range(max_ab+1)] for _ in range(max_ab+1) ] for _ in range(N+1)]
    dp[0][0][0] = 0

    for i in range(N):
        for j in range(max_ab+1):
            for k in range(max_ab+1):
                # ここでのINFはNoneと同じ意味なので
                if dp[i][j][k] == INF:
                    continue
                # i番目の薬品を加えない
                dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
                # i番目の薬品を加える
                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 = INF
    for ca in range(1, max_ab+1):
        for cb in range(1, max_ab+1):
            if ca*Mb == cb*Ma:
                ans = min(ans, dp[N][ca][cb])
    
    if ans == INF:
        print(-1)
    else:
        print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, Ma, Mb = map(int, input().split())
A = []
B = []
C = []
for _ in range(N):
    a, b, c = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
M = 401
dp = [[[float('INF') for _ in range(M)]
       for _ in range(M)] for _ in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
    for j in range(M):
        for k in range(M):
            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 + A[i]][k + B[i]
                                ] = min(dp[i + 1][j + A[i]][k + B[i]], dp[i][j][k] + C[i])
ans = float('INF')
for j in range(1, M):
    for k in range(1, M):
        if j * Mb == k * Ma:
            ans = min(ans, dp[N][j][k])
if ans == float('INF'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,ma,mb=map(int,input().split())
abc=[list(map(int,input().split())) for _ in [0]*n]

memo=[[10**4 for _ in [0]*(n*10+1)] for _ in [0]*(n*10+1)]
memo[0][0]=0

for N in range(n):
    for i in range(N*10,-1,-1):
        for j in range(N*10,-1,-1):
            a,b,c=abc[N]
            memo[i+a][j+b]=min(memo[i+a][j+b],memo[i][j]+c)

m=10**4
for i in range(1,n*10):
    for j in range(1,n*10):
        if i*mb==ma*j:
            m=min(m,memo[i][j])
if m==10**4:
    print(-1)
else:
    print(m)

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n,ma,mb = map(int,input().split())
x = [list(map(int,input().split())) for _ in range(n)]
sa = 0
sb = 0
for a,b,c in x:
    sa += a
    sb += b
dp = [[float('inf')]*(sb+1) for _ in range(sa+1)]
dp[0][0] = 0
for a,b,c in x:
    y = [[True]*(sb+1) for _ in range(sa+1)]
    for i in range(sa+1-a):
        for j in range(sb+1-b):
            if y[i][j]:
                if dp[i+a][j+b] > dp[i][j] + c:
                    dp[i+a][j+b] = dp[i][j] + c
                    y[i+a][j+b] = False
ans = float('inf')
for i in range(1,sa+1):
    for j in range(1,sb+1):
        if i*mb == j*ma:
            ans = min(ans,dp[i][j])
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:


import math
N,Ma,Mb = map(int,input().split(" "))
drags = [list(map(int,input().split(" "))) for  _ in range(N)]
INF = 10 ** 9
lim = N* 10 + 1
dp = [[[ INF for i in range(lim)] for j in range(lim)] for _ in range(N+1)]
dp[0][0][0] = 0
for num in range( N ):
    a,b,c = drags[num]
    dp[num + 1][0][0] = 0
    for i in range(0,lim): #完成した液体の aの量
        for j in range(0,lim):# bの量
            dp[num + 1][i][j]  =  dp[num][i][j]
            if i - a >= 0 and j - b >= 0:
                dp[num + 1][i ][j ] = min(dp[num][i ][j ] ,dp[num][i -a ][j -b  ]  + c)

ans = INF
for i in range(1,41):
    MA = Ma * i
    MB = Mb * i
    if MA >= lim or MB >= lim:
        break
    ans = min(ans, dp[-1][MA][MB])
if ans == INF:
    ans = -1
print(ans)