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
from itertools import product
 
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
 
C = [[int(s[i]) for s in S] for i in range(W)]
 
total = sum(sum(c) for c in C)
 
if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):
    
    ans = sum(X)
    if ans > answer:
      continue
    M = [[0]]
    for i, x in enumerate(X):
      if x:
        M.append([])
      M[-1].append(i+1)
    D = [0] * len(M)
    for c in C:
      for k, m in enumerate(M):
        D[k] += sum(c[i] for i in m)
        
      if any(d > K for d in D):
        ans += 1
        if ans > answer:
          break
        D = [sum(c[i] for i in m) for m in M]
        if any(d > K for d in D):
          ans = answer + 1
          break
    answer = min(answer, ans)

print(answer)

Solution (Python):
from collections import defaultdict
from itertools import product
 
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
 
i = 0
while i < len(S):
  if '1' in S[i]:
    i += 1
  else:
    del S[i]
H = len(S)
 
C = [[int(s[i]) for s in S] for i in range(W)]
 
total = sum(sum(c) for c in C)
 
if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):
    
    ans = sum(X)
    if ans > answer:
      continue
    M = [[0]]
    for i, x in enumerate(X):
      if x:
        M.append([])
      M[-1].append(i+1)
    D = [0] * len(M)
    for c in C:
      for k, m in enumerate(M):
        D[k] += sum(c[i] for i in m)
        
      if any(d > K for d in D):
        ans += 1
        if ans > answer:
          break
        D = [sum(c[i] for i in m) for m in M]
        if any(d > K for d in D):
          ans = answer + 1
          break
    answer = min(answer, ans)

print(answer)

Solution (Python):
def W_tips(j):
    global K,g,now,tips
    for i in range(g):
        now[i]+=tips[i][j]
    for i in range(g):
        if now[i] > K:
            return False
    return True

f_inf=float("inf")
H,W,K=map(int,input().split())
S=[list(map(int,list(input()))) for _ in range(H)]
ans = f_inf
for div in range(1 << (H-1)):
    g=0
    tips=[[0]*W]
    tips[g]=[s+b for s, b in zip(S[0],tips[g])]
    for i in range(1,H):
        if div >> (i-1) &1:
            g+=1
            tips.append([0]*W)
        tips[g]=[s + b for s, b in zip(S[i],tips[g])]
    num=g
    g+=1
    now=[0]*g
    for j in range(W):
        if W_tips(j)==False:
            num+=1
            now=[0]*g
            if W_tips(j)==False:
                num=f_inf
                break
    ans=min(ans,num)
print(ans)

Solution (Python):
import sys
from itertools import accumulate

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
S = [list(map(int, sr())) for _ in range(H)]
Scum = [list(accumulate(x)) for x in S]
answer = 10000
for bit in range(1<<(H-1)):
    count = 0
    for i in range(H-1):
        if bit >> i & 1:
            count += 1
    bit += 1 << H-1 
    
    prev = -1
    w = 0
    while w < W:
        white = 0
        cut = False
        for i in range(H):
            white += Scum[i][w] - (Scum[i][prev] if prev >= 0 else 0)
            if (bit >> i) & 1: 
                if white > K:
                    cut = True
                white = 0
        if cut:
            if prev == w-1: 
                break
            count += 1
            prev = w-1
        else:
            w += 1
    else:
        answer = min(answer, count)

print(answer)

Solution (Python):
def read():
    H, W, K = list(map(int, input().strip().split()))
    S = list()
    for i in range(H):
        s = list(map(int, input()))
        S.append(s)
    return H, W, K, S


def init_n_splits(H, ptn):
    n_splits = 0
    for h in range(1, H):
        if ptn & 1 == 1:
            n_splits += 1
        ptn >>= 1
    return n_splits


def check_first_column(w, H, K, ptn, S):
    k = [0 for h in range(H)]
    k[0] = S[0][w]
    if k[0] > K:
        return [-1 for h in range(H)]
    for h in range(1, H):
        if ptn & 1 == 1:
            k[h] = S[h][w]
        else:
            k[h] = S[h][w] + k[h-1]
        if k[h] > K:
            return [-1 for h in range(H)]
        ptn >>= 1
    return k


def check_next_column(w, H, K, ptn, S, prev):
    k = [0 for h in range(H)]
    k[0] = S[0][w]
    if k[0] + prev[0] > K:
        return [-1 for h in range(H)]
    for h in range(1, H):
        if ptn & 1 == 1:
            k[h] = S[h][w]
        else:
            k[h] = S[h][w] + k[h-1]
        if k[h] + prev[h] > K:
            return [-1 for h in range(H)]
        ptn >>= 1
    return [i + j for i, j in zip(k, prev)]


def solve(H, W, K, S, INF=10000000):
    ptns = 2 ** (H-1)
    min_n_splits = W * H
    for ptn in range(ptns):
        update = True
        n_splits = init_n_splits(H, ptn)
        ret = check_first_column(0, H, K, ptn, S)
        if ret[0] == -1:
            update = False
        else:
            for w in range(1, W):
                prev = ret
                ret = check_next_column(w, H, K, ptn, S, prev)
                if ret[0] == -1:
                    n_splits += 1
                    ret = check_first_column(w, H, K, ptn, S)
                    if ret[0] == -1:
                        update = False
                        break
        if update:
            min_n_splits = min(n_splits, min_n_splits)
    return min_n_splits

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Solution (Python):
import itertools

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
ans = 1e4
for t in itertools.product([0, 1], repeat=H-1):
    cnt = t.count(1)
    SW = []
    tmp = [int(s) for s in S[0]]
    for i, c in enumerate(t):
        if c:
            SW.append(tmp)
            tmp = [int(s) for s in S[i+1]]
        else:
            tmp = [tmp[j] + int(S[i+1][j]) for j in range(W)]
    SW.append(tmp)
    H_ = len(SW)
    sums = [0] * H_
    if max(itertools.chain.from_iterable(SW)) > K:
        continue
    for w in range(W):
        sumtmp = [sums[i] + SW[i][w] for i in range(H_)]
        if max(sumtmp) > K:
            cnt += 1
            sums = [SW[i][w] for i in range(H_)]
        else:
            sums = sumtmp
    ans = min(ans, cnt)
print(ans)

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

sumtable=[[0 for i in range(0,W)] for j in range(0,H+1)]
for i in range(1,H+1):
    for j in range(0,W):
        sumtable[i][j]=sumtable[i-1][j]+(int(S[i-1][j])&1)


ans=10**4
for i in range(0,2**(H-1)):
    segment=[]
    start=0
    end=0
    for j in range(0,H-1):
        if (i>>j) & 1==1:
            end=j
            segment.append((start,end))
            start=end+1
    segment.append((start,H-1))
    white=[0 for j in range(0,len(segment))]
    count=0
    for j in range(0,W):
        for k in range(0,len(segment)):
            start,end=segment[k]
            white[k]+=sumtable[end+1][j]-sumtable[start][j]
        if max(white)>K:
            count+=1
            for k in range(0,len(segment)):
                start,end=segment[k]
                white[k]=sumtable[end+1][j]-sumtable[start][j]
            if max(white)>K:
                break
    else:
        test=count+len(segment)-1
        if test<ans:
            ans=test

print(ans)

Solution (Python):
h, w, k = map(int, input().split())
S = [ [ int(i) for i in input()] for _ in range(h) ]
res = 10**4
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 = 10**4
            break

    res = min(res, ret)
print(res)

Solution (Python):
import sys


def main():
    h,w,k=map(int,input().split())
    s=[list(input()) for _ in range(h)]
    cnt=[[0]*(w+1) for _ in range(h+1)]

    for i in range(1,h+1):
        for j in range(1,w+1):
            flg=int(s[i-1][j-1])
            if i==0 and j==0:
                cnt[i][j]=flg
            elif i==0:
                cnt[i][j]=cnt[i][j-1]+flg
            elif j==0:
                cnt[i][j]=cnt[i-1][j]+flg
            else:
                cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+flg
    ans=h+w+1
    for p in range(1<<(h-1)):
        g=[0]*(h+1)
        gnum,gcnt=0,0
        for i in range(h-1):
            if p>>i&1:
                gnum+=1
                g[gnum]=i+1
        gcnt+=gnum
        gnum+=1
        g[gnum]=h
        sw,j=1,2
        while j<=w:
            for i in range(1,gnum+1):
                if cnt[g[i]][sw]-cnt[g[i]][sw-1]-cnt[g[i-1]][sw]+cnt[g[i-1]][sw-1]>k:
                    gcnt=h+w+2
                    j=w
                    break            
            for i in range(1,gnum+1):
                if cnt[g[i]][j]-cnt[g[i]][sw-1]-cnt[g[i-1]][j]+cnt[g[i-1]][sw-1]>k:
                    sw=j
                    gcnt+=1
                    break
            j+=1
        ans=min(ans,gcnt)
    print(ans)

if __name__ == '__main__':
    main()

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

ans = float('inf')
for div in range(2 ** (H - 1)):
    g = 0
    ids = [0] * H
    for i in range(H):
        ids[i] = g
        if div >> i & 1:
            g += 1
    g += 1

    c = [[0 for _ in range(1005)] for _ in range(10)]
    for i in range(H):
        for j in range(W):
            c[ids[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]
            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 = float('inf')
                break

    ans = min(ans, num)
print(ans)

Solution (Python):
H,W,K = map(int,input().split())
A = [0]*H
for i in range(H):
    A[i] = input()
s = 10000
for i in range(2**(H-1)):
    count = 0
    B = [0]*H
    B[H-1] = 1
    for j in range(H-1):
        if ((i >> j) & 1):
            B[j] = 1
            count += 1
    C = [0]*(count + 1)
    for j in range(W):
        a = [0]*(count + 1)
        n = 0
        max = C[0]
        maxa = a[0]
        for k in range(H):
            a[n] += int(A[k][j])
            C[n] += int(A[k][j])
            if B[k] == 1:
                if max < C[n]:
                    max = C[n]
                if maxa < a[n]:
                    maxa = a[n]
                n += 1
        if max > K:
            count += 1
            C[:] = a[:]
        if maxa > K:
            count = 10000
            break
    if s > count:
        s = count
print(s)

Solution (Python):
H, W, K = map(int, input().split())
S = [0] * H
INF = 1000000

for h in range(H):
    S[h] = list(input())


def check(divH):
    MAP = [0] * H
    BitDivH = "".join(["{:0", str(H - 1), "b}"]).format(divH)
    cnt = 0
    for i, bit in enumerate(BitDivH):
        if bit == "1":
            cnt += 1
            MAP[i + 1] = cnt
        else:
            MAP[i + 1] = cnt
    after_tmp = [0] * (MAP[-1] + 1)
    cnt = 0
    out = 0
    for w in range(W):
        for h in range(H):
            after_tmp[MAP[h]] += int(S[h][w])
        for af in after_tmp:
            if af > K:
                out = 1
                break
        else:
            after_tmp = [0] * (MAP[-1] + 1)
    if out == 1:
        return INF
    else:
        for w in range(W):
            for h in range(H):
                after_tmp[MAP[h]] += int(S[h][w])
            for af in after_tmp:
                if af > K:
                    cnt += 1
                    after_tmp = [0] * (MAP[-1] + 1)
                    for h2 in range(H):
                        after_tmp[MAP[h2]] += int(S[h2][w])
                    break
        return cnt + MAP[-1]

MIN = INF
for i in range(2**(H - 1)):
    MIN = min(MIN, check(i))

print(MIN)

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

for h in range(H):
    S[h] = list(input())


def check(divH):
    MAP = [0] * H
    BitDivH = "".join(["{:0", str(H - 1), "b}"]).format(divH)
    cnt = 0
    for i, bit in enumerate(BitDivH):
        if bit == "1":
            cnt += 1
            MAP[i + 1] = cnt
        else:
            MAP[i + 1] = cnt
    after_tmp = [0] * (MAP[-1] + 1)
    cnt = 0
    out = 0
    for w in range(W):
        for h in range(H):
            after_tmp[MAP[h]] += int(S[h][w])
        for af in after_tmp:
            if af > K:
                out = 1
                break
        else:
            after_tmp = [0] * (MAP[-1] + 1)
    if out == 1:
        return 1000000
    else:
        for w in range(W):
            for h in range(H):
                after_tmp[MAP[h]] += int(S[h][w])
            for af in after_tmp:
                if af > K:
                    cnt += 1
                    after_tmp = [0] * (MAP[-1] + 1)
                    for h2 in range(H):
                        after_tmp[MAP[h2]] += int(S[h2][w])
                    break
        return cnt + MAP[-1]

MIN = 1000000
for i in range(2**(H - 1)):
    MIN = min(MIN, check(i))

print(MIN)

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

for i in range(2**(H-1)):
    s = set()
    
    for j in range(H-1):
        if (i>>j)&1:
            s.add(j)
    
    cnt = [0]*(len(s)+1)
    ans_cand = len(s)
    
    for j in range(W):
        add = [0]*(len(s)+1)
        add_idx = 0
        
        for k in range(H):
            add[add_idx] += S[k][j]
        
            if k in s:
                add_idx += 1
        
        if max(add)>K:
            ans_cand = 10**18
            break
        
        for k in range(len(s)+1):
            if cnt[k]+add[k]>K:
                ans_cand += 1
                
                for l in range(len(s)+1):
                    cnt[l] = add[l]
                    
                break
        else:
            for k in range(len(s)+1):
                cnt[k] += add[k]
        
    ans = min(ans, ans_cand)
    
print(ans)

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):
def main():
    H, W, K = map(int, input().split())
    S = [input() for i in range(H)]
    ans = H * W

    for pat in range(2 ** (H - 1)):
        Cnt_sum = [0] * H  
        ans_w = 0
        ans_h =  bin(pat).count('1')
        fail = False
        for j in range(W): 
            if fail:
                break
            s = 0 
            Cnt = [0] * H
            for i in range(H):
                if (S[i][j] == '1'):
                    Cnt[s] += 1
                    Cnt_sum[s] += 1

                if Cnt[s] > K:
                    fail = True
                    break

                if (1 << i) & pat > 0: 
                    s += 1

            if any([v > K for v in Cnt_sum]):
                ans_w += 1
                Cnt_sum = Cnt[::]
        else:
            ans = min(ans, ans_h + ans_w)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,boundary=1,search=[],replacement_of_found='.',mp_def={'

    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
def show2d(g,h,w):
    for i in range(h):show(g[i*w:i*w+w])

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

h,w,k=LI()

ans=0
s=[]
for i in range(h):
    s.append([int(i)for i in input()])

ad=[[0]*(w+1)for i in range(h+1)]
for i in range(h):
    for j in range(w):
        ad[i+1][j+1]=ad[i][j+1]+ad[i+1][j]-ad[i][j]+s[i][j]

def check(ls):
    rt=[0]
    border=0
    wbg=0
    fl=False
    for wed in range(1,w+1):
        hbg=0
        for j in ls:
            hed=j
            cnt=ad[hed][wed]-ad[hed][wbg]-ad[hbg][wed]+ad[hbg][wbg]
            
            if cnt>k:
                fl=True
                border=wed-1
                
                break
            hbg=j
        if fl:
            if rt[-1]==border:
                return []
            wbg=wed-1
            rt+=[border]
            fl=False
    return rt

ans=h+w
bg=0
ed=h
for i in range(1<<(h-1)):
    c=[]
    for j in range(h-1):
        if i>>j&1:
            c+=[j+1]
    c+=[h]
    rt=check(c)
    if rt==[]:
        continue
    wcut=len(rt)
    ans=min(ans,len(c)-1+wcut-1)


print(ans)

Solution (Python):
from collections import defaultdict
from itertools import product
 
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
 
i = 0
while i < len(S):
  if '1' in S[i]:
    i += 1
  else:
    del S[i]
H = len(S)
 
C = [[int(s[i]) for s in S] for i in range(W)]
 
total = sum(sum(c) for c in C)
 
if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):
    ans = sum(X)
    if ans > answer:
      continue
    M = [[0]]
    for i, x in enumerate(X):
      if x:
        M.append([])
      M[-1].append(i+1)
    D = [0] * len(M)
    for c in C:
      for k, m in enumerate(M):
        D[k] += sum(c[i] for i in m)
      if any(d > K for d in D):
        ans += 1
        if ans > answer:
          break
        D = [sum(c[i] for i in m) for m in M]
        if any(d > K for d in D):
          ans = answer + 1
          break
    answer = min(answer, ans)
   
print(answer)

Solution (Python):
import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = np.array([[0 for _ in range(w)]])
    cnt = 0
    start = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo = np.concatenate((kouryo, s_arr[start:j+1].sum(axis=0, keepdims=True)), axis=0)
            start=j+1
    kouryo = np.concatenate((kouryo, s_arr[start:].sum(axis=0, keepdims=True)), axis=0)

    if cnt > ans: continue
    if np.any(kouryo>k): continue

    wa = np.array([0 for _ in range(len(kouryo))])
    for j in range(w):
        wa += kouryo[:, j]
        if np.max(wa)>k:
            cnt += 1
            if cnt > ans: break
            wa = kouryo[:, j]
    ans = min(ans, cnt)
print(ans)

Solution (Python):
def can_merge(K: int, prev_cnt: list, cur_cnt: list) -> bool:
    ret = True
    for i, _ in enumerate(cur_cnt):
        if prev_cnt[i] + cur_cnt[i] > K:
            ret = False
            break
    return ret

def merge(prev_cnt: list, cur_cnt: list):
    for i, _ in enumerate(cur_cnt):
        prev_cnt[i] += cur_cnt[i]

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

    min_split_num = 999+9
    for hbitv in range(2**(H-1)):
        split_num = bin(hbitv).count('1')
        region_num = split_num + 1
        prev_cnt = [0] * region_num

        
        for w in range(W):
            impossible_hbitv = False
            cur_cnt = [0] * region_num

            
            
            ri = 0
            for h in range(H):
                if S[h][w] == '1':
                    cur_cnt[ri] += 1
                    if cur_cnt[ri] > K:
                        impossible_hbitv = True
                        break

                if (hbitv >> h) % 0b10 == 1:
                    ri += 1

            if impossible_hbitv:
                break

            if can_merge(K, prev_cnt, cur_cnt):
                merge(prev_cnt, cur_cnt)
            else:
                split_num += 1
                prev_cnt, cur_cnt = cur_cnt, prev_cnt
        
        if not impossible_hbitv:
            min_split_num = min(min_split_num, split_num)

    print(min_split_num)
            
if __name__ == '__main__':
    main()

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

ans = 10 ** 6

def calc(lst): 
    n = sum(lst) + 1 
    tmp = [0] * n
    count = n - 1 
    for w in range(W):
        position = 0
        now = [0] * n
        for h in range(H):
            if S[h][w] == '1': 
                now[position] += 1
            if lst[h] == 1:
                position += 1
        
        flag = True
        for i in range(n):
            if tmp[i] + now[i] > K:
                flag = False

        if flag:
            for i in range(n):
                tmp[i] += now[i]
        else:
            count += 1
            for i in range(n):
                tmp[i] = now[i]
    for i in range(n):
        if now[i] > K:
            count += 10 ** 6
            
    return count

for i in range(2 ** (H - 1)):
    lst = [0] * (H)
    for j in range(H - 1):
        if (i >> j) & 1:
            lst[j] = 1
    ans = min(calc(lst), ans)

print (ans)

Solution (Python):
from itertools import product
h, w, k = map(int, input().split())
CHOCO = [list(map(int, input())) for _ in range(h)]



INF = 10**5






it = ["01"]*(h-1)
ans = INF
for x in product(*it):
    
    
    cnt = sum(map(int, x))

    
    agg = [[0]*(w) for _ in range(cnt+1)]
    *ls, = map(int, x+('1',))
    for i in range(w):
        prev = c = 0
        for j, split in enumerate(ls):
            if split:
                agg[c][i] = prev+CHOCO[j][i]
                prev = 0
                c += 1
            else:
                prev += CHOCO[j][i]
    

    
    
    tmp = [0]*(cnt+1)
    for xyz in zip(*agg):
        cannot_split = False
        can_continue = True
        for i, x in enumerate(xyz):
            if x > k:
                cannot_split = True
                break
            if x+tmp[i] > k:
                can_continue = False
                break

        if cannot_split:
            break

        if can_continue:
            for i, x in enumerate(xyz):
                tmp[i] += x
                continue
        else:
            for i, x in enumerate(xyz):
                tmp[i] = x
            cnt += 1

    if cannot_split:
        continue
    
    ans = min(ans, cnt)
print(ans)

Solution (Python):
from itertools import product
h, w, k = map(int, input().split())
CHOCO = [list(map(int, input())) for _ in range(h)]
INF = 10**5

it = ["01"]*(h-1)
ans = INF
for x in product(*it):
    cnt = sum(map(int, x))
    agg = [[0]*(w) for _ in range(cnt+1)]
    *ls, = map(int, x+('1',))
    for i in range(w):
        prev = c = 0
        for j, split in enumerate(ls):
            if split:
                agg[c][i] = prev+CHOCO[j][i]
                prev = 0
                c += 1
            else:
                prev += CHOCO[j][i]

    tmp = [0]*(cnt+1)
    cannot_split = False

    for xyz in zip(*agg):
        cannot_split = False
        can_continue = True
        for i, x in enumerate(xyz):
            if x > k:
                cannot_split = True
                break
            if x+tmp[i] > k:
                can_continue = False
                break

        if cannot_split:
            break

        if can_continue:
            for i, x in enumerate(xyz):
                tmp[i] += x
                continue
        else:
            for i, x in enumerate(xyz):
                tmp[i] = x
            cnt += 1

    if cannot_split:
        continue

    ans = min(ans, cnt)
print(ans)

Solution (Python):
import sys,math
sys.setrecursionlimit(10**9)
from collections import defaultdict
 
IA = lambda: map(int,input().split())
IAS= lambda: map(str,input().split())

n,m,K=IA()
a=["" for i in range(0,n)]
for i in range(0,n):
    a[i]=input()

ans=n*m+1
for k in range(0,1<<(n-1)):
    res=0
    temp=[]
    for j in range(0,(n-1)):
        if (k&(1<<(j)))!=0:
            temp.append(j)
            res+=1
    le=len(temp) 
    if le==0:
        temp.append(n-1)
        
    if temp[le-1]!=n-1:
        temp.append(n-1)
        
    le=len(temp) 
  


    
    sum1=[0 for i in range(0,11)]
    flag=0
    for j in range(0,m):
        if flag==1:break
        last=0
        for t in range(0,le):
            for w in range(last,temp[t]+1):
                if a[w][j]=='1':
                    sum1[t]+=1
            last=temp[t]+1
            
            if sum1[t]>K:
                res+=1
                last=0
                sum1=[0 for i in range(0,11)]
                for t1 in range(0,le):
                    if flag==1:break
                    for w1 in range(last,temp[t1]+1):
                        if a[w1][j]=='1':
                            sum1[t1]+=1
                    
                    if sum1[t1]>K:
                        flag=1
                        res=n*m+1
                        break
                    last=temp[t1]+1
                break
        if flag==1:break
     
    ans=min(res,ans)
                
            
    
print(ans)

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

ans = 10 ** 5
for bit in range(2 ** (H - 1)):    
    group = [0] * H
    gnum = 0

    
    for i in range(H - 1):
        if not bit >> i & 1:
            group[i + 1] = group[i]
        else:
            group[i + 1] = group[i] + 1
            gnum += 1

    gok = True
    add = 0  
    nums = [0] * (gnum + 1)  
    
    for j in range(W):
        ones = [0] * (gnum + 1)
        ok = True
        
        for i in range(H):
            ones[group[i]] += int(S[i][j])
            nums[group[i]] += int(S[i][j])
            if ones[group[i]] > K: gok = False;
            if nums[group[i]] > K: ok = False;

        if not ok:
            add += 1
            nums = ones[:]
            
    if gok:
        ans = min(ans, gnum + add)
                
    
print(ans)

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

ans = 10 ** 5
for bit in range(2 ** (H - 1)):    
    cur = [0] * H
    gnum = 0

    
    for i in range(H - 1):
        if not (bit & (1 << i)):
            cur[i + 1] = cur[i]
        else:
            cur[i + 1] = cur[i] + 1
            gnum += 1

    gok = True
    add = 0
    nums = [0] * (gnum + 1)
    
    for j in range(W):
        ones = [0] * (gnum + 1)
        ok = True
        
        for i in range(H):
            ones[cur[i]] += int(S[i][j])
            nums[cur[i]] += int(S[i][j])
            if ones[cur[i]] > K: gok = False;
            if nums[cur[i]] > K: ok = False;
                
        if not ok:
            add += 1
            nums = ones[:]
            
    if gok:
        ans = min(ans, gnum + add)
                
    
print(ans)