Problem:


Score : 300 points

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.

Constraints

All values in input are integers.

1\leq N, M\leq 12

1\leq X\leq 10^5

1\leq C_i \leq 10^5

0\leq A_{i, j} \leq 10^5

Input

Input is given from Standard Input in the following format:

N M X
C_1 A_{1,1} A_{1,2} \cdots A_{1,M}
C_2 A_{2,1} A_{2,2} \cdots A_{2,M}
\vdots
C_N A_{N,1} A_{N,2} \cdots A_{N,M}

Output

If the objective is not achievable, print -1; otherwise, print the minimum amount of money needed to achieve it.

Sample Input 1

3 3 10
60 2 2 4
70 8 7 9
50 2 3 9

Sample Output 1

120

Buying the second and third books makes his understanding levels of all the algorithms 10 or higher, at the minimum cost possible.

Sample Input 2

3 3 10
100 3 1 4
100 1 5 9
100 2 6 5

Sample Output 2

-1

Buying all the books is still not enough to make his understanding levels of all the algorithms 10 or higher.

Sample Input 3

8 5 22
100 3 7 5 3 1
164 4 5 2 7 8
334 7 2 7 2 9
234 4 7 2 8 2
541 5 4 3 3 6
235 4 8 6 9 7
394 3 6 1 6 2
872 8 4 3 7 2

Sample Output 3

1067



Sample input:
3 3 10
60 2 2 4
70 8 7 9
50 2 3 9


Sample output:
120

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np
n,m,x = map(int,input().split())
money_ls = [0] * n
ex_ls = [0] * n
for i in range(n):
    in_ = list(map(int, input().split()))
    money_ls[i] = in_[0]
    ex_ls[i] = in_[1:]

min_money = float('inf')


book_ls = [i for i in range(n)]
for num in range(1,n+1):
    for inds in combinations(book_ls, num):
        res = True
        money = 0
        ex_now = [0] * m
        for ind in inds:
            money += money_ls[ind]
            for i in range(m):
                ex_now[i] += ex_ls[ind][i]
        for i in range(m):
            if ex_now[i] < x:
                res = False
        if res:
            min_money = min(money, min_money)
if min_money == float('inf'):
    min_money = -1
print(min_money)

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
c = []
a = []
for i in range(n):
    lis = list(map(int, input().split()))
    c.append(lis[0])
    a.append(lis[1:])
#print(c)
#print(a)
ans = 10000000000000
for j in range(m):
    val = 0
    for i in range(n):
        val += a[i][j]
    #print(val)
    if val < x:
        print('-1')
        exit()
for i in range(2 ** n):
    flg = [True] * n
    for j in range(n):
        if i >> j & 1:
            flg[j] = False
    flg2 = True
    for j in range(m):
        val = 0
        for k in range(n):
            if flg[k] == False:
                continue
            val += a[k][j]
        #print(val)
        if val < x:
            flg2 = False
    if flg2 == True:
        val = 0
        for j in range(n):
            if flg[j] == True:
                val += c[j]
        ans = min(ans,val)
    #print(flg2)
print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())

books = [list(map(int, input().split())) for _ in range(n)]

ans = 10**10
for j in range(1 << n):
    flg = True
    for i in range(1, m+1):
        x1 = 0
        for k in range(n):
            a = books[k][i]
            if j & (1 << k):
                x1 += a

        if x1 < x:
            flg = False
            break
    if not flg:
        continue

    ans1 = 0
    for k in range(n):
        c = books[k][0]
        if j & (1 << k):
            ans1 += c

    ans = min(ans, ans1)

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

Submission status: Accepted

Solution code:
from itertools import chain,combinations
def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def isOverX(X, CA, M):
    s = [0] * (M + 1)
    for ca in CA:
        for i, a in enumerate(ca):
            s[i] += a
    if min(s[1:]) >= X:
        return s[0]
    else:
        return -1
def main():
    N, M, X = map(int, input().split())

    CA = []
    for i in range(N):
        CA.append(list(map(int, input().split())))
    
    ans = 10 ** 10
    ok = False
    for ca in powerset(CA):
        cost = isOverX(X, list(ca), M)
        if cost != -1:
            ans = min(ans, cost)
            ok = True
    print(ans if ok else -1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

# process
ans = 1300000
idx = [i for i in range(N)]
for i in range(1, N+1):
    combs = list(itertools.combinations(idx, i))
    for comb in combs:
        c = 0
        a = [0]*M
        for j in comb:
            c += C[j]
            for k in range(M):
                a[k] += A[j][k]
        if len([x for x in a if x<X]) == 0 and c < ans:
            ans = c

# output
print(-1 if ans == 1300000 else ans)

Submission status: Accepted

Solution code:
import itertools


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

c = [0]*n
a = [[0]*m for _ in range(n)]

for i in range(n):
    tmp=list(map(int,input().split()))
    c[i] = tmp.pop(0)
    a[i] = tmp

min_cost = float('inf')
for i in range(1,n+1):
    for seq in itertools.combinations(range(n),i):
        tmp_a = [0]* m
        flag = True
        sum_cost = 0
        for j in seq:
            sum_cost += c[j]
            for k in range(m):
                tmp_a[k]+= a[j][k]
                
        for k in range(m):
            if tmp_a[k] < x:
                flag = False
                break
        if flag:
            if min_cost > sum_cost:
                min_cost = sum_cost

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

Submission status: Accepted

Solution code:
from itertools import product

N, M, X = [int(x) for x in input().strip().split(" ")]
C = []
A = []

for _ in range(N):
    v = [int(x) for x in input().strip().split(" ")]
    c = v.pop(0)
    C.append(c)
    A.append(v)

sums = []
patterns = product(*[(0, 1) for _ in range(N)])
for pattern in patterns:
    price = 0
    status = [0 for _ in range(M)]
    for i, p in enumerate(pattern):
        price += C[i] * p
        for j in range(M):
            status[j] += A[i][j] * p
    if min(status) >= X:
        sums.append(price)

if len(sums) > 0:
    print(min(sums))
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import itertools

n, m, x = map(int, input().split())
a = []
c = []
for _ in range(n):
    lst = list(map(int, input().split()))
    c.append(lst[0])
    a.append(lst[1:])
ans = 1000 * 1000 * 1000 * 100
for i in itertools.product('01', repeat=n):
    cur = 0
    algs = [0] * m
    for j in range(len(i)):
        if i[j] == '1':
            cur += c[j]
            for k in range(len(a[j])):
                algs[k] += a[j][k]
    for p in algs:
        if p < x:
            break
    else:
        ans = min(ans, cur)

if ans == 1000 * 1000 * 1000 * 100:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

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

arr = []
for _ in range(n):
    i = map(int, input().split())
    arr.append((next(i), [*i]))

min_cost = float('inf')
for s in powerset(range(n)):
    cost = 0
    cur = [0]*m
    for i in s:
        cost += arr[i][0]
        for j in range(m):
            cur[j] += arr[i][1][j]

    ans = True
    for i in cur:
        if i < x:
            ans = False

    if ans:
        min_cost = min(min_cost, cost)


print(min_cost if min_cost != float('inf') else -1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import itertools
n,m,x = map(int,input().split())
ca = []
for i in range(n):
    ca.append([int(i) for i in input().split()])

comb = []
l = [i for i in range(n)]
for i in range(n+1):
    comb.append(list(itertools.combinations(l, i)))
#print(comb)

rikai = [0 for i in range(m)]
ans = pow(10, 1000)
tmp = 0
for i in range(len(comb)):
    for j in range(len(comb[i])):
        for h in comb[i][j]:
            for k in range(m):
                rikai[k] += ca[h][k+1]
            tmp += ca[h][0]
        #print(rikai)
        flag = True
        for p in rikai:
            if p < x:
                flag = False
        if ans > tmp and flag:
            ans = tmp
            #print(tmp)
            #print(i,j)
        tmp = 0
        rikai = [0 for i in range(m)]
if ans == pow(10, 1000):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

N,M,X = map(int, input().split())


text = []
for i in range(N):
    tmp = list(map(int, input().split()))
    text.append(tmp)

ans = float("inf")
for i in range(1 << N):
    tmp = [0] * (M+1)  
    flg = 0
    for j in range(N):
        if (i>>j) & 1:
            for k in range(M+1):
                tmp[k] += text[j][k]
    for l in range(1, M+1):
        if tmp[l] < X:
            flg = 1
            break
    if tmp[0] != 0 and not flg:   
        ans = min(ans, tmp[0])    

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

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = [list(map(int, input().split())) for i in range(N)]
ans = []

for i in range(2 ** N):
    buy = []
    temp = [0]*(M+1)
    for j in range(N): 
        if ((i >> j) & 1):
            buy.append(C[j][0]) 
            for k in range(M+1):
                temp[k] += C[j][k]
    
    check = 0
    for j in range(1,M+1):
        if temp[j]<X:
            check += 1
    
    if check == 0:
        ans.append(temp[0]) 

if ans==[]:
    print("-1")
else:
    print(min(ans))

Submission status: Accepted

Solution code:
N, M, X = map(int,input().split())
lines = [list(map(int,input().split())) for i in range(N)]

#print(lines)

import itertools

result = []
for n in range(1,len(lines)+1):
    for conb in itertools.combinations(lines, n):
        result.append(list(conb)) #タプルをリスト型に変換

candidates = set()
for r in result:
    #print(r)
    tmp = [0 for _ in range(M+1)]
    for line in r:
        for i, l in enumerate(line):
            tmp[i] += l
    #print(r, tmp)#, list(enumerate(r)))
    flag_add = True
    for i in range(M):
        if tmp[1+i] < X:
            flag_add = False
            break
    if flag_add:
        candidates.add(tmp[0])

ans = min(candidates) if len(candidates) != 0 else -1
print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[]
num=[]
for i in range(n):
    inp=list(map(int,input().split()))
    a.append(inp[1:])
    num.append(inp[0])
ans=10**12
flag=0
for i in range(2**n):
    f=0
    s=0
    cnt=[0]*m
    for j in range(n):
        if (i>>j & 1):
            for k in range(m):
                cnt[k]+=a[j][k]
            s+=num[j]
    for l in range(len(cnt)):
        if cnt[l]<x:
            f=1
    if f==0:
        ans=min(ans,s)
        flag=1
if flag==1:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from operator import add

ans = 10000000
N, M, X = map(int, input().split())
C = [list(map(int, input().split())) for i in range(N)]
for i in range(2 ** N):
    cnt = 0
    res = [0] * (M + 1)
    for j in range(N):
        if ((i >> j) & 1):
            res = list(map(add, res, C[j]))
    for r in res[1:]:
        if r >= X:
            cnt += 1
    if cnt == len(res[1:]) and ans > res[0]:
        ans = res[0]

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

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
c=[]
a=[]
for i in range(n):
    A=list(map(int,input().split()))
    C=A.pop(0)
    c.append(C)
    a.append(A)

num=[]
for i in range(2 **n):
  chars = list(f"{i:0{n}b}")
  chars=list(map(int,chars))
  num.append(chars)

ans=100000000000000
for cart in num:
    t=[0]*m
    money=0
    for i in range(len(cart)):
        if cart[i]==1:
            money+=c[i]
            for k in range(m):
                t[k]+=a[i][k]
    if min(t)>=x and money<ans:
        ans=money
if ans==100000000000000:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N,M,X=list(map(int,input().split()))
cost = []
tech = []
for _ in range(N):
    book=list(map(int,input().split()))
    cost.append(book[0])
    tech.append(book[1:])

ans = 10**10
for i in range(1,2**N):
    tmp = [0]*M
    c = 0
    for ind,j in enumerate("{:0>{haba}b}".format(i, haba=N)):
        if j == "0":
            continue
        c+=cost[ind]
        for k,upp in enumerate(tech[ind]):
            tmp[k]+=upp
    isOk = True
    for t in tmp:
        if t<X:
            isOk = False
            break
    if isOk:
        ans = min(ans,c)
if ans == 10**10:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import itertools

n, m, x = map(int, input().split())
c = []
a = []
for _ in range(n):
    c_a = list(map(int, input().split()))
    c.append(c_a[0])
    a.append(c_a[1:])

min_money = 10**6 * 12
for num in range(1, n + 1):
    for choices in itertools.combinations(range(n), num):
        is_ok = True
        for j in range(m):
            understand_rate = 0
            for i in choices:
                understand_rate += a[i][j]
            if understand_rate < x:
                is_ok = False
                break
        if is_ok:
            money = 0
            for i in choices:
                money += c[i]
            min_money = min(min_money, money)
if min_money == 10**6 * 12:
    print(-1)
else:
    print(min_money)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
r = [0]*M
A = []
ans = float('inf')
for _ in range(N):
    A_ = list(map(int,input().split()))
    A.append(A_)
    for i in range(M):
        r[i] += A_[i+1]
for i in range(len(r)):
    if r[i] < X:
        print(-1)
        exit()

for i in range(2**N):
    r = [0]*(M+1)
    p = 0
    for j in range(N):
        if ((i>>j)&1):
            c = A[j]
            for k in range(M+1):
                r[k] += c[k]
    for l in range(M):
        if r[l+1] <X:
            p = -1
            break
        else:
            continue
    if p == 0:
        ans = min(ans,r[0])
    else:
        continue
print(ans)

Submission status: Accepted

Solution code:

import math

def input_num():
	ls = input().strip().split(" ")
	return [int(e) for e in ls]

n,m,x = input_num()
c_ls = []
a_ls = []
for i in range(n):
	ls = input_num()
	c = ls[0]
	c_ls.append(c)
	a_ls.append(ls[1:])

# 部分和問題(NP完全)かつM<=12から、愚直法で解く

def judge(tx):
	for i in range(len(tx)):
		if tx[i] < x: return False
	return True

tc_ls = []
for i in range(2**n):
	raw_s = bin(i)[2:]
	s = "0"*(n-len(raw_s)) + raw_s
	f_ls = [e == "1" for e in s]
	tc = 0
	tx = [0 for _ in range(m)]
	for book_idx, f in enumerate(f_ls):
		if f is False: continue
		tc += c_ls[book_idx]
		tx = [tx[j]+a_ls[book_idx][j] for j in range(m)]
	if judge(tx) is True:
		tc_ls.append(tc)

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

Submission status: Accepted

Solution code:
from itertools import combinations 
n, m, x = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(n)]
ans = float("INF")
for a in range(1, n + 1):
    for i in combinations(c, a):
        point = [0] * m
        money = 0
        for j in range(a):
            for k in range(m):
                point[k] += i[j][k + 1]
            money += i[j][0]
        if min(point) >= x:
            ans = min(ans, money)

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

Submission status: Accepted

Solution code:
# C - Skill Up

N, M, X = map(int, input().split())
C, A = [], []
for _ in range(N):
    c, *a = map(int, input().split())
    C.append(c)
    A.append(a)

costs = []
def f(i, cost, points):
    if X <= min(points):
        costs.append(cost)
        return
    if N <= i:
        return
    f(i + 1, cost, points)
    tmp = [p for p in points]
    for j in range(M):
        tmp[j] += A[i][j]
    f(i + 1, cost + C[i], tmp)

f(0, 0, [0] * M)
print(min(costs) if len(costs) != 0 else -1)

Submission status: Accepted

Solution code:
import numpy as np
n,m,x = map(int,input().split())
b = []
for _ in range(n):
    c = np.array(list(map(int,input().split())))
    b.append(c)
ans = float('INF')
d = np.array([x]*m)
for i in range(2**n):
    bag = []
    for j in range(n):
        if ((i>>j) & 1):
            bag.append(b[j])
    if bag:
        c = sum(bag)
        e = c[1:] - d
        if all(i >= 0 for i in e):
            ans = min(ans, c[0])
if ans == float('INF'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
def calc_cost(book_dict, book_list, M, X):
    algo_score = [0] * M
    cost = 0
    for book_index in book_list:
        A = book_dict[book_index][1]
        cost += book_dict[book_index][0]
        for i in range(len(A)):
            algo_score[i] += A[i]
            
    for i in range(M):
        if (algo_score[i] < X):
            return -1
    
    return cost
        
    


def main():
    from itertools import combinations
    N, M, X = map(int, input().split())
    book_dict = {}
    for i in range(N):
        record = list(map(int, input().split()))
        c = 0
        A = []

        for j in range(M+1):
            if (j == 0):
                c = record[j]
            else:
                A.append(record[j])
        book_dict[i] = (c, A)

    max_cost = (10**5) * N + 1
    min_cost = max_cost
    is_possible = False
    for i in range(1, N+1, 1):
        for comb in combinations(list(range(N)), i):
            cost = calc_cost(book_dict, list(comb), M, X)
            if(cost != -1):
                is_possible = True
                min_cost = min(min_cost, cost)

    if(is_possible):
        print(min_cost)
    else:
        print(-1)            

main()

Submission status: Accepted

Solution code:

def _main():
  n_book, n_algo, target = map(int, input().split())

  book_infos = []
  for _ in range(n_book):
    book_infos.append(list(map(int, input().split())))

  ans = float('inf')
  def dp(cost, current_levels, current_book):
    if min(current_levels) >= target:
      nonlocal ans
      ans = min(ans, cost)
      return
    for index, book_info in enumerate(book_infos[current_book+1:], current_book+1):
      next_levels = [cur + up for cur, up in zip(current_levels, book_info[1:])]
      dp(cost+book_info[0], next_levels, index)

  dp(0, [0 for _ in range(n_algo)], -1)
  print(ans if ans < float('inf') else -1)
  
_main()

Submission status: Accepted

Solution code:
import numpy as np

n, m, x = map(int, input().split())
books = []
for i in range(n):
    book = list(map(int, input().split()))
    books.append(book)

min_cost = float('inf')
for i in range(2 ** n):
    cost = 0
    _sum = np.array([0] * m)
    for j in range(n):  
        if ((i >> j) & 1):  
            _sum += np.array(books[j][1:]) 
            cost += books[j][0]
    flag = 0
    for k in _sum:
        if k < x:
            flag = 1
    if flag == 0:
        min_cost = min(min_cost, cost)
if min_cost == float('inf'):
    print(-1)
else:
    print(min_cost)

Submission status: Accepted

Solution code:
import itertools

N, M, X = map(int, input().split())
C = [0 for _ in range(N)]
A = [[] for _ in range(N)]
for i in range(N):
  lis = list(map(int, input().split()))
  C[i] = lis[0]
  A[i] = lis[1:]
  
junretu = list(itertools.product([0, 1], repeat=N))
mini = [10**10]
for jun in junretu:
  count = 0
  und = [0 for _ in range(M)]
  for i, j in enumerate(jun):
    if j == 1:
      count += C[i]
      for k in range(M):
        und[k] += A[i][k]
  flag = 0
  for i in range(M):
    if und[i] >= X:
      continue
    flag = 1
    break
  if flag == 0:
    mini.append(count)
if min(mini) == 10**10:
  print(-1)
else:
  print(min(mini))

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = []
a = []
for i in range(n):
    row = list(map(int, input().split()))
    c.append(row[0])
    a.append(row[1:])

import itertools

ans = float('inf')
for r in range(n+1):
    for idxs in itertools.combinations(range(n), r=r):
        price = [0]*m
        for idx in idxs:
            for i in range(m):
                price[i] += a[idx][i]
        
        if all(price[i] >= x for i in range(m)):
            ans = min(ans, sum(c[idx] for idx in idxs))

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

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np

N,M,X = (int(x) for x in input().split())
CA = np.zeros((N,M+1))
ans = float('inf')
for i in range(N):
    CA[i] = np.array(list(map(int, input().split())))
for i in range(1,N+1):
    for x in combinations(CA,i):
        temp = np.sum(x,axis=0)
        for j in range(1,M+1):
            if temp[j] < X:
                break
        else:
            ans = min(ans,temp[0])
if ans == float('inf'):
    print('-1')
else:
    print(int(ans))

Submission status: Accepted

Solution code:
################# <-----------------  Quicksilver_ -----------------> ##################
from itertools import combinations

n,m,k=[int(i) for i in input().split()]

glob=[]

for i in range(n):
    arr=[int(i) for i in input().split()]
    glob.append(arr)

l=list(range(0,n))

mino=1000000000000000

for i in range(1,n+1):

    comb = combinations(l,i)

    r=[]
    for ijk in range(m+1):
        r.append(0)

    for z in comb:
        for fg in range(m+1):
            r[fg]=0
        for y in z:
            for yu in range(m+1):
                r[yu]+=glob[y][yu]
        if min(r[1:])>=k:
            mino=min(mino,r[0])
if mino==1000000000000000:
    print(-1)
else:
    print(mino)