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:
import itertools
import numpy as np

mNMX = map(int, input().split())
lNMX = list(mNMX)

mBook = [map(int, input().split()) for i in range(lNMX[0])]
lBook = [list(mBook[i]) for i in range(lNMX[0])]
nBook = np.array(lBook)
mPrice = 10 ** 8

for i in range(0, lNMX[0]):
    combi = itertools.combinations(range(0, lNMX[0]), i + 1)
    for c in combi:
        cBook = nBook[c, :]
        sBook = np.sum(cBook, axis = 0)
        comp = [0 if i >= lNMX[2] else -1 for i in sBook[1:]]
        if(sum(comp) == 0):
            mPrice = sBook[0] if sBook[0] < mPrice else mPrice
    
print(mPrice if mPrice <= 12 * 10 ** 5 else -1)

Submission status: Accepted

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

A = [0]*M
for i in range(N):
    for k in range(M):
        A[k] += CA[i][k+1]
for i in range(M):
    if A[i] < X:
        print('-1')
        exit() 

price = 0
ans = 10**10
A = [0]*M
for i in range(2**N):
    list = [1]*N
    for j in range(len(list)):
        if (i>>j) & 1:
            list[j] = 0
        price = 0
        A = [0]*M
        for k in range(N):
            if list[k] == 1:
                for s in range(M):
                    A[s] += CA[k][s+1]
                price += CA[k][0]
    if all(A[m] >= X for m in range(M)):
        ans = min(ans,price)
print(ans)

Submission status: Accepted

Solution code:
import itertools 
def solve():
    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)

    ans = n*1e8
    for i in range(n):
        for j in itertools.combinations(range(n), i+1):
            cnt = [0]*m
            for k in j:
                for l in range(m):
                    cnt[l] += a[k][l]
            for s in range(m):
                if cnt[s] < x:
                    break
                if s == m-1:
                    num = 0
                    for q in j:
                        num += c[q]
                    ans = min(ans, num)
    if ans == n*1e8:
        ans = -1
            
    return ans
    

print(solve())

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]

mincost = 0
for i in range(n):
    mincost += l[i][0]

s = []
for i in range(m+1):
    s.append(0)

flag = 0

for i in range(2 ** n):
    cost = 0
    for j in range(n):
        if ((i >> j) & 1):
            cost += l[j][0]
            for k in range(1, m+1):
                s[k] += l[j][k]
    b = 1
    for k in range(1, m+1):
        if s[k] < x:
            b = 0 
    if b == 1:
        flag = 1
        mincost = min(cost, mincost)
    for i in range(m+1):
        s[i] = 0

if flag == 1:
    print(mincost)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from itertools import *
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N,M,X= LI()
R = [list(map(int,input().split())) for i in range(N)]
S = [0]

R.sort(key=lambda x: x[0])
i = 1
count = 0
flag = 1
ans = 9999999
while flag:
    temp = list(combinations(R, i))
    # print(temp)
    for q in range(0,len(temp)):
        temp2 = list(np.sum(temp[q], axis=0))
        
        n = sum(temp2[x]>=X for x in range(1,len(temp2)))
        if n == M:
            ans = min(ans,temp2[0])
    i += 1
    if i>N:
        flag = 0
if ans == 9999999:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np

N, M, X = map(int, input().split())
p = list(product([0, 1], repeat=N))
p = np.array(p).astype(bool)

# print(len(p))
C = []
A = []

for i in range(N):
    c, *a = map(int, input().split())
    C.append(c)
    A.append(a)
A = np.array(A)
C = np.array(C)

# print(p, C, A)
INF = 10 ** 18
ans = INF

for i in range(len(p)):
    # print(cond, type(cond))
    B = A[p[i]]
    B = np.sum(B, axis=0)
    # print(B, B >= X)
    if np.all(B >= X):
        ans = min(ans, C[p[i]].sum())
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

for i in range(1,2**n):
  bag = []
  total = 0
  value = [0]*m
  for j in range(n):
    if (i >> j) & 1:
      bag.append(books[j])
      total += books[j][0]
      for k in range(m):
        value[k] += books[j][k+1]
  if(all([e >=x for e in value])):
    cost = min(cost,total)
    
if(cost == 2000000000):
  print(-1)
else:
  print(cost)

Submission status: Accepted

Solution code:
import copy

#参考書数、理解度目標　参考書ステータス　今とってる参考書　理解度合計　値段合計
def comall(depth,n,x,a,usum,vsum):
  allok = True
  for i in range(1,len(usum)):
    #print(i, end = " ")
    if usum[i] < x:
      allok = False
      break
  #print()
  if allok:
    #print(vsum)
    return vsum
  else:
    #print(depth)
    if depth >= n:
      return 10000000
    else:
      v1 = comall(depth+1,n,x,a,copy.copy(usum),vsum)#i番目の参考書は買わない
      for i in range(1,len(usum)):
        usum[i] += a[depth][i]
      v2 = comall(depth+1,n,x,a,copy.copy(usum),vsum+a[depth][0])#i番目の参考書は買う
      return min(v1,v2)


def main():
  nmx = input().split()
  n = int(nmx[0])
  m = int(nmx[1])
  x = int(nmx[2])

  c = []
  for i in range(n):
    cn = list(map(lambda x:int(x), input().split() ))
    c.append(cn)
    
  ans = comall(0,n,x,c,[0]*(m+1),0)
  if ans == 10000000:
    print(-1)
  else:
    print(ans)
    
main()

Submission status: Accepted

Solution code:
import itertools
n, m, x = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

mn = 10**18
l = [i for i in range(n)]
for y in range(1, n+1):
    for v in itertools.combinations(l, y):
        tm = [0]*m
        k = 0
        for i in v:
            k += a[i][0]
            for j in range(1, m+1):
                tm[j-1] += a[i][j]
        flag = True
        for i in range(m):
            if tm[i] < x:
                flag = False
                break
        if flag:
            mn = min(k, mn)

if mn == 10**18:
    print(-1)
else:
    print(mn)

Submission status: Accepted

Solution code:
import itertools
import numpy as np


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

    C = []
    Q = []
    for i in range(N):
        QQ = list(map(int, input().split()))
        C.append(QQ[0])
        Q.append(QQ[1:])

    C = np.array(C)
    Q = np.array(Q)
    ok = False

    NN = range(N)
    ans = np.sum(C)

    for j in range(1, N + 1):
        for jj in list(itertools.combinations(NN, j)):
            tmp_value = C[list(jj)]
            tmp_score = Q[list(jj)]
            sum_ = tmp_score.sum(axis=0)
            finish_sum_ = len(list(filter(lambda x: x >= X, sum_)))

            if finish_sum_ == M:
                ans = min(ans, tmp_value.sum())
                ok = True

    if not ok:
        print(-1)
        return

    print(ans)


resolve()

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
A, C = [], []
for _ in range(N):
    tmp = input().split()
    C.append(int(tmp[0]))
    A.append([int(i) for i in tmp[1:]])
is_clear = False
min_cost = 10**10
for flg_number in range(2 ** N):
    flgs = format(flg_number, '0'+str(N)+'b')
    thr = [X] * M
    cost = 0
    for i in range(N):
        if flgs[i] == '1':
            cost += C[i]
            for j in range(M):
                thr[j] -= A[i][j]
    is_all_clear = True
    for j in range(M):
        if thr[j] > 0:
            is_all_clear = False
            break
    if is_all_clear:
        is_clear = True
        if min_cost > cost:
            min_cost = cost
if is_clear:
    print(min_cost)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys



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

a=[]

s=[0]*m

money=0

for i in range(n):
  A=list(map(int,input().split()))
  a.append(A)

  money+=A[0]

  for j in range(1,m+1):
    s[j-1]+=A[j]

for i in range(m):
  if s[i]<x:
    print("-1")
    sys.exit()




buy=[0]*n

saitei=-1

for i in range(1,(2**n)+1): #全組み合わせ
  buy=[0]*n
  t=[0]*m
  money=0
  i1=i
  for j in range(n): #どれを買うか
    buy[j]=(i1)%2
    i1=int((i1)/2)

    if buy[j]==1:
      money+=a[j][0]
      for k in range(1,m+1): #買った本no達成度の総和
        t[k-1]+=a[j][k]
  #print(buy)
  #print(t)
  flag=True
  for r in range(m):
    if t[r]<x:
      flag=False
      break
  if flag==True:
    if saitei==-1 or saitei>money:
      saitei=money

print(saitei)

Submission status: Accepted

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

c = []
a = []


def inc(l):
    if l[-1] == 0:
        l[-1] = 1
        return l
    else:
        l[-1] = 0
        return inc(l[:-1]) + [0]


def buy(a, l):
    sum_ = 0
    exps = [0] * m

    for i in range(n):
        if l[i] == 0:
            continue
        else:
            for j in range(m):
                exps[j] += a[i][j]
            sum_ += c[i]

    good = True

    for i in range(m):
        if exps[i] < x:
            good = False
            break

    return sum_, good


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

min_ = 99999999999999

selected = [0] * n

for i in range(2**n):
    try:
        sum_, good = buy(a, selected)

        if good and sum_ < min_:
            min_ = sum_

        selected = inc(selected)

    except:
        if min_ == 99999999999999:
            print(-1)
        else:
            print(min_)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

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

ca = []
for i in range(n):
    ca.append(list(map(int,input().split())))

res = 10**20

for p in range(1<<n):
    tmp = 0
    cnt = [0]*m
    for j in range(n):
        if (p>>j)&1 == 1:
            tmp += ca[j][0]
            for i in range(1,m+1):
                cnt[i-1] += ca[j][i]
    
    if min(cnt) >= x:
        res = min(res,tmp)
if res == 10**20:
    print(-1)
else:
    print(res)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np
def main():
    N, M, X = map(int, input().split())
    books = np.array([list(map(int,input().split())) for i in range(N)])
    value = select(N, M ,X, books)
    print(value)



def select(N, M, X, books):
    kouho = []
    selected = range(0, N)
    skills = books[:, 1:]
    for i in range(N, -1, -1):
        for perm in combinations(selected, i):
            selected_skills = skills[list(perm)]
            s = selected_skills.sum(axis=0)
            if len(s[s<X]) > 0:
                continue
            else:
                kouho.append(perm)
    if len(kouho) == 0:
        return -1
    value = min([sum([books[i][0] for i in k]) for k in kouho])
    return value


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

Submission status: Accepted

Solution code:
def main():
    n, m, x = [int(e) for e in input().split()]
    CA = [[int(e) for e in input().split()] for i in range(n)]

    ans = 10 ** 9
    for i in range(1, 2 ** n):
        bs = format(i, f'0{n}b')

        cs = 0
        Sm = [0] * m
        for i in range(n):
            if bs[i] == '1':
                cs += CA[i][0]
                for mi in range(m):
                    Sm[mi] += CA[i][mi + 1]

        if all(sm >= x for sm in Sm):
            ans = min(cs, ans)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
n, m, x = map(int, input().split())

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

for i in range(n):
    ca = list(map(int, input().split()))
    for j in range(m):
        c[i] = ca[0]
        a[i][j] = ca[j+1]

for i in range(m):
    s = 0
    for j in range(n):
        s += a[j][i]
    if s < x:
        print(-1)
        exit()

s = 1000000000

for i in range(1, n+1):
    for j in list(combinations(range(n), i)):
        t = [0] * m
        S = 0
        for k in range(len(j)):
            S += c[j[k]]
            for l in range(m):
                t[l] += a[j[k]][l]
        p = s
        s = min(s, S)
        for y in range(m):
            if t[y] < x:
                s = p
                break
print(s)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
t = []
for i in range(n):
  ti = list(map(int,input().split()))
  t.append(ti)
mn = float("inf")
flag = False
for i in range(2**n):
  cost = 0
  a =[0]*m
  j = 0
  while i > 0:
    if i%2 == 1:
      cost += t[j][0]
      for k in range(m):
        a[k] += t[j][1+k]
    i = i//2
    j += 1
  if min(a)>=x:
    flag = True
    if cost < mn:
      mn = cost
if flag:
  print(mn)
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
from itertools import product
import numpy as np
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, M, X = map(int, readline().split())
    CA = list(list(map(int, readline().split())) for _ in range(N))
    CA = np.array(CA)
    target = [0] + [X]*M
    target = np.array(target)
    ans = INF
    for i in range(2**N):
        tmp = 0
        for j in range(N):
            if (i>>j)&1:
               tmp += CA[j]
        if np.all(tmp>=target):
            ans = min(ans, tmp[0])
    print(-1 if ans==INF else ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def combinationListRecursive(data, r):
  result = []
  _combinationListRecursive(data, r, 0, [], result)
  return result

def _combinationListRecursive(data, r, start, progress, result):
  if r == 0:
    result.append(progress)
    return

  for i in range(start, len(data)):
    _combinationListRecursive(data, r - 1, i + 1, progress + [data[i]], result)

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

tmp = []
for i in range(1, n+1):
    c = combinationListRecursive(t, i)
    for j in c:
        cnt = [0] * (m + 1)
        for k in j:
            for l in range(m+1):
                cnt[l] += k[l]
        tmp.append(cnt)

ans = float("INF")
for i in tmp:
    ignore = False
    for j in i[1:]:
        if x > j:
            ignore = True
    if ignore:
        continue

    ans = min(ans, i[0])

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

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

book=[]
skil=[0]*M
for i in range(N):
    line=list(map(int,input().split(' ')))
    book.append(line)
    skil=list(map(lambda x,y:x+y,skil,line[1:]))

min_p=12000000
for n in range(1,N+1):
    for conbo in itertools.combinations(book,n):
        conbo_book=[0]*(1+M)
        for b in list(conbo):
            conbo_book=list(map(lambda x,y:x+y,conbo_book,b))
        if len([m for m in conbo_book[1:] if m>=X])==M:
            if min_p>conbo_book[0]:
                min_p=conbo_book[0]

print(min_p) if min_p<12000000 else print("-1")

Submission status: Accepted

Solution code:
import itertools
fi = list(map(int,input().split()))
n = fi[0]
m = fi[1]
x = fi[2]
c = []
cn = []
y = 1
for k in range(n):
  cn.append(k)
for i in range(n):
  a = list(map(int,input().split()))
  c.append(a)
for j in range(m):
  wa = 0
  for s in range(n):
    wa=wa+c[s][j+1]
  if wa < x:
    y=y*0

money = []
if not y==0:
  for s in range(n+1):
    ca = list(itertools.combinations(cn, s+1))
    cb = len(ca)
    for q in range(cb):
      cwa = []
      chan = 0
      for l in range(m+1):
        cwa.append(0)
      for p in range(s+1):
        cwa = list(map(lambda x,y: x+y, c[ca[q][p]], cwa))
      for t in range(m):
        if cwa[t+1]>=x:
          chan = chan+1
        if chan ==m:
          money.append(cwa[0])
  print(min(money))
else:
  print(-1)

Submission status: Accepted

Solution code:
import itertools
n, m, x = map(int, input().split())
a = [0] * n
ans = 100000000
for i in range(n):
    a[i] = list(map(int, input().split()))
for i in range(1, n+1):
    for j in itertools.combinations(range(n), i):
        b = [0] * m
        c = 0
        for k in list(j):
            for l in range(m):
                b[l] += a[k][l+1]
            c += a[k][0]
        if sum(y >= x for y in b) == m:
            ans = min(ans, c)
if ans == 100000000:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
N,M,X=map(int,input().split())
CA=[]
D=[]

for n in range(N):
  arr=list(map(int,input().split()))
  CA.append(arr)
CA=np.array(CA)

v=list(itertools.product([0,1], repeat=N))

for v_ in v:
  SUM=np.zeros(M+1)
  for n in range(N):
    if v_[n]==1:
      SUM = SUM+CA[n]
  D.append(list(SUM))

key=[]
value=[]
  
for d in D:
  key.append(d[0])
  value.append(d[1:])
  
dict = dict(zip(key,value))
dict_sorted = sorted(dict.items(), key=lambda x:x[0])


for d in dict_sorted:
  if all([i>=X  for i in d[1]]):
    print(int(d[0]))
    exit()

print(-1)

Submission status: Accepted

Solution code:
b0=input().split()
book=int(b0[0])
pro=int(b0[1])
norma=int(b0[2])

bl=[]
for x in range(book):
  bl.append([int(y) for y in input().split()])
  
mn=-1
for x in range(2**book):
  if book>9:
    k=str(book)+"b"
  else:
    k="0"+str(book)+"b"
  x2=format(x, k)
  m=0
  exl=[0 for i in range(pro)]
  for y in range(book):
    if x2[y]=="1":
      m+=bl[y][0]
      for j in range(pro):
        exl[j]+=bl[y][j+1]
  if min(exl)>=norma and (mn==-1 or mn>m):
    mn=m

print(mn)

Submission status: Accepted

Solution code:
#C

#デバッグ
debug=1
def pront(*n):
    if debug==1:
        print(n)
        
#10**9+7を底とした処理

base=10**9+7

def add(a,b):#a+b
    return (a+b)%base

def sub(a,b):#a-b
    return (a-b)%base

def multi(a,b):#a*b
    return (a*b)%base

def exp(a,b):#a**b
    x=1
    c=a
    d=b
    while d!=0:
        if d%2==1:
            x=multi(x,c)
        c=(c**2)%base
        d=d//2
    return x

def div(a,b):#a/b
    return(multi(a,exp(b,base-2)))

#入力
N,M,Z=map(int,input().split())

A=[list(map(int,input().split())) for i in range(N)]

#処理
X=[0 for i in range(N)]
x=float('inf')
while True:
    Y=[0 for i in range(M)]
    z=0
    for i in range(N):
        if X[i]==1:
            z+=A[i][0]
            for j in range(M):
                Y[j]+=A[i][j+1]
    for j in range(M):
        if Y[j]<Z:
            break
        if  j==M-1:
            #print(z,X)
            if z<x:
                
                x=z
    for i in range(N):
        if X[-i-1]==0:
            X[-i-1]=1
            break
        else:
            X[-i-1]=0
    #print(X)
    if X==[0 for i in range(N)]:
        break
if x==float('inf'):
    print(-1)
else:
    print(x)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
a = []
for i in range(n):
    b = list(map(int, input().split()))
    a.append(b)
l = []
for f in range(2**n):
    p = [0]*(m+1)
    for i in range(n):
        if (bin(f >> i)[-1] == '1'):
            for j in range(m+1):
                p[j] += a[i][j]
    if min(p[1:]) >= x:
        l.append(p[0])
if len(l) == 0:
    print('-1')
else:
    print(min(l))

Submission status: Accepted

Solution code:
import itertools
N, M, X = map(int, input().split())
book_lists = [list(map(int, input().split())) for i in range(N)]
no_skill_flg = True
for i in range(1, N+1):
    for j in itertools.combinations(book_lists,i):
        sum_list = [0 for _ in range(M+1)]
        for book_date in j:
            for k, l in enumerate(book_date):
                sum_list[k] += l
        if all([s >= X for s in sum_list[1:]]):
            no_skill_flg = False
            if 'ans' in globals():
                ans = min(ans, sum_list[0])
            else:
                ans = sum_list[0]
print(ans if not no_skill_flg else -1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
master = []
ans = 10 ** 18
for i in range(n):
    b = list(map(int, input().split()))
    master.append(b)

for i in range(2 ** n):
    kau = [0 for _ in range(m + 1)]
    for j in range(n):
        if (i >> j) & 1:
            # print(i)
            for k in range(m + 1):
                kau[k] += master[j][k]
    ng = 0
    for k in range(1, m + 1):
        if kau[k] < x:
            ng = 1
    if not ng:
        ans = min(ans, kau[0])
    # print(ans)
    # print(kau)
print(ans if ans != 10 ** 18 else -1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

N, M, X = map(int, input().split())
A = np.zeros((N, M), dtype=np.int32)
C = np.zeros(N, dtype=np.int32)

for i in range(N):
  H = list(map(int, input().split()))
  C[i] = H[0]
  A[i,:] = H[1:M+1]

Sum = A.sum(axis=0)
price = []
if(min(Sum) < X):
  print('-1')
else:
  for i in range(2**N):
    bb = bin(i)
    B = [0]*N
    B += [int(bb[k]) for k in range(2, len(bb))]
    B = np.array([B[-N:]]).T

    pro = A*B
    s = pro.sum(axis=0)
    if(min(s) >= X):
      price.append(np.dot(C,B)[0])

  print(min(price))

Submission status: Accepted

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

set_list = []
for i in range(2 ** N):
    select = []
    for j in range(N):
        if ((i >> j) & 1):
            select.append(j)
    if len(select) != 0:
        set_list.append(select)
    
cost = []
for i in range(2 ** N - 1):
    cost.append(sum([CA[set_list[i][j]][0] for j in range(len(set_list[i]))]))

skill = []
for i in range(2 ** N - 1):
    tmp = [0]*M
    for j in set_list[i]:
        for k in range(M):
            tmp[k] += CA[j][k+1]
    skill.append(tmp)

pool = []
for i in range(2**N - 1):
    flag = 0
    for j in skill[i]:
        if j < X:
            flag = 1
    if flag == 0:
        pool.append(cost[i])
        

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

Submission status: Accepted

Solution code:
from itertools import combinations

N, M, X = map(int, input().split())
skill = [0] * M
N_list = []
C_sum = 0
all_list = [0] * (M+1)

res_list = 0
for i in range(N):
  list_ = list(map(int, input().split()))
  N_list.append(list_)
  all_list = [all_list[i]+list_[i] for i in range(M+1)]

result = []  
for i in range(1, N+1):
  ref = list(combinations(N_list, i))
  for j in range(len(ref)):
    sums = [0] * (M+1)
    for k in range(i):
      sums = [sums[l]+ref[j][k][l] for l in range(M+1)]
    result.append(sums)
kekka = []
for i in range(len(result)):
  if all(result[i][j]>=X for j in range(1, M+1)):
    kekka.append(result[i][0])
if kekka != []:
  print(min(kekka))
else:
  print(-1)

Submission status: Accepted

Solution code:
#3
import itertools
import numpy as np

n,m,x = input().split(' ')
book_list = []
for i in range(int(n)):
    book_list.append([int(s) for s in input().split(' ')])
    
ok_list = []
for num in range(1,len(book_list)+1):
    for i in itertools.combinations(book_list,num):
        goukei = np.sum(np.array(i),axis=0)
        flag = True
        for j in range(1,len(goukei)):
            if goukei[j] < int(x):
                flag = False
                break
        if flag:
            ok_list.append(goukei.tolist())
            
if ok_list:
    print(sorted(ok_list)[0][0])
else:
    print(-1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = list()
a = list()
for i in range(n):
  row_input = list(map(int, input().split()))
  c.append(row_input[0])
  a.append(row_input[1:])
inf_value = 2*sum(c)
def check_valid(completed_choice):
  jth_skill = [0]*m
  for i in range(n):
    if completed_choice[i] == 1:
      for j in range(m):
        jth_skill[j] += a[i][j]
  return all(value>=x for value in jth_skill)
def choose_next_row(partial_choice):
  if len(partial_choice) == n:
    if check_valid(partial_choice):
      return sum(include*cost for include, cost in zip(partial_choice, c))
    else:
      return inf_value
  return min(choose_next_row(partial_choice+[0]), choose_next_row(partial_choice+[1]))
ans = choose_next_row([])
if ans == inf_value:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import itertools, numpy
n, m, x = map(int, input().split())
l = list(list(map(int, input().split())) for i in range(n))
sm = numpy.sum(l, axis=0)
ad = -1
kk = []

for k in range(n):
    com = list(itertools.combinations(l,k+1))
    sm = numpy.sum(com, axis=1)
    for i in range(len(sm)):
        kk.append(sm[i])
    
kk.sort(key=lambda z: z[0])

for i in range(len(kk)):
    if all(s >= x for s in kk[i][1:]) == True:
        ad = kk[i][0]
        break
print(ad)

Submission status: Accepted

Solution code:
from copy import copy


def recursive_bober(k, s):
    global n
    global arr
    global perm
    
    if k == n:
        perm.append(list(map(int, s.split())))
        return
    
    recursive_bober(k + 1, s)
    s += str(arr[k]) + ' '
    recursive_bober(k + 1, s)


n, m, x = map(int, input().split())
c = [0] * n
a = [[0] * m] * n
jojo = []

for i in range(n):
    cur = list(map(int, input().split()))
    c[i] = cur[0]
    for j in range(1, m + 1):
        a[i][j - 1] = cur[j]
    
    jojo.append(a[i].copy())

arr = [0] * n
for i in range(n):
    arr[i] = i

perm = []
recursive_bober(0, '')

mn = 10 ** 10
for i in perm:
    bober = [0] * m
    sum = 0
    
    for j in i:
        sum += c[j]
        for k in range(m):
            bober[k] += jojo[j][k]
    
    bad = False
    for j in bober:
        if j < x:
            bad = True
            break
    
    if not bad:
        mn = min(mn, sum)

print(mn if mn != 10 ** 10 else -1)

Submission status: Accepted

Solution code:
import itertools

def main():

    n,m,x = map(int,input().split())
    C = []
    A = []
    for i in range(n):
        array = list(map(int,input().split()))
        C.append(array[0])
        A.append(array[1:])
    cost = 10**10
    for i in range(1,n+1):
        combs = itertools.combinations(range(n), i)
        for comb in combs:
            skill = [0]*m
            cost_tmp = 0
            for e in comb:
                cost_tmp += C[e]
                for j in range(m):
                    skill[j] += A[e][j]
            for j in range(m):
                if skill[j] < x:
                    break
                if j == m-1:
                    cost = min(cost, cost_tmp)
    if cost == 10**10:
        print(-1)
        return
    print(cost)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M, X = [int(v) for v in input().strip().split(" ")]

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

####### input ######
selection = []


class Solution():
    def __init__(self, N, M, X, A, C):
        self.N = N
        self.M = M
        self.X = X
        self.A = A
        self.C = C
        self.min_cost = sum(self.C) + 100


    def search(self, from_index, selection=None):
        if from_index < self.N:
            for i in range(from_index, self.N):
                s = selection + [i]
                result = self.search(from_index=i + 1, selection=s)
                if result != -1:
                    if result < self.min_cost:
                        self.min_cost = result
            this_result = self.search(from_index=self.N, selection=selection)
            if this_result != -1:
                if this_result < self.min_cost:
                    self.min_cost = this_result
            return self.min_cost
        else:
            XX = [self.X] * self.M
            for s in selection:
                for j in range(self.M):
                    XX[j] -= self.A[s][j]

            success_flag = True
            for x in XX:
                if x > 0:
                    success_flag = False
                    break

            if success_flag:
                money = 0
                for s in selection:
                    money += self.C[s]
                return money
            else:
                return -1

s = Solution(N, M, X, A, C)

result = s.search(from_index=0, selection=selection)
if result == sum(C) + 100:
    print(-1)
else:
    print(result)

Submission status: Accepted

Solution code:
import sys
n, m, x = map(int, input().split())
MAX = sys.maxsize

datas = []
for i in range(n):
    datas.append(list(map(int, input().split())))

kingaku = 0
memos = [[0] * (m+2) for _ in range(n)]


def rec(i, rikaido, kingaku):
    
    #print('i, rikaido, kingaku', i, rikaido, kingaku)
    #print('終了条件', [i >= x for i in rikaido])
    # 終了条件：成功：全ての理解度がx以上になっている
    if all([i >= x for i in rikaido]):
        return kingaku

    # 終了条件：失敗；n冊目までチェックし終えた
    if i == n:
       return MAX

    return min(rec(i+1, rikaido, kingaku), rec(i+1, [u+t for u, t in zip(rikaido, datas[i][1:])], kingaku+datas[i][0]))


ans = rec(0, [0] * m , 0)
if ans == MAX:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x = [int(i) for i in input().split()]
bk = []
for _ in range(n):
   bk.append([int(i) for i in input().split()])
rp = 2**n 
ans = 10000000
for i in range(rp):
   rikai = [0]*m
   mon = 0
   for j in range(n):
      if i>>j & 1:
         mon += bk[j][0]
         for k in range(m):
            rikai[k] += bk[j][k+1]
   flag = True
   for j in rikai: #この組み合わせでいいか
      if j < x:
         flag = False
         break
   if flag:
      ans = min(ans,mon)
if ans == 10000000:
   ans = -1
print(ans)