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

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def solve():
    h, w, k = LI()
    s = SR(h)
    bit_length = [0] 
    for i in range((h-1)): 
        bit_length += [x + 1 for x in bit_length]
    ans = inf
    for i in range(1 << (h - 1)):
        tmp = [0] * (bit_length[i] + 1)
        num = 0
        for x in range(w):
            t = 0
            f = 0
            tmp1 = [0] * (bit_length[i]+1)
            for y in range(h):
                
                tmp[t] += int(s[y][x])
                tmp1[t] += int(s[y][x])
                if tmp[t] > k:
                    f = 1
                if tmp1[t] > k:
                    break
                t += 1 & (i >> y) 

            else:
                if f:
                    num += 1
                    
                    tmp = tmp1[::1]
                continue
            break
        else:
            
            ans = min(ans, bit_length[i] + num)
    print(ans)


        
    return



if __name__ == '__main__':
    solve()

Solution (Python):
from itertools import accumulate
H, W, K = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]
accs = [[0]+list(accumulate(l)) for l in zip(*S)]

ans = float('inf')
for i in range(1 << (H-1)):
    parts = []
    tans = 0
    for k in range(H-1):
        if i & (1 << k):
            tans += 1
            parts.append(k+1)
    parts.append(H)
    cts = [0] * len(parts)
    for j in range(W):
        prev = 0
        flag1 = False
        for idx, p in enumerate(parts):
            c = accs[j][p] - accs[j][prev]
            cts[idx] += c
            if cts[idx] > K:
                flag1 = True
                break
            prev = p
        if flag1:
            tans += 1
            prev = 0
            flag2 = False
            for idx, p in enumerate(parts):
                c = accs[j][p] - accs[j][prev]
                if c > K:
                    
                    flag2 = True
                    break
                cts[idx] = c
                prev = p
            if flag2:
                break
    else:
        ans = ans if ans < tans else tans
print(ans)

Solution (Python):
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
'''




h,w,kk = list(map(int, input().split()))

info = []
for i in range(h):
    s = input()
    ss = []
    for j in range(w):
        ss.append(int(s[j]))
    info.append(ss)

n = 2**(h-1)


anss=[]

for i in range(n):
    
    bit = ValueToBits(i,h-1)
    bitsum = sum(bit)
    blocks = bitsum + 1
    
    
    sums = [0 for i in range(blocks)]
    sums2 = [0 for i in range(blocks)]
    ids = []
    
    nowid = 0
    ids.append(nowid)
    for j in range(h-1):
        if(bit[j]==1):
            nowid+=1
        ids.append(nowid)
    
    
    dead = 0
    lines = 0
    for k in range(w-1):
        flag=0
        for j in range(h):
            sums[ids[j]]+=info[j][k]
        
        for j in range(blocks):
            sums2[j] = sums[j]
            
            if(sums[j]>kk):
                
                dead = 1
        full=0
        for j in range(h):
            sums2[ids[j]]+=info[j][k+1]
            
            
        for j in range(blocks):
            if(sums2[j] > kk):
                lines +=1
                full=1
                
                break
        
        
        if(full==1):
            for j in range(blocks):
                sums[j] = 0
                
        if(dead==1):
            
            break
    if(dead==1):
        anss.append(999999)
    else:
        anss.append(lines + bitsum)
        

print(min(anss))

Solution (Python):
h,w,k = map(int,input().split())
s = []
for i in range(h):
    s0 = list(input())
    s.append(s0)
al = []
wl = [[0 for i in range(h)] for i in range(w)]
for i in range(w):
    count = 0
    for j in range(h):
        if s[j][i] == "1":
            count += 1
        wl[i][j] = count
for i in range(2**(h-1)):
    ans = 0
    b = []
    for j in range(h-1):
        if ((i >> j) & 1):
            b.append(j)
    
    b.append(h-1)
    bl = []
    now = -1
    for j in b:
        if now == -1:
            bl.append(wl[0][j])
            now = j
        else:
            bl.append(wl[0][j]-wl[0][now])
            now = j
    ans = len(bl)-1
    key = 1
    key2 = 0
    for j in range(1,w):
        now = -1
        aa = []
        key2 = 0
        for x in  range(len(bl)):
            
            if now == -1:
                if bl[x] > k:
                    key = 0
                    break
                else:
                    bl[x] += wl[j][b[x]]
                    aa.append(wl[j][b[x]])
                    if bl[x] > k:
                        key2 = 1
                    now = b[x]
            else:
                if bl[x] > k:
                    key = 0
                    break
                else:
                    bl[x] += wl[j][b[x]] - wl[j][now]
                    aa.append(wl[j][b[x]]-wl[j][now])
                    now = b[x]
                    if bl[x] > k:
                        key2 = 1
        if key2 == 1 and key == 1:
            for x in range(len(bl)):
                bl[x] = aa[x]
            ans += 1
        elif key == 0:
            break
    if key == 1:
        al.append(ans)
print(min(al))

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
H,W,K=map(int,input().split())
S=[input() for i in range(H)]
from itertools import product
l=tuple(product([0,1], repeat=(H-1)))
a=2000
for i in l:
    t=sum(i)
    p=t
    w=[0]*(t+1)
    c=0
    x=[0]*W
    while c<W:
        it=0
        for k in range(H):
            if S[k][c]=="1":
                w[it]+=1
            if k!=H-1 and i[k]:
                it+=1
        for j in w:
            if j>K:
                w=[0]*(t+1)
                p+=1
                x[c]+=1
                break
        else:
            c+=1
            continue
        if x[c]==2:
            break
    else:
        if p<a:
            a=p
print(a)

Solution (Python):
import sys
input = sys.stdin.readline
h,w,k = map(int,input().split())
C = [list(input().rstrip()) for i in range(h)]

for i in range(h):
    for j in range(w):
        C[i][j] = int(C[i][j])


A = [[0] * w for i in range(h)]
A = C

















ans = 10**15

for i in range(2**(h-1)):
    owa=0
    ib = format(i, "b").zfill(h-1)
    H = [0] * h
    t = 0
    for j in range(h-1):
        if ib[j] == "1":
            t += 1
        H[j+1] = t
    
    ans0 = ib.count("1")
    ans00 = ans0
    D = [0] * h
    for j in range(w):
        DD = [0] * h
        for kk in range(h):
            DD[H[kk]] += A[kk][j]
        f = 0
        
        for kk in range(h):
            if DD[kk] > k:
                owa = 1
                break
            elif DD[kk]+D[kk] > k:
                f = 1
                
        if owa==1:
            break
        if f == 1:
            ans0 += 1
            D = DD[:]
        else:
            for kk in range(h):
                D[kk] += DD[kk]

    if owa==0:
        ans = min(ans, ans0)
        
print(ans)

Solution (Python):
h,w,k = map(int,input().split())
s = [input() for _ in range(h)]
data_yoko = [[0]*(w+1) for _ in range(h)]
for i in range(w):
    for j in range(h):
        if s[j][i] == "1":
            data_yoko[j][i+1] = 1
        data_yoko[j][i+1] += data_yoko[j][i]
data_tate = [[0]*w for _ in range(h+1)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "1":
            data_tate[i+1][j] = 1
        data_tate[i+1][j] += data_tate[i][j]

ans = h*w
for case in range(2**(h-1)):
    now = 0
    use = []
    for bit in range(h-1):
        if case>>bit & 1:
            use.append(bit+1)
            now += 1
    use.append(h)
    left = [0]*len(use)
    pre = -1
    check1 = True
    check2 = True
    for i in range(w):
        for j in range(len(use)):
            to = data_tate[use[j]][i] if j == 0 else data_tate[use[j]][i]-data_tate[use[j-1]][i]
            if k < to:
                check1 = False
                break
            if to + left[j] > k:
                check2 = False
                break
            left[j] += to
        if not check1:
            break
        if check2:
            continue
        for j in range(len(use)):
            left[j] = data_tate[use[j]][i] if j == 0 else data_tate[use[j]][i]-data_tate[use[j-1]][i]
        now += 1
        check2 = True
    if check1:
        ans = min(ans,now)

print(ans)

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

ans = float('inf')

for i in range(2**(h-1)):
    a = format(i,'b').zfill(h-1)
    choco = [[int(x) for x in s[0]]]
    for k in range(1,h):
        if a[k-1]=='1':
            choco.append([0 for x in range(w)])
        for j in range(w):
            if s[k][j]=='1':
                choco[-1][j]+=1
    b = 0
    c = [0 for x in range(len(choco))]
    ok = 1
    for j in range(w):
        for k in range(len(choco)):
            if choco[k][j]>K:
                ok = 0
                break
            c[k]+=choco[k][j]
        if max(c)>K:
            b+=1
            c = [choco[x][j] for x in range(len(choco))]
    if ok:
        ans = min(b+a.count('1'),ans)
print(ans)

Solution (Python):
H, W, K = map(int, input().split())
S = [list(map(int, input())) for _ in range(H)]
ans = 10**18
for i in range(2**(H-1)):
    flag2 = False
    tate = 0
    tmp = [0 for _ in range(H)]
    for k in range(W):

        flag1 = False
        for j in range(H):
            if S[j][k] == 1:
                tmp[j] += 1
        tmp2 = tmp[:]
        for j in range(H - 1):
            if not ((i >> j) & 1):
                tmp2[j + 1] += tmp2[j]
        for j in range(H):
            if tmp2[j] > K:
                tate += 1
                flag1 = True
                break
        if flag1:
            tmp = [0 for _ in range(H)]
            for j in range(H):
                if S[j][k] == 1:
                    tmp[j] += 1
            tmp2 = tmp[:]
            for j in range(H - 1):
                if not ((i >> j) & 1):
                    tmp2[j + 1] += tmp2[j]
            for j in range(H):
                if tmp2[j] > K:
                    flag2 = True
                    break
        if flag2:
            break
    if flag2:
        continue

    yoko = 0
    for j in range(H - 1):
        if (i >> j) & 1:
            yoko += 1
    ans = min(ans, tate+yoko)

print(ans)

Solution (Python):
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
def popcnt(n):
  c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
  c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
  c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
  c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
  c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
  c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
  return c

answer = 10 ** 18

for i in range(2 ** (H - 1)):
    flag = 0
    answer_tmp = popcnt(i)
    
    dic = [-1] * H
    index = 0
    for j in range(H):
        dic[j] = index
        if i >> j & 1:
            index += 1
    tmp = [0] * (index + 1)
    
    
    
    for k in range(W):
        for j in range(H):
            
            if S[j][k] == "1":
                tmp[dic[j]] += 1
        if k == 0 and max(tmp) > K:
            
            flag = 1
            break
        if max(tmp) > K:
            answer_tmp += 1
            for j, t in enumerate(tmp):
                tmp[j] = 0
            for j in range(H):
                
                if S[j][k] == "1":
                    tmp[dic[j]] += 1
            if max(tmp) > K:
                flag = 1
                break
        
        if flag:
            break
    if flag:
        continue
    
    answer = min(answer, answer_tmp)

print(answer)

Solution (Python):
from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7


def inp(): return int(sys.stdin.readline())


def inpl(): return list(map(int, sys.stdin.readline().split()))


def inpl_str(): return list(sys.stdin.readline().split())


H, W, K = inpl()
SS = [list(map(int, str(input()))) for _ in range(H)]

ans = INF

for bit in range(1 << H-1):
    tmpSS = []
    nSS = []
    for b in range(H):
        nSS.append(SS[b])
        
        if bit & (1 << b) != 0:
            tmpSS.append(nSS)
            nSS = []

    tmpSS.append(nSS)
    tmp_ans = len(tmpSS) - 1
    nSS = []

    for tmpS in tmpSS:
        L = len(tmpS)
        nS = [0]*W
        for x in range(W):
            for y in range(L):
                nS[x] += tmpS[y][x]
        nSS.append(nS)

    

    L = len(nSS)
    tmpl = [0]*L
    for x in range(W):
        for y in range(L):
            tmpl[y] += nSS[y][x]

        if max(tmpl) > K:
            for y in range(L):
                tmpl[y] = nSS[y][x]
            tmp_ans += 1
            if max(tmpl) > K:
                tmp_ans = INF

    ans = min(ans, tmp_ans)

print(ans)

Solution (Python):
from itertools import accumulate
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
S = [list(map(int, input().rstrip())) for _ in range(H)]
cum = [list(accumulate(S[i])) for i in range(H)]
ans = float('inf')
for bit in range(1 << (H-1)):
    cnt = 0
    prev = -1
    for h in range(H-1):
        cnt += (bit >> h) & 1
    for w in range(W):
        s = 0
        cut = False
        for h in range(H):
            if h > 0 and bit >> (h-1) & 1:
                if s > K:
                    cut = True
                    break
                s = 0
            s += cum[h][w] - (cum[h][prev] if prev >= 0 else 0)
        if s > K:
            cut = True
        if cut:
            if w-1 == prev:
                break
            cnt += 1
            prev = w-1
            continue
    else:
        ans = min(ans, cnt)
print(ans)

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy


from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd

sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    h,w,k = inpm()
    s = [[] for _ in range(h)]
    for i in range(h):
        a = list(input())
        for j in range(w):
            s[i].append(int(a[j]))
    dp = [[0 for _ in range(w+1)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            dp[i][j+1] = dp[i][j] + s[i][j]
    ans = (h-1)+(w-1)
    for e in range(pow(2,h-1)):
        cut = []
        for _ in range(h-1):
            cut.append(e%2)
            e //= 2
        NUM = sum(cut)+1
        DP = [[0 for _ in range(w)] for _ in range(NUM)]
        index = [0 for _ in range(h)]
        for i in range(h-1):
            index[i+1] = index[i] + cut[i]
        for i in range(h):
            for j in range(w):
                DP[index[i]][j] += s[i][j]
        ANS = sum(cut)
        cnt = [0 for _ in range(NUM)]
        for j in range(w):
            for i in range(NUM):
                if cnt[i]+DP[i][j] <= k:
                    cnt[i] += DP[i][j]
                else:
                    ANS += 1
                    for d in range(NUM):
                        cnt[d] = DP[d][j]
                    break
            if j == w-1:
                if max(cnt)>k:
                    ANS = (h-1)+(w-1)
        ans = min(ans,ANS)
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):
def nasu(x):
  L = [0]
  t = x
  cnt = 1
  while t != 0:
    if t & 1:
      L.append(cnt)
    t >>= 1
    cnt += 1
  Ans = len(L) - 1

  L.append(H)
  pr = 0
  for i in range(1, W + 1):
    f = True
    for j in range(1, len(L)):
      k = D[L[j]][i] + D[L[j - 1]][pr] - D[L[j]][pr] - D[L[j - 1]][i]
      if k > K:
        pr = i - 1
        Ans += 1
        
        break     
    else:
      continue
    for j in range(1, len(L)):
      k = D[L[j]][i] + D[L[j - 1]][pr] - D[L[j]][pr] - D[L[j - 1]][i]
      if k > K:
        return 10 ** 10
  
  return Ans

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

N = 2 **(H - 1)

D = [[0] * (W + 1) for _ in range(H + 1)]
for i in range(1, H + 1):
  D[i][1] = S[i - 1][0]

for i in range(1, H + 1):
  for j in range(2, W + 1):
    D[i][j] = D[i][j - 1] + S[i - 1][j - 1]

for i in range(2, H + 1):
  for j in range(W, 1, -1):
    D[i][j] += D[i - 1][j]
  D[i][1] += D[i - 1][1]

Ans = 10 ** 10
for i in range(N):
  Ans = min(Ans, nasu(i))

print(Ans)

Solution (Python):
import sys
input = sys.stdin.readline

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

m = float('inf')
for i in range(1 << (H - 1)) :
  pos = [0] * H
  x = 0
  for j in range(H - 1) :
    if i & (1 << j) :
      x += 1
    pos[j+1] = x
  
  ret = x
  x = 0
  cnt = [0] * H
  flag = 0
  while x < W :
    for y in range(H) :
      cnt[pos[y]] += S[y][x]
      if cnt[pos[y]] > K :
        cnt = [0] * H
        ret += 1
        flag += 1
        break
    else :
      x += 1
      flag = 0
      
    if flag == 2 :
      ret = float('inf')
      break
  
  m = min(m, ret)
  
print(m)

Solution (Python):
import sys
from itertools import combinations as combi
input = sys.stdin.readline
H, W, K = map(int, input().split())
S = [list(input())[: -1] for _ in range(H)]
cs = [[0] * (W + 1) for _ in range(H)]
for i in range(H):
  for j in range(W): cs[i][j + 1] = cs[i][j] + int(S[i][j] == "1")
res = H * W

for t in range(H):
  for c in combi([x for x in range(H - 1)], t):
    l = 0
    tres = 0
    while l < W:
      ok = l
      ng = W + 1
      while ng - ok > 1:
        m = (ok + ng) // 2
        tt = 0
        i = 0
        ttt = 0
        while i < H:
          ttt += cs[i][m] - cs[i][l]
          if i in c:
            tt = max(tt, ttt)
            ttt = 0
          i += 1
        tt = max(tt, ttt)
        if tt <= K: ok = m
        else: ng = m
      if l == ok:
        tres = H * W
        break
      l = ok
      tres += int(l < W)

    
    res = min(res, tres + len(c))
print(res)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    H,W,K=map(int,input().split())
    S=[[] for _ in range(H)]
    for i in range(H):
        S[i]=list(map(int,list(input())))
    ans=INF
    for i in range(2**(H-1)):
        f=True
        tmp=0
        wari=0
        d={}
        d[0]=0
        for j in range(H-1):
            if (i>>j)&1:
                tmp+=1
            d[j+1]=tmp
        wari+=tmp
        l=[0]*H
        for yoko in range(W):
            f=False
            for tate in range(H):
                if S[tate][yoko]:
                    l[d[tate]]+=1
                    if l[d[tate]]>K:
                        wari+=1
                        l=[0]*H
                        f=True
                        break
            if f:
                f2=False
                for tate in range(H):
                    if S[tate][yoko]:
                        l[d[tate]]+=1
                        if l[d[tate]]>K:
                            f2=True
                            break
                if f2:
                    wari=INF
                    break
        ans=min(ans,wari)
    print(ans)
                    
            
            

if __name__ == '__main__':
    main()

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

def check(Bss):
    L = len(Bss)
    accBs = [0] * L
    numCut = 0
    for i in range(W):
        for j in range(L):
            if Bss[j][i] > K:
                return H*W
            if accBs[j] + Bss[j][i] > K:
                accBs = [0] * L
                numCut += 1
                break
        for j in range(L):
            accBs[j] += Bss[j][i]
    return numCut

ans = H*W
for ptn in range(2**(H-1)):
    Bss = []
    Bs = Ass[0]
    numCut = 0
    for i in range(1, H):
        if (ptn>>(i-1)) & 1:  
            Bss.append(Bs)
            Bs = Ass[i]
            numCut += 1
        else:  
            Bs = [B+A for B, A in zip(Bs, Ass[i])]
    Bss.append(Bs)

    numCut += check(Bss)
    ans = min(ans, numCut)

print(ans)

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

count_table = []
for line in s:
	counts = [0]
	count = 0
	for c in line:
		if c == 1:
			count += 1
		counts.append(count)
	count_table.append(counts)

def check_limit(groups, last_div, x):
	for g in groups:
		whites = 0
		for y in g:
			counts = count_table[y]
			whites += counts[x + 1] - counts[last_div]
			if whites > K:
				return False
	return True

def check(groups):
	count = 0
	last_div = 0
	divides = 0
	for x in range(W):
		if not check_limit(groups, last_div, x):
			if last_div == x:
				return None
			else:
				divides += 1
				last_div = x
	return divides

min_total = W + H

for i in range(2 ** (H - 1)):
	div = []
	n = i
	divides_h = 0
	for j in range(H - 1):
		if n % 2 == 0:
			div.append(True)
			divides_h += 1
		else:
			div.append(False)
		n = n // 2
	cur_group = [0]
	groups = [cur_group]
	for j in range(H - 1):
		if div[j]:
			cur_group = [j + 1]
			groups.append(cur_group)
		else:
			cur_group.append(j + 1)
	divides_v = check(groups)
	if divides_v != None and divides_h + divides_v < min_total:
		min_total = divides_h + divides_v

print(min_total)

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

n = h

final = 10000000

for ii in range(2**(n-1)):
    ans = 0
    op = [0]*(n-1)
    cnt = 1
    for j in range((n-1)):
        if (ii >> j) & 1:
            op[j] = 1
            cnt += 1
            ans += 1
    
    opp = [0]
    for i in range(n-1):
        opp.append(opp[-1]+op[i])
    h_block = [0]*cnt
    for j in range(w):
        err = False
        tmp = [0]*cnt
        for i in range(h):
            if s[i][j] == '1':
                tmp[opp[i]] += 1
        if max(tmp) > k:
            err = True
            break
        if any(tmp[i] + h_block[i] > k for i in range(cnt)):
                ans +=1
                h_block = tmp[:]
        else:
            for i in range(cnt):
                h_block[i] += tmp[i]
    if err:
        continue
    final = min(final,ans)

print(final)

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

ans = H*W
S2 = [[0]*(W+1) for _ in [0]*(H+1)]
for i in range(H):
    for j in range(W):
        S2[i+1][j+1] = S2[i][j+1] + S[i][j]
for i in range(1,H+1):
    for j in range(W):
        S2[i][j+1] += S2[i][j]

for i in range(1<<(H-1)):
    check = [0]+[j+1 for j in range(H-1) if i>>j&1]+[H]
    cnt = len(check)-2
    l = 0
    r = 1
    while r<=W:
        for j,k in zip(check[:-1],check[1:]):
            if S2[j][l] + S2[k][r] - S2[j][r] - S2[k][l] > K:
                if r==l+1:
                    cnt += H*W
                    r = W+1
                    break
                cnt += 1
                l = r-1
                r = r
                break
        else:
            r += 1
    ans = min(ans,cnt)
print(ans)

Solution (Python):
def main():
    from itertools import product
    h, w, K = map(int, input().split())
    grid = [list(input()) for _ in [0]*h]
    m = 10**9
    for i in range(2**h):
        i = (("0"*h)+bin(i)[2:])[-h:]+"2"
        memo = [0]
        for j in range(h):
            if i[j] == i[j+1]:
                pass
            else:
                memo.append(j+1)
        ans = len(memo)-1
        ans2 = [0]
        memo2 = [0]*ans
        j = 0
        flag = False
        while j < w:
            if flag:
                break
            for k in range(ans):
                memo2[k] += [grid[l][j]
                             for l in range(memo[k], memo[k+1])].count("1")
                if memo2[k] > K:
                    ans2.append(j)
                    memo2 = [0]*ans
                    if ans2[-1] == ans2[-2]:
                        flag = True
                    break
            else:
                j += 1
        if flag == False:
            m = min(m, ans+(len(ans2)-2))
    print(m)


main()

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

ans = 10 ** 18
for i in range(1 << (h-1)):
    possible = True
    x = i
    cut = [0] * (h-1)
    for j in range(h-1):
        cut[j] = x & 1
        x >>= 1
    index = [0] * h
    for j in range(h-1):
        index[j+1] = index[j] + cut[j]
    n = index[h-1] + 1

    s = [0 for _ in range(n)]
    ver = 0
    for j in range(w):
        need = False
        for z in range(h):
            s[index[z]] += int(f[z][j])
            if s[index[z]] > k:
                need = True
        if need:
            ver += 1
            s = [0 for _ in range(n)]
            for z in range(h):
                s[index[z]] += int(f[z][j])
                if s[index[z]] > k:
                    possible = False
    if possible:
        ans = min(ans, sum(cut) + ver)
print(ans)

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
h,w,k=map(int,input().split())
S=[input() for _ in range(h)]
ans=float("inf")
import bisect
for i in range(2**(h-1)):
  Cut=[]
  cur=0
  for ii in range(h-1):
    if i&(1<<ii):
      Cut.append(ii)
  p=len(Cut)+1
  Num=[0]*h
  for ii in range(h):
    Num[ii]=bisect.bisect_left(Cut,ii)

  A=[0]*p
  Chk=True
  for j in range(w):
    B=[0]*p    
    for jj in range(h):
      if S[jj][j]=="1":
        B[Num[jj]]+=1
    for jj in range(p):
      if B[jj]>k:
        Chk=False
      if A[jj]+B[jj]>k:
        cur+=1
        A=B
        break
      else:
        continue
    else:
      for jjj in range(p):
        A[jjj]+=B[jjj]
  if Chk:
    ans=min(ans,cur+p-1)
print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read




h,w,k = [int(i) for i in readline().split()]
b = [readline() for _ in range(h)]

ans = INF = 10**9
N = 2**(h-1)


for mask in range(N):
    res = [(mask>>j)&1 for j in range(h-1)]
    
    R = []
    now = [0]
    for i in range(h-1):
        if res[i] == 0:
            now.append(i+1)
        else:
            R.append(now[:])
            now = [i+1]
    if now: R.append(now[:])
    
    L = len(R)
    val = res.count(1)

    num = [0]*L
    for i in range(w):
        nnum = [0]*L
        for j in range(L):
            p = 0
            for kk in R[j]:
                if b[kk][i]=="1": p += 1
            nnum[j] = p
        
        
        for j in range(L):   
            if num[j] + nnum[j] > k:
                val += 1
                num = nnum
                break
        else:
            for j in range(L): num[j] += nnum[j]
        
        
        if any(ni>k for ni in nnum):
            val = INF
            break
    
    
    ans = min(ans,val)

print(ans)