Problem:
 Score : 500 points    Problem Statement We have a chocolate bar partitioned into H horizontal rows and W vertical columns of squares.  The square (i, j) at the i -th row from the top and the j -th column from the left is dark if S_{i,j} is 0 , and white if S_{i,j} is 1 .  We will cut the bar some number of times to divide it into some number of blocks. In each cut, we cut the whole bar by a line running along some boundaries of squares from end to end of the bar.  How many times do we need to cut the bar so that every block after the cuts has K or less white squares?      Constraints  1 \leq H \leq 10  1 \leq W \leq 1000  1 \leq K \leq H \times W  S_{i,j} is 0 or 1 .         Input Input is given from Standard Input in the following format:  H  W  K  S_{1,1}S_{1,2}...S_{1,W}  :  S_{H,1}S_{H,2}...S_{H,W}       Output Print the number of minimum times the bar needs to be cut so that every block after the cuts has K or less white squares.        Sample Input 1 3 5 4
11100
10001
00111      Sample Output 1 2  For example, cutting between the 1 -st and 2 -nd rows and between the 3 -rd and 4 -th columns - as shown in the figure to the left - works.  Note that we cannot cut the bar in the ways shown in the two figures to the right.        Sample Input 2 3 5 8
11100
10001
00111      Sample Output 2 0  No cut is needed.       Sample Input 3 4 10 4
1110010010
1000101110
0011101001
1101000111      Sample Output 3 3

Solution (Python):
import numpy as np
import itertools

H, W, K = map(int, input().split())
choco = []
for i in range(H):
    choco.append([int(x) for x in list(input())])

arr = np.array(choco)


count = (H-1) + (W-1)


for k in range(H):
    
    
    if count <= k:
        break

    
    for comb in itertools.combinations(range(1,H),k):

        
        t = (None,) + comb + (None,)
        s = [slice(t[j],t[j+1],) for j in range(len(t)-1)]
        
        sum_p = [0] * (k+1)
        
        cut = k
        
        for col in zip(*choco):

            
            sum_a = [sum(col[b]) for b in s]
            
            
            if any(map(K.__lt__, sum_a)):
                
                break
            
            
            
            sum_b = [x + y for x,y in zip(sum_p, sum_a)]

            if any(map(K.__lt__, sum_b)):
                cut += 1
                sum_p = sum_a
            else:
                sum_p = sum_b
                
                
        
        else:
            count = min(count,cut)

print(count)

Solution (Python):
H,W,K = map(int, input().split())
S = [input() for _ in range(H)]

L = [[0]*(W) for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "1":
            L[i][j] = 1
        
ans = H*W
for i in range(2**(H-1)):
    cnt = 0
    used = [0]*W
    memo = []
    for j in range(H-1):
        if i & (1<<j):
            cnt += 1
            memo.append(j+1)
    memo.append(H)
    num = [0]*(cnt+1)
    for j in range(W):
        idx = 0
        for k in range(H):
            if memo[idx] == k:
                idx += 1
            num[idx] += L[k][j]
        f = False
        for k in range(len(num)):
            if num[k] > K:
                f = True
                break
        if f:
            if j == 0 or used[j-1] == 1:
                cnt = H*W
                break
            used[j-1] = 1
            cnt += 1
            num = [0]*len(num)
            idx = 0
            for k in range(H):
                if memo[idx] == k:
                    idx += 1
                num[idx] += L[k][j]
    ans = min(ans, cnt)
print(ans)

Solution (Python):
from itertools import accumulate


def solve(h, w, lim, choco):
    acc = [[0] + list(accumulate(int(c == '1') for c in s)) for s in choco]
    acc = list(zip(*acc))
    acc = [[0] + list(accumulate(s)) for s in acc]
    acc = list(zip(*acc))
    

    ans = 10 ** 9
    
    
    for bit in range(1 << (h - 1)):
        k = 1
        tmp = 0
        while k < w:
            
            i = 0
            l = w + 1
            sp = bit | 1 << (h - 1)
            while sp:
                b = sp & -sp
                sp ^= b
                j = b.bit_length()
                lt = k
                while lt <= w and acc[j][lt] - acc[j][k - 1] - acc[i][lt] + acc[i][k - 1] <= lim:
                    lt += 1
                if lt == k:
                    break
                l = min(l, lt)
                
                i = j
            else:
                k = l
                if k <= w:
                    tmp += 1
                continue
            break
        else:
            
            ans = min(ans, tmp + bin(bit).count('1'))
    return ans


h, w, k = map(int, input().split())
choco = [input() for _ in range(h)]
print(solve(h, w, k, choco))

Solution (Python):



def solve(choco, cut_pos, k):
    cuts = len(cut_pos) - 2
    blocks = [0] * (len(cut_pos) - 1)

    for col in zip(*choco):
        need_cut = False
        for i, blk in enumerate(zip(cut_pos, cut_pos[1:])):
            s, e = blk
            white = sum(col[s:e])
    
            if white > k:
                return float('inf')

            if blocks[i] + white > k:
                need_cut = True
                break
            else:
                blocks[i] += white

        if need_cut:
            for i, blk in enumerate(zip(cut_pos, cut_pos[1:])):
                s, e = blk
                blocks[i] = sum(col[s:e])

        cuts += need_cut
    
    return cuts


def main():
    h, w, k = map(int, input().split())

    choco = [[int(s) for s in list(input())] for _ in range(h)]
    min_cuts = float('inf')

    for cuts in range(1 << (h-1)):
        cut_pos = [0] + [i+1 for i in range(h-1) if cuts & (1 << i)] + [h]
        min_cuts = min(min_cuts, solve(choco, cut_pos, k))

    print(min_cuts)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import *
H, W, K = map(int, input().split())
S = [list(map(int, input())) for i in range(H)]
ans = 100000
for p in product([0,1],repeat=H-1):
    tmp_ans = sum(p)
    index = []
    for i,j in enumerate(p):
        if j == 1:
            index.append(i+1)
    count = [0] * (len(index) +1)
    for w in range(W):
        plate = [yoko[w] for yoko in S]
        tmp = [0]*(len(index)+1)
        if index == []:
            tmp[0] = sum(plate)
        else:
            tmp[0] = sum(plate[0:index[0]])
            for itr in range(len(index)):
                if itr == len(index) -1:
                    tmp[itr+1] += sum(plate[index[itr]:])
                else:
                    tmp[itr+1] += sum(plate[index[itr]:index[itr+1]])
        if max(tmp) > K :
            tmp_ans = 11111111111
        tmp_sum = [x+y for (x,y) in zip(count,tmp)]
        if max(tmp_sum) > K:
            tmp_ans +=1
            count = tmp
        else:
            count = tmp_sum
    if tmp_ans < ans:
        ans = tmp_ans

print(ans)

Solution (Python):

import sys



H,W,K = map(int,input().split())
S = [[0]*W for _ in range(H)]
for i in range(H):
    st = list(input())
    for j,t in enumerate(st):
        S[i][j] = int(t)


ans = 10**9+7
for i in range(1<<(H-1)):
    res = 0
    tmp = i
    h = [0]*(H-1)
    idx = (H-2)
    while tmp>0:
        if tmp&1:
            h[idx]=1
            res += 1
        idx -= 1
        tmp>>=1
    group = [0]*H
    for j in range(H-1):
        group[j+1] = group[j] + h[j]
    
    L = group[-1]+1
    count = [0]*(L)
    possible = True
    for j in range(W):
        nxt = [0]*(L)
        for k in range(H):
            if S[k][j]:
                nxt[group[k]] += 1
        
        cut = False
        for l in range(L):
            if count[l]+nxt[l]>K:
                cut = True
                break
        
        if cut:
            for l in range(L):
                if nxt[l]>K:
                    possible = False
                    break
                count[l] = nxt[l]
            else:
                res += 1
                continue
            break
            
        else:
            for l in range(L):
                count[l] += nxt[l]
    if possible:
        ans = min(ans,res)
print(ans)

Solution (Python):
h,w,K = map(int,input().split())
sij = [input() for j in range(h)]

num = 2**(h-1)
hon = 10**18

for i in range(num):
    tmp = format(i,'0'+str(h)+'b')
    
    yoko_hon = sum(list(map(int,tmp)))+1
    blk = [0]*(yoko_hon)
    
    tmp_col = 0
    tmp_hon = yoko_hon-1
    flag = True
    ok_flag = True
    for j in range(w):
        tmp_blk = [0]*(yoko_hon)
        blk_num = 0
        for k in range(h):
            if tmp[k] == str(1):
                blk_num += 1
            
            tmp_blk[blk_num] += int(sij[k][j])
            
            if blk[blk_num] + tmp_blk[blk_num] > K:
                flag = False
                continue
        
        
        if flag == False:
            for l in range(yoko_hon):
                if tmp_blk[l] > K:
                    ok_flag = False
                    break
                blk[l] = tmp_blk[l]
            tmp_hon += 1
            tmp_col = 0
            flag = True
        else:
            for l in range(yoko_hon):
                blk[l] += tmp_blk[l]
                tmp_col += 1
        if ok_flag == False:
            break
            
    
    if ok_flag == False:
        ok_flag = True
        continue
    
    hon = min(tmp_hon,hon)
    
print(hon)

Solution (Python):
sel='E'

if sel=='A':
    N,M=map(int,input().split())
    ans=0
    ans+=M*(M-1)//2
    ans+=N*(N-1)//2
    print(ans)


if sel=='B':
    def ispal(s):
        for i in range(len(s)//2+1):
            if s[i]!=s[-(i+1)]:
                return False
        return True

    S=input()
    N=len(S)
    if ispal(S) and ispal(S[:(N-1)//2]) and ispal(S[(N+3)//2-1:]):
        print('Yes')
    else:
        print('No')


if sel=='C':
    L=int(input())
    print((L**3)/27)


if sel=='D':    
    N=int(input())
    A=[int(i) for i in input().split()]
    kin=list(set(A))
    cnt={}
    for k in kin:
        cnt[k]=0
    for a in A:
        cnt[a]+=1
    SUM=0
    for k in kin:
        SUM+=cnt[k]*(cnt[k]-1)//2
    for a in A:
        if cnt[a]>=2:
            print(SUM-cnt[a]+1)
        else:
            print(SUM)
        

if sel=='E':
    def add(in1, in2):
        return [a + b for a, b in zip(in1, in2)]

    def split(ar, k, w):
        a = 0
        if max(max(ar)) > k:
            return -1
        tm = ar[0]
        for i in range(1, w):
            tm = add(tm, ar[i])
            if max(tm) > k:
                a += 1
                tm = ar[i]
        return a        

    h, w, k = map(int, input().split())
    s = [[int(i) for i in input()] for j in range(h)]
    ans = h*w

    for i in range(2**(h-1)):
        data = []
        temp = s[0]
        sp = bin(i+2**h)[4:]
        for j in range(1, h):
            if sp[j-1] == "0":
                temp = add(temp, s[j])
            else:
                data.append(temp)
                temp = s[j]
        data.append(temp)
        ans_ = split([list(x) for x in zip(*data)], k, w)
        if ans_ == -1:
            continue
        ans_ += sp.count("1")
        if ans > ans_:
            ans = ans_
    print(ans)

Solution (Python):
h, w, k = map(int, input().split())
s = [list(map(int, input())) for _ in range(h)]
ans = float("inf")

for sep in range(1 << (h-1)):
    g_id = [0] * h
    cur = 0
    for i in range(h-1):
        g_id[i] = cur
        if sep >> i & 1: cur += 1
    g_id[h-1] = cur
    g_num = cur+1

    ng = False
    for i in range(w):
        tmp = [0] * g_num
        for j in range(h): tmp[g_id[j]] += s[j][i]
        if any([x > k for x in tmp]): ng = True; break
    if ng: continue

    res = g_num-1
    
    gs = [0] * g_num
    for i in range(h):
        gs[g_id[i]] += s[i][0]
    
    for i in range(1, w):
        tmp = gs[::]
        for j in range(h):
            tmp[g_id[j]] += s[j][i]
        if any([x > k for x in tmp]):
            res += 1
            gs = [0] * g_num
        for j in range(h): gs[g_id[j]] += s[j][i]

    ans = min(ans, res)

print(ans)

Solution (Python):
from itertools import *

H, W, K = map(int, input().split())
S = [list(map(int, input())) for i in range(H)]

cut_min = H+W-2

for r_cut in range(H):
  if cut_min <= r_cut:
    continue
  for r_pos in combinations(range(1, H), r_cut):
    r_pos = (None,)+r_pos+(None,)
    r_blocks = [slice(*r_pos[i:i+2]) for i in range(len(r_pos)-1)]
    
    cut = r_cut
    prev_sum = [0] * len(r_blocks)
    for col in zip(*S):
      curr_sum = [sum(col[b]) for b in r_blocks]
      if any(map(K.__lt__, curr_sum)):
        break
      next_sum = [x+y for x,y in zip(prev_sum, curr_sum)]
      if any(map(K.__lt__, next_sum)):
        cut += 1
        if cut_min <= cut:
          break
        prev_sum = curr_sum
      else:
        prev_sum = next_sum
    else:
      cut_min = cut
print(cut_min)

Solution (Python):
import itertools


H, W, K = map(int, input().split())
S = [list(map(int, input())) for _ in range(H)]


ans = H*W

for divr in range(1<<(H-1)):    
    row = 0
    Sr = [[S[0][i] for i in range(W)]]
    for i in range(1, H):
        if 1&(divr>>i-1):
            row += 1
            Sr.append([S[i][j] for j in range(W)])
        else:
            Sr[row] = [Sr[row][j]+S[i][j] for j in range(W)]

    
    cnt = [0]*(row+1)
    ans_ = row
    flg = True
    for i in range(W):
        for j in range(row+1):
            if Sr[j][i] > K:
                flg = False
                break
            cnt[j] += Sr[j][i]
            if cnt[j] > K:
                ans_ += 1
                cnt = [0]*(row+1)
                for l in range(row+1):
                    cnt[l] += Sr[l][i]
                break

        if ans_ >= ans or not flg:
            break

    if flg:
        ans = min(ans, ans_)


print(ans)

Solution (Python):
H,W,K = map(int,input().split())
S = [[int(i) for i in input()] for _ in range(H)]
ans = float("inf")


for i in range(2**(H-1)): 
    start = [0]
    end = []
    for j in range(H-1):
        if i >> j & 1 == 1:
            j += 1
            start.append(j)
            end.append(j)
    end.append(H)
    L = len(end)
    
    divcnt = L-1
    
    wcnt = [0]*L
    
    tmp = [0]*L
    for w in range(W):
        
        flag = False
        for idx in range(L):
            cnt = 0
            for h in range(start[idx],end[idx]):
                cnt += S[h][w]
                if cnt > K: break
            else:
                tmp[idx] = cnt
                wcnt[idx] += cnt
                if wcnt[idx] > K: flag = True
                continue
            break
        else:
            if flag:
                
                wcnt = tmp[:]
                divcnt += 1
            continue
        break
    else:
        ans = min(ans,divcnt)

print(ans)

Solution (Python):
H, W, K = map(int, input().split())
s = [list(input()) for _ in range(H)]

c = [[0 for _ in range(W)] for _ in range(H)]





ans = (H-1) * (W-1)
for div in range(1<<(H-1)):
    g = 0 
    id = [0] * H 
    for i in range(H):
        id[i] = g
        if div>>i&1: 
            g += 1 
    g += 1 
    
    for i in range(g):
        for j in range(W):
            c[i][j] = 0
    
    for i in range(H):
        for j in range(W):
            c[id[i]][j] += int(s[i][j])

    num = g - 1 
    now = [0] * g 
    
    def add(j):
        for i in range(g):
            now[i] += c[i][j] 
        for i in range(g):
            
            if now[i] > K: return False
        return True

    for j in range(W):
        if not (add(j)): 
            num += 1
            now = [0] * g
            if not (add(j)):
                num = (H-1) * (W-1)
                break
    
    ans = min(ans, num) 

print(ans)

Solution (Python):
from collections import deque

H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))


def cut(bit):

    """
    横の切れ目の場所をビットで管理する。
    "00...0" <= bit <= "11...1"(H - 1桁)の時に、縦に入れる切れ目の最小回数を返す。
    """

    end = [] 
    for i in range(H - 1):
        if bit[i] == '1':
            end.append(i)
    end.append(H - 1)
    chocolates = [0] * (len(end))
    

    """
    ここまでで板チョコを横に切ったわけだが、こうして分割した横長の部分板チョコを
    上からsection = 0, 1, 2,..., len(end)-1と呼び分けることにする。
    """

    cut = 0
    whites_sum = [0] * len(end) 
    for w in range(W):
        whites = [0] * len(end) 
        section = 0 
        coarse = False 

        for h in range(H + 1):
            
            if h > end[section]:
                if whites[section] > K:
                    coarse = True
                    break
                elif whites_sum[section] + whites[section] > K:
                    cut += 1
                    whites_sum = whites
                    whites = [0] * len(end)
                    section += 1
                else:
                    whites_sum[section] += whites[section]
                    section += 1

            
            if h < H and S[h][w] == '1':
                whites[section] += 1

        
        if coarse:
            return -1
    return cut


ans = 10 ** 10
for h in range(2 ** (H - 1)):
    bit = bin(h)[2:] 
    l = len(bit)
    bit = '0' * (H - 1 - l) + bit 
    

    vertical_cuts = cut(bit)
    if vertical_cuts != -1:
        preans = vertical_cuts + bit.count('1')
        ans = min(ans, preans)
        


print(ans)

Solution (Python):
h,w,k = map(int, input().split())
s = [input() for _ in range(h)]

def out(l,ll):
    for z in range(ll):
        if l[z] > k:
            return True
    return False

def A(lt, hon):
    noww = [0] * (hon + 1)
    yoko = 0
    for j in range(w):
        kari = [0] * (hon + 1)
        for x in range(hon + 1):
            for y in range(lt[x], lt[x+1]):
                if s[y][j] == "1":
                    kari[x] += 1
        if out(kari, hon+1):
            return h * w
        
        neww = []
        for x in range(hon + 1):
            neww.append(noww[x] + kari[x])
        if out(neww, hon+1):
            yoko += 1
            noww = kari
        else:
            noww = neww
    return yoko + hon

ans = h * w

for i in range(2 ** (h-1)):
    tate = [0]
    honsu = 0
    for j in range(h-1):
        if ((i >> j) & 1):
            tate.append(j + 1)
            honsu += 1
    tate.append(h)
    ans = min(ans, A(tate, honsu))

print(ans)

Solution (Python):
import itertools
 
H,W,K=map(int, input().split())
S=[]
for _ in range(H):
  S.append([int(s) for s in input()])
 
ans=2000
for t in itertools.product([0,1],repeat=H-1):
  cnt=t.count(1)
  lst=[[s for s in S[0]]]
  for h in range(H - 1):
    if t[h]==1:
      lst.append(S[h+1])
    else:
      lst[-1]=[lst[-1][i]+S[h+1][i] for i in range(W)]
  L=len(lst)
  R=[0]*L
  for w in range(W):
    if max(lst[i][w] for i in range(L))>K:
      break
    tmp=[R[i]+lst[i][w] for i in range(L)]
    if max(tmp)>K:
      cnt+=1
      R=[lst[i][w] for i in range(L)]
    else:
      R=tmp
  else:
    ans=min(ans,cnt)
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def MAP(): return map(int, input().split())
inf = sys.maxsize

h, w, k = MAP()
s = [[int(i) for i in STR()] for _ in range(h)]

ans = inf
for i in range(2 ** (h - 1)): 
    hdiv = [1 for _ in range(h)]
    for j in range(h - 1):
        tmp = 2 ** j
        hdiv[j] = 1 if i & tmp else 0
    sh = sum(hdiv)
    tmpans = sh - 1
    wdiv = [0 for _ in range(w - 1)]
    partsum = [0 for _ in range(sh + 1)]
    j = 0
    cnt = 0
    while j < w: 
        tmp = 0
        idx = 0
        for kk in range(h): 
            tmp += s[kk][j]
            if hdiv[kk]:
                partsum[idx] += tmp
                tmp = 0
                idx += 1
        flag = True
        for kk in range(sh + 1):
            if partsum[kk] > k:
                tmpans += 1
                partsum = [0 for _ in range(sh + 1)]
                flag = False
        if flag:
            j += 1
            cnt = 0
        else:
            cnt += 1
        if cnt > 2:
            tmpans = inf
            break
    ans = min(ans, tmpans)
print(ans)

Solution (Python):
import sys
inf = sys.maxsize

if __name__ == '__main__':
    h, w, k = map(int, sys.stdin.readline().strip().split())
    s = [[int(i) for i in sys.stdin.readline().strip()] for _ in range(h)]
    
    ans = inf
    for i in range(2 ** (h - 1)): 
        hdiv = [1 if i & 2 ** j else 0 for j in range(h - 1)]
        hdiv.append(1)
        sh = sum(hdiv)
        tmpans = sh - 1
        partsum = [0 for _ in range(sh)]
        partsum_p = [0 for _ in range(sh)]
        j = 0
        for j in range(w): 
            tmp = 0
            idx = 0
            flag = False
            for kk in range(h): 
                tmp += s[kk][j]
                if hdiv[kk]:
                    partsum_p[idx] = partsum[idx]
                    partsum[idx] += tmp
                    if partsum[idx] > k and not flag:
                        tmpans += 1
                        flag = True
                    tmp = 0
                    idx += 1
            if flag:
                partsum = [partsum[l] - partsum_p[l] for l in range(sh)]
                partsum_p = [0 for _ in range(sh)]
                for kk in range(sh):
                    if partsum[kk] > k:
                        tmpans = inf
                        break
        ans = min(ans, tmpans)
    print(ans)

Solution (Python):
from itertools import combinations

H, W, K = map(int, input().split())

map = [None] * H
for i in range(H):
  map[i] = [int(c) for c in input().strip()]


def a(heights=[]) -> int:
  assert len(heights) > 0
  count = len(heights) - 1

  total = {i: (0, 0) for i in range(len(heights))}
  for i in range(W):
    violate = False
    for j, height in enumerate(heights):
      n = 0
      for k in range(height[0], height[1]):
        n += map[k][i]
      if n > K:
        return -1
      total[j] = (total[j][0] + n, n)
      if total[j][0] > K:
        violate = True
    if violate:
      count += 1
      for j in range(len(heights)):
        tmp = total[j][1]
        total[j] = (tmp, tmp)
  return count


patterns = [[(0, H)]]
iterable = [i + 1 for i in range(H - 1)]
for r in range(1, H):
  for c in combinations(iterable, r):
    pattern = []
    last = 0
    for i in c:
      pattern.append((last, i))
      last = i
    pattern.append((last, H))
    patterns.append(pattern)

print(min(filter(lambda x: x >= 0, [a(p) for p in patterns])))

Solution (Python):
def add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]
 
def split(ar, k, w):
    a = 0
    if max(max(ar)) > k:
      return -1
    tm = ar[0]
    for i in range(1, w):
        tm = add(tm, ar[i])
        if max(tm) > k:
            a += 1
            tm = ar[i]
    return a        
 
h, w, k = map(int, input().split())
s = [[int(i) for i in input()] for j in range(h)]
ans = h+w
 
for i in range(2**(h-1)):
    data = []
    temp = s[0]
    sp = bin(i+2**h)[4:]
    if ans < sp.count("1"):
        continue
    for j in range(1, h):
        if sp[j-1] == "0":
            temp = add(temp, s[j])
        else:
            data.append(temp)
            temp = s[j]
    data.append(temp)
    ans_ = split([list(x) for x in zip(*data)], k, w)
    if ans_ == -1:
        continue
    ans_ += sp.count("1")
    if ans > ans_:
        ans = ans_
print(ans)

Solution (Python):
import itertools
H, W, K = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(H)]
def check(k):
    if k <= K:
        return(True)
    else:
        return(False)
        
noans = 0
def make_lst(i):
    global noans, lst, havelst
    temp = S[0][i]
    for h in range(H-1):
        if y[h]:
            lst.append(temp)
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
    lst.append(temp)
    if check(max(lst)):
        havelst = 1
    else:
        noans = 1

               
def nocut(i):
    global cutnum, lst, havelst, noans
    prelst = []
    temp = S[0][i]
    if i == W-1:
        if not check(temp):
            noans = 1
    j = 0
    for h in range(H-1):            
        if y[h]:
            lst[j] += temp
            prelst.append(temp)
            j += 1
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
        if i == W-1:
            if not check(temp):
                noans = 1
    prelst.append(temp)
    lst[-1] += temp
    if check(max(lst)):

        return(True)
    else:
        cutnum += 1
        lst = prelst        

        
                 
ans = float("inf")    
for y in itertools.product((0, 1), repeat=H-1):
    havelst = 0
    lst = []
    cutnum = sum(y)
    for x in range(W):
        if noans:
            break
        if havelst:
            nocut(x)
        else:
            make_lst(x)

    if noans:
        noans = 0
        continue
    else:
        ans = min(cutnum, ans)
print(ans)

Solution (Python):
import itertools
H, W, K = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(H)]
def check(k):
    if k <= K:
        return(True)
    else:
        return(False)
        
noans = 0
def make_lst(i):
    global noans, lst, havelst
    temp = S[0][i]
    for h in range(H-1):
        if y[h]:
            lst.append(temp)
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
    lst.append(temp)
    if check(max(lst)):
        havelst = 1
    else:
        noans = 1

               
def nocut(i):
    global cutnum, lst, havelst, noans
    prelst = []
    temp = S[0][i]
    if i == W-1:
        if not check(temp):
            noans = 1
    j = 0
    for h in range(H-1):            
        if y[h]:
            lst[j] += temp
            prelst.append(temp)
            j += 1
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
        if i == W-1:
            if not check(temp):
                noans = 1
    prelst.append(temp)
    lst[-1] += temp
    if check(max(lst)):

        return(True)
    else:
        cutnum += 1
        lst = prelst        

        
                 
ans = float("inf")    
for y in itertools.product((0, 1), repeat=H-1):
    havelst = 0
    lst = []
    cutnum = sum(y)
    for x in range(W):
        if noans:
            break
        if havelst:
            nocut(x)
        else:
            make_lst(x)

    if noans:
        noans = 0
        continue
    else:
        ans = min(cutnum, ans)
print(ans)

Solution (Python):


import itertools


INF = 10 ** 5


H, W, K = list(map(int, input().split()))
S = [[int(e) for e in input()] for _ in range(H)]


def solve(w, l):
    n = len(l) + 1
    ans = 0
    if n == 1:
        dp = 0
        for j in range(W):
            x = w[-1][j]
            if x > K:
                return INF
            dp += x
            if dp > K:
                ans += 1
                dp = x
    else:
        dp = [0] * n
        for j in range(W):
            x = [0] * n
            b = False
            for i in range(n):
                if i == 0:
                    x[i] = w[l[i]][j]
                elif i == n - 1:
                    x[i] = w[-1][j] - w[l[-1]][j]
                else:
                    x[i] = w[l[i]][j] - w[l[i-1]][j]
                if x[i] > K:
                    return INF
                dp[i] += x[i]
                if dp[i] > K:
                    b = True
            if b:
                dp = x
                ans += 1
    return ans


def main():
    w = [S[0]]
    for i in range(1, H):
        w.append([w[i-1][j] + S[i][j] for j in range(W)])

    ans = INF
    num_list = [i for i in range(H - 1)]
    for i in range(H):
        comb_list = itertools.combinations(num_list, i)
        for l in comb_list:
            ans = min(ans, i + solve(w, l))

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]
 
def split(ar, k, w):
    a = 0
    if max(max(ar)) > k:
      return -1
    tm = ar[0]
    for i in range(1, w):
        tm = add(tm, ar[i])
        if max(tm) > k:
            a += 1
            tm = ar[i]
    return a        
 
h, w, k = map(int, input().split())
s = [[int(i) for i in input()] for j in range(h)]
ans = h*w
 
for i in range(2**(h-1)):
    data = []
    temp = s[0]
    sp = bin(i+2**h)[4:]
    if ans < sp.count("1"):
        continue
    for j in range(1, h):
        if sp[j-1] == "0":
            temp = add(temp, s[j])
        else:
            data.append(temp)
            temp = s[j]
    data.append(temp)
    ans_ = split([list(x) for x in zip(*data)], k, w)
    if ans_ == -1:
        continue
    ans_ += sp.count("1")
    if ans > ans_:
        ans = ans_
print(ans)

Solution (Python):

import itertools
H, W, K = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(H)]
def check(k):
    if k <= K:
        return(True)
    else:
        return(False)
        
noans = 0
def make_lst(i):
    global noans, lst, havelst
    temp = S[0][i]
    for h in range(H-1):
        if y[h]:
            lst.append(temp)
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
    lst.append(temp)
    if check(max(lst)):
        havelst = 1
    else:
        noans = 1
               
def nocut(i):
    global cutnum, lst, havelst
    prelst = []
    temp = S[0][i]
    j = 0
    for h in range(H-1):
        if y[h]:
            lst[j] += temp
            prelst.append(temp)
            j += 1
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
    prelst.append(temp)
    lst[-1] += temp
    if check(max(lst)):
        return(True)
    else:
        cutnum += 1
        lst = prelst        
                 
ans = float("inf")
cutlst = []    
for y in itertools.product((0, 1), repeat=H-1):
    havelst = 0
    lst = []
    cutnum = sum(y)
    for x in range(W):
        if noans:
            break
        if havelst:
            nocut(x)
        else:
            make_lst(x)
    if noans==1:
        noans = 0
        continue
    ans = min(cutnum, ans)
print(ans)

Solution (Python):
h, w, k = map(int, input().split())

choco = [[0] * w for _ in range(h)]

for i in range(h):
    s = input()
    for j in range(w):
        choco[i][j] = int(s[j])

ans = float("inf")
for bit in range(1 << (h - 1)):
    idx = [0] * h
    group = 0
    for i in range(h):
        idx[i] = group
        if (bit >> i) & 1:
            group += 1
    group += 1
    array = [[0] * w for _ in range(group)]
    for j in range(w):
        for i in range(h):
            array[idx[i]][j] += choco[i][j]

    cnt = group - 1
    cum = [0] * group
    canAdd = True
    for i in range(w):
        for j in range(group):
            if cum[j] > k:
                canAdd = False

        if ans <= cnt:
            canAdd = False

        if canAdd is False:
            break

        for j in range(group):
            tmp = cum[j] + array[j][i]
            if tmp > k:
                cnt += 1
                for l in range(group):
                    cum[l] = array[l][i]
                break
            cum[j] += array[j][i]

    if canAdd:
        ans = min(ans, cnt)

print(ans)

Solution (Python):
import numpy as np
H,W,K = map(int, input().split())
C = np.array([list(map(int, input())) for _ in range(H)])
C = np.hstack([np.zeros([H,1]),C])
np.cumsum(C, axis=1, out=C)
ans = 10**5
for s in range(1<<(H-1)):
	ind = 0
	A = np.zeros([1,W+1])
	for i in range(H):
		if s >> i & 1 == 1:
			A = np.vstack([A,C[ind:i+1,:].sum(axis=0)])
			ind = i+1
	A = np.vstack([A,C[ind:].sum(axis=0)])

	ind = 0
	cnt = 0
	while True:
		cut = 10**3+2
		for a in A:
			cut = min(cut, np.searchsorted(a,a[ind]+K,side='right'))
		if cut == W+1:
			break
		if ind == cut-1:
			cnt = 10**4+2
			break
		else:
			ind = cut-1
		cnt += 1

	h_cnt = 0
	for i in range(H):
		if s >> i & 1 == 1:
			h_cnt += 1

	ans = min(ans, cnt+h_cnt)

print(ans)