Problem: Takahashi, who is a novice in competitive programming, wants to learn M algorithms. Initially, his _understanding level_ of each of the M algorithms is 0.  Takahashi is visiting a bookstore, where he finds N books on algorithms. The i-th book (1\leq i\leq N) is sold for C_i yen (the currency of Japan). If he buys and reads it, his understanding level of the j-th algorithm will increase by A_{i,j} for each j (1\leq j\leq M). There is no other way to increase the understanding levels of the algorithms.  Takahashi's objective is to make his understanding levels of all the M algorithms X or higher. Determine whether this objective is achievable. If it is achievable, find the minimum amount of money needed to achieve it.

Submission attempts (in order):
print(-1)

N, M, X = map(int, input().split())
A = []
C = []
for _ in range(N):
    CA = list(map(int, input().split()))
    C.append(CA[0])
    A.append(CA[1::])

# print(A)
# print(C)

ans_money = float('inf')
# ans_algorythm = None
for i in range(2**(N-1)):
    bit = bin(i)[2::]
    # print("bit: {}".format(bit))
    tmp_money = 0
    tmp_algorythm = [0] * M
    for j, b in enumerate(bit[::-1]):
        if b == '1':
            tmp_money += C[j]
            for k, c in enumerate(A[j]):
                tmp_algorythm[k] += c
    
    if len(list(filter(lambda x: x < X, tmp_algorythm))) == 0:
        ans_money = min(tmp_money, ans_money)
        break

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


DEBUG = True

import time

N, K = map(int, input().split())
A = [int(i)-1 for i in input().split()]

visited = [False] * N
next = A[0]
visited[0] = True
K -= 1
while not visited[next]:
    if DEBUG:
        print("K: {}, next: {}".format(K, next))
        print("visited: {}".format(visited))
        time.sleep(0.1)
    if K == 0:
        print(next+1)
        exit()
    visited[next] = True
    next = A[next]
    K -= 1

K -= 1
now = next
count = 1
next = A[next]
while now != next:
    next = A[next]
    count += 1
if DEBUG:
    print("count: {}".format(count))

K %= count

if DEBUG:
    print("now: {}, count: {}, K: {}".format(now, count, K))

while K > 0:
    if DEBUG:
        print("now: {}".format(now))
    now = A[now]
    K -= 1

print(A[now]+1)


DEBUG = False

N, M, X = map(int, input().split())
A = []
C = []
for _ in range(N):
    CA = list(map(int, input().split()))
    C.append(CA[0])
    A.append(CA[1::])

if DEBUG:
    print(A)
    print(C)

max_money = 10**5 * N + 1
ans_money = max_money
# ans_algorythm = None
for i in range(2**N):
    bit = bin(i)[2::]
    bit = bit.zfill(N)
    if DEBUG:
        print("i: {}, bit: {}".format(i, bit))
    tmp_money = 0
    tmp_algorythm = [0] * M
    for j, b in enumerate(bit):
        if b == '1':
            tmp_money += C[j]
            for k, c in enumerate(A[j]):
                tmp_algorythm[k] += c
    if DEBUG:
        print("tmp_money: {}, tmp_algorythm: {}".format(tmp_money, tmp_algorythm))
    if len(list(filter(lambda x: x < X, tmp_algorythm))) == 0:
        ans_money = min(tmp_money, ans_money)
        if DEBUG:
            print("ans_money: {}".format(ans_money))
        # break

if ans_money == max_money:
    print(-1)
else:
    print(ans_money)


Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Accepted