TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: You are given an undirected unweighted graph with N vertices and M edges that contains neither self-loops nor double edges.   Here, a _self-loop_ is an edge where a_i = b_i (1≤i≤M), and _double edges_ are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).   How many different paths start from vertex 1 and visit all the vertices exactly once?   Here, the endpoints of a path are considered visited.  For example, let us assume that the following undirected graph shown in Figure 1 is given.    Figure 1: an example of an undirected graph  The following path shown in Figure 2 satisfies the condition.    Figure 2: an example of a path that satisfies the condition  However, the following path shown in Figure 3 does not satisfy the condition, because it does not visit all the vertices.    Figure 3: an example of a path that does not satisfy the condition  Neither the following path shown in Figure 4, because it does not start from vertex 1.    Figure 4: another example of a path that does not satisfy the condition

Submission attempts (in order):
import sys
n,m = map(int,input().split())
graph = [list(input().split(" ")) for i in range(n)]

result=0

def dfs(a, list, graph,  result):
  print(list)
  if len(list) == n:
    result = result + 1

  for g in graph:
    if g[0] == a and g[1] not in list:
      list.append(g[1])
      result = dfs(g[1], list, graph, result)
    if g[1] == a and g[0] not in list:
      list.append(g[0])
      result = dfs(g[0], list, graph, result)

  return result

for g in graph:
  list = []
  if g[0] == "1":
    list.append(1)
    result += dfs("1", list, graph, 0)

print(result)


import sys
n,m = map(int,input().split())
graph = [list(input().split(" ")) for i in range(n)]

result=0

def dfs(a, list, graph,  result):
  print(list)
  if len(list) == n:
    result = result + 1

  for g in graph:
    if g[0] == a and g[1] not in list:
      list.append(g[1])
      result = dfs(g[1], list, graph, result)
    if g[1] == a and g[0] not in list:
      list.append(g[0])
      result = dfs(g[0], list, graph, result)

  return result

for g in graph:
  list = []
  if g[0] == "1":
    list.append(1)
    result += dfs("1", list, graph, 0)

print(result)


N, M = map(int, input().split())
adj_matrix = [[0]* N for _ in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    adj_matrix[a-1][b-1] = 1
    adj_matrix[b-1][a-1] = 1

def dfs(v, used):
    if not False in used:
        return 1
    
    ans = 0
    for i in range(N):
        if not adj_matrix[v][i]:
            continue
        if used[i]:
            continue
        
        used[i] = True
        ans += dfs(i, used)
        used[i] = False
    
    return ans

used = [False] * N
used[0] = True

print(dfs(0, used))

Verdicts: Runtime Error

Runtime Error

Accepted
Problem: You are given an undirected unweighted graph with N vertices and M edges that contains neither self-loops nor double edges.   Here, a _self-loop_ is an edge where a_i = b_i (1≤i≤M), and _double edges_ are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).   How many different paths start from vertex 1 and visit all the vertices exactly once?   Here, the endpoints of a path are considered visited.  For example, let us assume that the following undirected graph shown in Figure 1 is given.    Figure 1: an example of an undirected graph  The following path shown in Figure 2 satisfies the condition.    Figure 2: an example of a path that satisfies the condition  However, the following path shown in Figure 3 does not satisfy the condition, because it does not visit all the vertices.    Figure 3: an example of a path that does not satisfy the condition  Neither the following path shown in Figure 4, because it does not start from vertex 1.    Figure 4: another example of a path that does not satisfy the condition

Submission attempts (in order):
n,m=map(int,input().split())
A=[["."]*n for i in range(n)]
B=[["."]*m for i in range(m)]
for i in range(n):
  A[i]=list(input())
for i in range(m):
  B[i]=list(input())
for i in range(n-m+1):
  for j in range(n-m+1):
    a=0
    for x in range(m):
      for y in range(m):
        if A[i+x][j+y]!=B[x][y]:
          a=1
          break
    if a==0:
      print("Yes")
      exit()
print("No")

import itertools
n,m=map(int,input().split())
G=[[0]*n for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  G[a-1][b-1]=1
  G[b-1][a-1]=1
S=""
for i in range(1,n):
  S=S+str(i)
ans=0
for x in itertools.permutations(S):
  a=0
  if G[0][int(x[0])]==0:
    a=1
  for i in range(n-2):
    if G[int(x[i])][int(x[i+1])]==0:
      a=1
  if a==0:
    ans=ans+1
print(ans)

Verdicts: Runtime Error

Accepted
Problem: You are given an undirected unweighted graph with N vertices and M edges that contains neither self-loops nor double edges.   Here, a _self-loop_ is an edge where a_i = b_i (1≤i≤M), and _double edges_ are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).   How many different paths start from vertex 1 and visit all the vertices exactly once?   Here, the endpoints of a path are considered visited.  For example, let us assume that the following undirected graph shown in Figure 1 is given.    Figure 1: an example of an undirected graph  The following path shown in Figure 2 satisfies the condition.    Figure 2: an example of a path that satisfies the condition  However, the following path shown in Figure 3 does not satisfy the condition, because it does not visit all the vertices.    Figure 3: an example of a path that does not satisfy the condition  Neither the following path shown in Figure 4, because it does not start from vertex 1.    Figure 4: another example of a path that does not satisfy the condition

Submission attempts (in order):
import itertools

n,m=map(int,input().split())
g=[list(map(int,input().split())) for _ in range(m)]
v=list(itertools.permutations(range(1,n+1)))
print(v)

ans=0

for x in v:
    tf=True
    if x[0]!=1:
        tf=False
    else:
        for i in range(n-1):
            if not ([x[i],x[i+1]] in g or [x[i+1],x[i]] in g):
                tf=False
                break
    if tf:
        ans+=1
print(ans)

import itertools

n,m=map(int,input().split())
g=[list(map(int,input().split())) for _ in range(m)]
v=list(itertools.permutations(range(1,n+1)))

ans=0

for x in v:
    tf=True
    if x[0]!=1:
        tf=False
    else:
        for i in range(n-1):
            if not ([x[i],x[i+1]] in g or [x[i+1],x[i]] in g):
                tf=False
                break
    if tf:
        ans+=1
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: You are given an undirected unweighted graph with N vertices and M edges that contains neither self-loops nor double edges.   Here, a _self-loop_ is an edge where a_i = b_i (1≤i≤M), and _double edges_ are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).   How many different paths start from vertex 1 and visit all the vertices exactly once?   Here, the endpoints of a path are considered visited.  For example, let us assume that the following undirected graph shown in Figure 1 is given.    Figure 1: an example of an undirected graph  The following path shown in Figure 2 satisfies the condition.    Figure 2: an example of a path that satisfies the condition  However, the following path shown in Figure 3 does not satisfy the condition, because it does not visit all the vertices.    Figure 3: an example of a path that does not satisfy the condition  Neither the following path shown in Figure 4, because it does not start from vertex 1.    Figure 4: another example of a path that does not satisfy the condition

Submission attempts (in order):
n , m = map(int , input().split())
edge = [[] for _ in range(m) ]
#print(edge)
for _ in range(m):
    a , b = map(int , input().split())
    a -= 1 ; b -= 1
    edge[a].append(b)
    edge[b].append(a)
print(edge)

def DFS(s):
    global visited
    #ret=1 if all(visited) else 0
    if all(visited):
        ret = 1
    else:
        ret = 0
    for e in edge[s]:
        print("e",e)
        if visited[e] == True:
            continue
        visited[e] = True
        ret += DFS(e)
        visited[e] = False
    return ret

visited = [False] * n
visited[0] = True
print(DFS[0])

n , m = map(int , input().split())
edge = [[] for _ in range(m) ]
#print(edge)
for _ in range(m):
    a , b = map(int , input().split())
    a -= 1 ; b -= 1
    edge[a].append(b)
    edge[b].append(a)
#print(edge)

def DFS(s):
    global visited
    #ret=1 if all(visited) else 0
    if all(visited):
        ret = 1
    else:
        ret = 0
    for e in edge[s]:
        #print("e",e)
        if visited[e] == True:
            continue
        visited[e] = True
        ret += DFS(e)
        visited[e] = False
    return ret

visited = [False] * n
visited[0] = True
print(DFS[0])

n , m = map(int , input().split())
edge = [[] for _ in range(n) ]
#print(edge)
for _ in range(m):
    a , b = map(int , input().split())
    a -= 1 ; b -= 1
    edge[a].append(b)
    edge[b].append(a)
#print(edge)

def DFS(s):
    global visited
    #ret=1 if all(visited) else 0
    if all(visited):
        ret = 1
    else:
        ret = 0
    for e in edge[s]:
        #print("e",e)
        if visited[e] == True:
            continue
        visited[e] = True
        ret += DFS(e)
        visited[e] = False
    return ret

ans = 0
visited = [False] * n
visited[0] = True
ans += DFS(0)
print(ans)


Verdicts: Runtime Error

Runtime Error

Accepted
Problem: You are given an undirected unweighted graph with N vertices and M edges that contains neither self-loops nor double edges.   Here, a _self-loop_ is an edge where a_i = b_i (1≤i≤M), and _double edges_ are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).   How many different paths start from vertex 1 and visit all the vertices exactly once?   Here, the endpoints of a path are considered visited.  For example, let us assume that the following undirected graph shown in Figure 1 is given.    Figure 1: an example of an undirected graph  The following path shown in Figure 2 satisfies the condition.    Figure 2: an example of a path that satisfies the condition  However, the following path shown in Figure 3 does not satisfy the condition, because it does not visit all the vertices.    Figure 3: an example of a path that does not satisfy the condition  Neither the following path shown in Figure 4, because it does not start from vertex 1.    Figure 4: another example of a path that does not satisfy the condition

Submission attempts (in order):
import itertools
import collections

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

a = [list(sorted(map(int, input().split()))) for i in range(m)]
a.sort()

cnt = 0

for i in itertools.permutations(range(2, n + 1), (n - 1)):
    li = [1] + list(i)
    for edge in zip(li, li[1:]):
        print(edge)
    if sum(list(sorted(edge)) in a for edge in zip(li, li[1:])) == n - 1:
       cnt += 1

print(cnt)


import itertools
import collections

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

a = [list(sorted(map(int, input().split()))) for i in range(m)]
a.sort()

cnt = 0

for i in itertools.permutations(range(2, n + 1), (n - 1)):
    li = [1] + list(i)
    if sum(list(sorted(edge)) in a for edge in zip(li, li[1:])) == n - 1:
        cnt += 1

print(cnt)


Verdicts: Wrong Answer

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


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

Verdicts: Wrong Answer

Accepted
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())
abc = [list(map(int, input().split())) for i in range(n)]

inf = float('inf')

dp = [[inf for i in range(n*10)] for i in range(n*10)]

for i in range(n):
    for j in range(i*10,-1):
        for k in range(i*10,-1):
            if dp[j][k]!=inf:
                dp[j + abc[i][0]][k + abc[i][1]] =min(dp[j+abc[i][0]][k+abc[i][1]],dp[j][k]+abc[i][2])
    dp[abc[i][0] - 1][abc[i][1] - 1]= min(dp[abc[i][0] - 1][abc[i][1] - 1], abc[i][2])

ans = inf

for j in range(n*10):
    for k in range(n*10):
        if ma*(k+1)==mb*(j+1):
            ans = min(ans,dp[j][k])

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


n,ma,mb = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(n)]

inf = float('inf')

dp = [[inf for i in range(n*10)] for i in range(n*10)]

for i in range(n):
    for j in range(i*10-1,-1,-1):
        for k in range(i*10-1,-1,-1):
            if dp[j][k]!=inf:
                dp[j + abc[i][0]][k + abc[i][1]] =min(dp[j+abc[i][0]][k+abc[i][1]],dp[j][k]+abc[i][2])
    dp[abc[i][0] - 1][abc[i][1] - 1]= min(dp[abc[i][0] - 1][abc[i][1] - 1], abc[i][2])

ans = inf

for j in range(n*10):
    for k in range(n*10):
        if ma*(k+1)==mb*(j+1):
            ans = min(ans,dp[j][k])

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

Verdicts: Wrong Answer

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

INF = 10 ** 8

lst = [[INF] * 401 for i in range(401)]
lst[0][0] = 0

for _ in range(N):
    a, b, c = map(int, input().split())
    for i in range(a, 401):
        for j in range(b, 401):
            if lst[i][j] == INF:
                pass
            else:
                lst[i][j] = min(lst[i][j], lst[i - a][j - b] + c)

ans = INF
n = 400 // max(Ma, Mb)
for i in range(1, n + 1):
    ans = min(ans, lst[Ma * i][Mb * i])

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



import numpy as np

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

dp = np.zeros((U + 1, U + 1), dtype = np.int64)
temp = np.zeros_like(dp)

INF = 10 ** 18
dp += INF
dp[0, 0] = 0

for _ in range(N):
    a, b, c = map(int, input().split())
    temp[:] = dp.copy()
    temp[a:, b:] = np.minimum(temp[a:, b:], dp[:-a, :-b] + c)
    dp = temp 

answer = INF
for t in range(1, 401):
    a = Ma * t
    b = Mb * t
    if max(a, b) >= U: 
        break
    answer = min(answer, dp[a, b])

if answer == INF:
    answer = -1

print (answer)


Verdicts: Wrong Answer

Accepted
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 = (list)(map(int, input().split()))
N_max = 40
abmax = 10
l = []
inf = 10**6
dp = [[[inf]*401 for _ in range(401)] for _ in range(40)]


for _ in range(N):
    l.append((list)(map(int, input().split())))

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

for i in range(N):
    for ca in range(401):
        for cb in range(401):
            if dp[i][ca][cb] != inf:
                dp[i+1][ca][cb] = min(dp[i+1][ca][cb], dp[i][ca][cb])
                t_a = l[i][0]
                t_b = l[i][1]
                dp[i+1][ca+t_a][cb+t_b] =\
                    min(dp[i+1][ca+t_a][cb+t_b], dp[i][ca][cb]+l[i][2])

ans = inf
for i in range(401):
    for j in range(401):
        if i*Mb == j*Ma:
            ans = min(ans, dp[N][i][j])

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


N, Ma, Mb = (list)(map(int, input().split()))
l = []
inf = 10**6
dp = [[[inf]*401 for _ in range(401)] for _ in range(41)]


for _ in range(N):
    l.append((list)(map(int, input().split())))

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

for i in range(N):
    for ca in range(401):
        for cb in range(401):
            if dp[i][ca][cb] != inf:
                dp[i+1][ca][cb] = min(dp[i+1][ca][cb], dp[i][ca][cb])
                t_a = l[i][0]
                t_b = l[i][1]
                dp[i+1][ca+t_a][cb+t_b] =\
                    min(dp[i+1][ca+t_a][cb+t_b], dp[i][ca][cb]+l[i][2])

ans = 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 == inf:
    ans = -1
print(ans)


Verdicts: Runtime Error

Accepted
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):
INF = float('inf')
N, Ma, Mb = map(int, input().split())
a, b, c = [None] * N, [None] * N, [None] * N
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())
dp = [[[INF] * (10*N+1) for j in range(10*N+1)] for i in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
    for j in range(10*N+1):
        for k in range(10*N+1):
            if j >= a[i] and k >= b[i]:
                dp[i+1][j][k] = min(dp[i][j][k], dp[i][j-a[i]][k-b[i]]+c[i])
ans = INF
for i in range(1, 10*N+1):
    for j in range(1, 10*N+1):
        if i * Mb == j * Ma and ans < dp[N][i][j]:
            ans = dp[N][i][j]
ans = -1 if ans == INF else ans
print(ans)

from collections import defaultdict
N, Ma, Mb = map(int, input().split())
INF, MAX = 1000000000, 10 * N + 1
dp = defaultdict(lambda : INF)
dp[(0, 0)] = 0
for i in range(N):
    a, b, c = map(int, input().split())
    predp = dp.copy()
    for ab, v in predp.items():
        _a, _b = ab
        dp[(_a+a, _b+b)] = min(dp[(_a+a, _b+b)], v+c)
ans = INF
for i in range(1, N+1):
    ans = min(ans, dp[(Ma*i, Mb*i)])
ans = -1 if ans == INF else ans
print(ans)


Verdicts: Wrong Answer

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


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] > v + c :
                pd[nk] = v + c
        else:
            pd[nk] = v + 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)


Verdicts: Wrong Answer

Accepted
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())
INF = 10000
maxa = 0
maxb = 0
maxc = 0
medi = []
for i in range(n):
    a, b, c = map(int,input().split())
    maxa = max(maxa, a)
    maxb = max(maxb, b)
    maxc = max(maxc, c)
    medi.append([a, b, c])
dp = [[[INF for k in range(maxb+1)] for j in range(maxa+1)] for i in range(n+1)]
dp[0][0][0] = 0
for i in range(n):
    for x in range(maxa+1):
        for y in range(maxb+1):
            if dp[i][x][y] == INF:
                continue
            dp[i + 1][x][y] = min(dp[i + 1][x][y], dp[i][x][y])
            a, b, c = medi[i]
            if x + a <= maxa and y + b <= maxb:
                dp[i + 1][x + a][y + b] = min(dp[i][x][y] + c, dp[i + 1][x + a][y + b])

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

print(-1)

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

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

Verdicts: Wrong Answer

Wrong Answer

Accepted
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):
import numpy as np
n, ma, mb = map(int, input().split())
r = 10 * n + 6
inf = 10**5
dp = np.full((n+1, r, r), inf)
dp[0][0][0] = 0
for i in range(n):
    a, b, c = map(int, input().split())
    for j in range(r):
        for k in range(r):
            if j + a < r and k + b < r:
                dp[i+1][j+a][k+b] = min(
                    dp[i][j][k] + c, dp[i][j+a][k+b]
                )
            dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])

ans = inf
x, y = 0, 0
for i in range(1, n+1):
    while True:
        x += ma
        y += mb
        if x < r and y < r:
            ans = min(ans, dp[i][x][y])
        else:
            break
if ans == inf:
    print(-1)
else:
    print(int(ans))

import numpy as np
n, ma, mb = map(int, input().split())
r = 10 * n + 6
inf = 10**5
dp = np.full((n+1, r, r), inf)
dp[0][0][0] = 0
for i in range(n):
    a, b, c = map(int, input().split())
    dp[i+1][a:, b:] = np.minimum(
        dp[i][:r-a, :r-b] + c, dp[i][a:, b:]
    )
    dp[i+1] = np.minimum(dp[i+1], dp[i])

ans = inf
x, y = 0, 0
while True:
    x += ma
    y += mb
    if x < r and y < r:
        ans = min(ans, dp[n][x][y])
    else:
        break
if ans == inf:
    print(-1)
else:
    print(int(ans))

Verdicts: Wrong Answer

Accepted
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):
print(-1)

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

mix=set([(0,0)])
ans=10**9
cost={(0,0):0}
for i in range(N):
    a,b,c=list(map(int,input().split()))
    tmp=mix.copy()
    for x in tmp:
        d=x[0]+a
        e=x[1]+b
        f=min(cost.get((d,e),10**9),cost[x]+c)
        cost[(d,e)]=f
        mix.add((d, e))
        if d*Mb==e*Ma and f<ans:
            ans=f
print(cost)
print(mix)
if ans==10**9:
    ans=-1
print(ans)

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

mix=set([(0,0)])
ans=10**9
cost={(0,0):0}
for i in range(N):
    a,b,c=list(map(int,input().split()))
    tmp=mix.copy()
    tmp2=cost.copy()
    for x in tmp:
        d=x[0]+a
        e=x[1]+b
        f=min(tmp2.get((d,e),10**9),tmp2[x]+c)
        cost[(d,e)]=f
        mix.add((d, e))
        if d*Mb==e*Ma and f<ans:
            ans=f
"""
print(cost)
print(mix)
"""
if ans==10**9:
    ans=-1
print(ans)

Verdicts: Wrong Answer

Wrong Answer

Accepted
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, f.readline().split())
a, b, c = [], [], []
for _ in range(n):
    at, bt, ct = map(int, f.readline().split())
    a.append(at)
    b.append(bt)
    c.append(ct)
    
dp = [[float('inf') for _ in range(n*mb + 1)] for _ in range(n*ma + 1)]
dp[0][0] = 0
used = [[0, 0]]

for i in range(n):
    add_used = []
    for at, bt in used:
        if at+a[i] <= n and bt+b[i] <= n:
            if dp[at+a[i]][bt+b[i]] == float('inf'):
                add_used.append([at+a[i], bt+b[i]])
            
            dp[at+a[i]][bt+b[i]] = min(dp[at][bt]+c[i], dp[at+a[i]][bt+b[i]])
        
    used += add_used

if dp[-1][-1] == float('inf'):
    print(-1)
else :
    print(dp[-1][-1])

import copy
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())
   
dp = [[float('inf')] * (sum(b)+1) for _ in range(sum(a)+1)]
dp[0][0] = 0
step = set([(0, 0)])

for i in range(n):
    ai, bi = a[i], b[i]

    s = step.copy()
    tempdp = copy.deepcopy(dp)
    for si in s: 
        if dp[si[0]+ai][si[1]+bi] > dp[si[0]][si[1]] + c[i]:
            tempdp[si[0]+ai][si[1]+bi] = dp[si[0]][si[1]] + c[i]
            step.add((si[0]+ai, si[1]+bi))
        
    dp = tempdp[:]
#28 20

ans = float('inf')
for i in range(1, min(sum(a)//ma, sum(b)//mb)+1):
    ans = min(ans, dp[ma*i][mb*i])
    
if ans == float('inf'): print(-1)
else : print(ans)

Verdicts: Runtime Error

Accepted
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):
global N
global Nlist
global Ma
global Mb
global minicost
minicost = 10000000
N, Ma, Mb = map(int,input().split()) 
Nlist = []
for i in range(N):
    a,b,c = map(int,input().split())
    Nlist.append([a,b,c])
def dvector(Masum,Mbsum,cost,vector):
    print(vector)
    global Ma
    global Mb
    global Nlist
    global minicost
    if len(vector) == len(Nlist):
        return 0
    dvector(Masum,Mbsum,cost,vector+[0])
    Masum+= Nlist[len(vector)-1][0]
    Mbsum+= Nlist[len(vector)-1][1]
    cost += Nlist[len(vector)-1][2]
    if Mbsum > 0:
        if Masum/Mbsum == Ma/Mb:
            if minicost > cost:
                minicost = cost
    print(vector,cost,minicost)
    if cost < minicost:
        dvector(Masum,Mbsum,cost,vector+[1])
    return 0
    
dvector(0,0,0,[])
if minicost == 10000000:
    print("-1")
else:
    print(minicost)

global N
global Nlist
global Ma
global Mb
global minicost
minicost = 10000000
N, Ma, Mb = map(int,input().split()) 
Nlist = []
for i in range(N):
    a,b,c = map(int,input().split())
    Nlist.append([a,b,c])

def dvector(Masum,Mbsum,cost,vector):
    global Ma
    global Mb
    global Nlist
    global minicost
    if len(vector) == len(Nlist):
        return 0
    dvector(Masum,Mbsum,cost,vector+[0])
    Masum+= Nlist[len(vector)-1][0]
    Mbsum+= Nlist[len(vector)-1][1]
    cost += Nlist[len(vector)-1][2]
    if Mbsum > 0:
        if Masum/Mbsum == Ma/Mb:
            if minicost > cost:
                minicost = cost
    if cost < minicost:
        dvector(Masum,Mbsum,cost,vector+[1])
    return 0
    
dvector(0,0,0,[])
if minicost == 10000000:
    print("-1")
else:
    print(minicost)

Verdicts: Wrong Answer

Accepted
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 = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(n)]
dp = [[float("inf") for i in range(10*n+1)] for i in range(10*n+1)]
dp[0][0],ans = 0,float("inf")
for i in range(n):
	for j in range(10*(i-1)+1):
		for k in range(10*(i-1)+1):
			if dp[j][k]!=float("inf"): dp[j+x[i][0]][k+x[i][1]] = min(dp[j][k]+x[i][2],dp[j+x[i][0]][k+x[i][1]])
for i in range(ma,10*n+1,ma):
	if i*mb//ma<=10*n: ans=min(ans,dp[i][i*mb//ma])
if ans==float("inf"): print(-1)
else: print(ans)

n, ma, mb = map(int, input().split())
INF = float("inf")
dp = [[[INF for i in range(10*n+1)] for i in range(10*n+1)] for i in range(n+1)]
dp[0][0][0],ans = 0,INF
for i in range(1,n+1):
    a,b,c = (int(l) for l in input().split())
    for j in range(10*(i-1)+1):
        for k in range(10*(i-1)+1):
            if dp[i-1][j][k] != INF:
              dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k])
              dp[i][j+a][k+b] = min(dp[i][j+a][k+b], dp[i-1][j][k]+c)
for i in range(ma,10*n+1,ma):
	if i*mb//ma<=10*n: ans=min(ans,dp[n][i][i*mb//ma])
if ans==INF: print(-1)
else: print(ans)

Verdicts: Wrong Answer

Accepted
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 = [int(i) for i in input().split()]
lst = [[int(i) for i in input().split()] for _ in range(n)]
lst.sort(key=lambda x: x[2])

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


for i in lst:
    k, v = i[0] * mb - i[1] * ma, i[2]
    l = [[j, dic[j]] for j in dic]
    for item in l:
        push(item[0] + k, item[1] + v)
    push(k, v)

print(dic[0] if 0 in dic else '-1')

n, ma, mb = [int(i) for i in input().split()]
lst = [[int(i) for i in input().split()] for _ in range(n)]
lst.sort(key=lambda x: x[2])
dic = {}
def push(k,v):
    if k in dic:
        dic[k] = min(dic[k],v)
    else:
        dic[k] = v


for i in lst:
    k, v = i[0] * mb - i[1] * ma, i[2]
    l = [[j, dic[j]] for j in dic]
    for item in l:
        push(item[0] + k, item[1] + v)
    push(k, v)

print(dic[0] if 0 in dic else '-1')

Verdicts: Runtime Error

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

dp = [[10**18 for _ in range(401)] for _ in range(401)]

dp[0][0]=0
for i in range(N):
    a,b,c=map(int,input().split())
    for ca in range(361, -1, -1):
        for cb in range(361, -1, -1):
            dp[ca+a][cb+b] = min(dp[ca+a][cb+b],dp[ca][cb]+c)
        

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

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

dp = [[[10**18 for _ in range(401)] for _ in range(401)] for _ in range(N+1)]

dp[0][0][0]=0
for i in range(N):
    for ca in range(i * 10):
        for cb in range(i * 10):
            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 = 10**18
for ca in range(401):
    for cb in range(401):
        if not ca*Mb == cb*Ma or ca == 0:
            continue
        if ans > dp[N][ca][cb]:
            ans = dp[N][ca][cb]
        
if ans == 10**18:
    print(-1)
else:
    print(ans)


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

dp = [[10**18 for _ in range(401)] for _ in range(401)]

dp[0][0]=0
for i in range(N):
    a,b,c=map(int,input().split())
    for ca in range(i * 10, -1, -1):
        for cb in range(i * 10, -1, -1):
            dp[ca+a][cb+b] = min(dp[ca+a][cb+b],dp[ca][cb]+c)

ans = 10**18
for ca in range(401):
    for cb in range(401):
        if not ca*Mb == cb*Ma or ca == 0:
            continue
        if ans > dp[ca][cb]:
            ans = dp[ca][cb]
        
if ans == 10**18:
    print(-1)
else:
    print(ans)


Verdicts: Wrong Answer

Wrong Answer

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


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 = [[INF] * M for k in range(M)]
s = set()
min_cost[0][0] = 0
s.add((0, 0))

for k in range(n):
    ss = set(s)
    for i, j in reversed(sorted(s)):
        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]]:
                ss.add((i + a[k], j + b[k]))
                min_cost[i + a[k]][j + b[k]] = cc
    s = ss

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)


Verdicts: Runtime Error

Accepted