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

def main():
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    if S.sum() <= K:
        print(0)
        exit(0)
    answer = float('INF')
    for i in range(0, 2 ** (H - 1)):
        horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
        result = greedy(W, S, K, horizons, answer)
        answer = min(answer, result)
    print(answer)


def greedy(W, S, K, horizons, current_answer):
    answer = sum(horizons)
    
    
    
    
    
    
    
    
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0).tolist())
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0).tolist())
    
    h = len(S2)
    partial_sums = [0] * h
    for right in range(W):
        current = [0] * h
        for idx in range(h):
            current[idx] = S2[idx][right]
            partial_sums[idx] += S2[idx][right]
        
        if max(current) > K:
            return float('INF')
        
        if max(partial_sums) > K:
            answer += 1
            if answer >= current_answer:
                return float('INF')
            partial_sums = current
    return answer

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
from itertools import product
H, W, K = map(int, input().split())
G = np.array([list(map(int, list(input()))) for _ in range(H)])
 
ans = float('inf')
for pattern in product([0, 1], repeat=H - 1):
    
    div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [10]
 
    
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0))
 
    
    if [r for r in rows if np.any(r > K)]:
        continue
 
    
    rows = [r.tolist() for r in rows]
    tmp_ans = 0
    counts = [0] * len(rows)
    w = 0
    while w < W:
        for r in range(len(rows)):
            counts[r] += rows[r][w]
        if any([c > K for c in counts]):
            counts = [0] * len(rows)
            w -= 1
            tmp_ans += 1
        w += 1
 
    
    tmp_ans += len(div) - 2
    ans = min(ans, tmp_ans)
 
print(ans)

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

ssum = [[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if i == 0:
      ssum[i][j] = s[i][j]
    else:
      ssum[i][j] = ssum[i-1][j] + s[i][j]

def cnt(line,i,j):
  if i == 0:
    return ssum[j-1][line]
  else:
    return ssum[j-1][line] - ssum[i-1][line]

ans = 10**6
for i in range(2**(h-1)):
  l = [0]
  s = 0
  for j in range(h):
    if i >> j & 1:
      s += 1
      l.append(j+1)
  l.append(h)
  d = [0]*(len(l)-1)
  for j in range(w):
    nxt = [cnt(j,l[k],l[k+1]) for k in range(len(l)-1)]
    d2 = [nxt[i]+d[i] for i in range(len(l)-1)]
    if max(nxt) > K:
      s = 10**7
      break
    if max(d2) > K:
      d = nxt
      s += 1
    else:
      d = d2
  ans = min(ans,s)
print(ans)

Solution (Python):



def _f(H, W, S):
    '''
    >>> f = _f(3, 3, [[1, 0, 0], [1, 0, 1], [0, 1, 1]])
    >>> f(0, 0, 1, 1)
    1
    >>> f(0, 0, 3, 0)
    0
    >>> f(0, 0, 3, 1)
    2
    >>> f(1, 1, 3, 3)
    3
    >>> f(0, 0, 3, 3)
    5
    >>> f(2, 0, 3, 3)
    2
    '''
    acc = [[0] * (W + 1) for _ in range(H+1)]
    for h in range(1, H+1):
        for w in range(1, W+1):
            acc[h][w] = acc[h][w-1] + acc[h-1][w] - acc[h-1][w-1] + S[h-1][w-1]

    def f(sh, sw, eh, ew):
        return acc[eh][ew] + acc[sh][sw] - acc[sh][ew] - acc[eh][sw]

    return f

def _solve(H, W, K, S, c, f):
    
    sw = 0
    cut = 0
    for ew in range(1, W+1):
        
        if any(f(sh, ew-1, eh, ew) > K for sh, eh in c):
            return float('inf')
        if any(f(sh, sw, eh, ew) > K for sh, eh in c):
            cut += 1
            sw = ew - 1
    return cut


def solve(H, W, K, S):
    from itertools import product, compress
    f = _f(H, W, S)
    ans = float('inf')
    for flag in product(range(2), repeat=H-1):
        t = (0,) + tuple(compress(range(1,H), flag)) + (H,)
        c = tuple(zip(t, t[1:]))
        ans = min(ans, _solve(H, W, K, S, c, f)+sum(flag))
    return ans


    


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

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

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

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

ans = float('inf')

for i in range(2 ** (h-1)):
    
    sep = [0]
    for j in range(h-1):
        if i & (1 << j):
            sep.append(j+1)

    memo = [0 for _ in range(len(sep))]
    cnt = 0
    

    
    

    for k in range(w):
        
        memo2 = [0 for _ in range(len(sep))]
        sep_index = 0
        for l in range(h):
            
            if sep_index < len(sep) - 1 and sep[sep_index+1] <= l:
                sep_index += 1
                
            if s[l][k] == '1':
                if memo[sep_index] + memo2[sep_index] == K:
                    cnt += 1
                    memo = [0 for _ in range(len(sep))]
                memo2[sep_index] += 1
                if memo2[sep_index] > K:
                    cnt += ans
        for ii in range(len(sep)):
            memo[ii] += memo2[ii]
    ans = min(ans, cnt + len(sep) - 1)

print(ans)

Solution (Python):

import heapq
from collections import defaultdict, deque

from itertools import accumulate, permutations
import sys
import bisect


sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
msi = lambda: map(str, input().split())
lmii = lambda: list(map(int, input().split()))
lmsi = lambda: list(map(str, input().split()))
smii = lambda: sorted(map(int, input().split()))


H, W, K = mii()
S = []
for i in range(H):
    S.append(si())

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

    c = [[0] * W for _ in range(g+1)]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '1':
                c[id[i]][j] += 1

    now = defaultdict(int)

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

    num = g
    for j in range(W):
        if not add(j):
            num += 1
            now = defaultdict(int)
            if not add(j):
                num = INF
                break

    ans = min(ans, num)

print(ans)

Solution (Python):
import numpy as np
from itertools import product
H, W, K = map(int, input().split())
G = np.array([list(map(int, input())) for _ in range(H)])
 
ans = float('inf')

for pattern in product([0, 1], repeat=H - 1):
    
    div=[0]
    for i, p in enumerate(pattern):
      if p==1:
        div= div+[i+1]
    div += [10]       
    
     
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0))
    
     
    count=0
    for r in rows:
      if np.any(r>K):
        count=1
    if count==1:
      continue
    
    
    rows = [r.tolist() for r in rows]
    tmp_ans = 0
    counts = [0] * len(rows)
    w = 0
    
    while w<W:
      for r in range(len(rows)):
        counts[r] += rows[r][w]
        
      if any([c>K for c in counts]):
        counts=[0] * len(rows)
        w -=1
        tmp_ans += 1
      
      w+=1
    a=tmp_ans +len(div)-2
    ans=min(a,ans)
  
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6) 
import math
from copy import copy, deepcopy
from operator import itemgetter

from bisect import bisect_left, bisect, bisect_right

from collections import deque 



from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds





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


S = [list(map(int, list(input()))) for i in range(H)]
rui=[[0]*(W+1) for _ in range(H)]
tate=[False]*(H-1)

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

ans=H*W
for tcut in range(2**(H-1)):
    ncut=0
    for h in range(H-1): 
        if tcut >> h &1:
            tate[h]=True
            ncut+=1
        else:
            tate[h]=False
    start=0
    bed=[]
    for h in range(H-1):
        if tate[h]==True:
            goal=h+1
            part=[0]*(W+1)
            for i in range(start,goal):
                for j in range(1,W+1):
                    part[j]+=rui[i][j]
            bed.append(part)
            start=h+1
    goal=H
    part=[0]*(W+1)
    for i in range(start,goal):
        for j in range(1,W+1):
            part[j]+=rui[i][j]
    bed.append(part)
    ycut=0
    pos=True
    for j in range(1,W+1):
        for b in bed:
            if b[j]-b[j-1]>K:
                pos=False
                break
            elif b[j]-b[ycut]>K:
                ycut=j-1
                ncut+=1
        if pos==False:
            break
    if pos==False:
        continue
    ans=min(ans,ncut)    

                
print(ans)

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

S = [input() for _ in range(H)]

ans = 10**10
for i in range(2**(H-1)):   
    rel = [0 for h in range(H)]
    a,b = 0,0
    for h in range(H-1):
        if i>>h&1:
            b += 1
        rel[h+1] = b

    a += b

    cnt = [0 for j in range(b+1)]
    for w in range(W):
        for h in range(H):
            if S[h][w] == '1':
                cnt[rel[h]] += 1
        
        OK = True
        for j in range(b+1):
            if cnt[j] > K:
                OK = False
                break
        
        if OK:
            continue

        a += 1
        cnt = [0 for j in range(b+1)]
        for h in range(H):
            if S[h][w] == '1':
                cnt[rel[h]] += 1

        OK2 = True
        for j in range(b+1):
            if cnt[j] > K:
                OK2 = False
                break
        
        if OK2:
            continue
        a = 10**10
        break
    ans = min(ans,a)
print(ans)

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

S = [input() for _ in range(H)]

ans = 10**10
for i in range(2**(H-1)):   
    rel = [0 for h in range(H)]
    a,b = 0,0
    for h in range(H-1):
        if i>>h&1:
            b += 1
        rel[h+1] = b

    a += b

    cnt = [0 for j in range(b+1)]
    for w in range(W):
        for h in range(H):
            if S[h][w] == '1':
                cnt[rel[h]] += 1
        
        OK = True
        for j in range(b+1):
            if cnt[j] > K:
                OK = False
                break
        
        if OK:
            continue

        a += 1
        cnt = [0 for j in range(b+1)]
        for h in range(H):
            if S[h][w] == '1':
                cnt[rel[h]] += 1

        OK2 = True
        for j in range(b+1):
            if cnt[j] > K:
                OK2 = False
                break
        
        if OK2:
            continue
        a = 10**10
        break
    ans = min(ans,a)
print(ans)

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    H,W,K=map(int, input().split())
    oS=[list(map(int, list(input().rstrip()))) for _ in range(H)]

    ans=10**10
    for p in range(1<<(H-1)):
        S=[[oS[i][j] for j in range(W)] for i in range(H)]
        tmp=0
        flag=False
        for i in range(1,H):
            if p&1:
                for j in range(W):
                    S[i][j] += S[i-1][j]
                    if S[i][j]>K: flag=True
            else:
                tmp+=1
            p>>=1
        if flag: continue

        for j in range(W-1):
            for i in range(H):
                if S[i][j]+S[i][j+1]>K:
                    tmp+=1
                    break
            else:
                for i in range(H):
                    S[i][j+1] += S[i][j]

        ans = min(ans, tmp)

    print(ans)

if __name__ == '__main__':
    main()

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

S = [input() for _ in range(H)]

def calc(L):
    M = len(L)
    cnt = [0] * M
    ret = 0

    for w in range(W):
        for i, (t, b) in enumerate(zip(L, L[1:])):
            for j in range(t, b):
                if S[j][w] == '1':
                    cnt[i] += 1
        if max(cnt) > K:
            cnt = [0] * M
            ret += 1
            for i, (t, b) in enumerate(zip(L, L[1:])):
                for j in range(t, b):
                    if S[j][w] == '1':
                        cnt[i] += 1
        if max(cnt) > K:
            return 10**18

    return ret

ans = 10**18
for mask in range(1 << (H - 1)):
    L = [0] + [d + 1 for d in range(H - 1) if (mask & (1 << d)) > 0] + [H]
    ans = min(ans, len(L) - 2 + calc(L))
print(ans)

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

G = [list(input()) for _ in range(H)]

ans = H * W

def calc(lst):
    group = sum(lst) + 1
    tmp = [[0] * W for _ in range(group)] 
    k = 0
    for j in range(W):
        for i in range(H):
            if G[i][j] == '1':
                tmp[k][j] += 1
            if lst[i] == 1 or i == H - 1:
                k = (k + 1) % group
    
    cut = group - 1
    for j in range(W):
        flag = False
        for i in range(group):
            if tmp[i][j] > K:
                return 10 ** 9
            if j < W - 1:
                if tmp[i][j] + tmp[i][j + 1] > K: 
                    flag = True
        if flag:
            cut += 1
        else:
            for i in range(group):
                if j < W - 1:
                    tmp[i][j + 1] += tmp[i][j]
    return cut


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(ans, calc(lst))

print (ans)

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    S = [list(map(int, list(input().strip("\n")))) for _ in range(H)]
    sumS = [[0] * (W + 1) for _ in range(H + 1)]
    for h in range(H):
        for w in range(W):
            sumS[h+1][w+1] = sumS[h+1][w] + sumS[h][w+1] - sumS[h][w] + S[h][w]
    minK = 1000000000000
    for h in range(2 ** (H - 1)):
        count = 0
        border = [0]
        k = h
        for i in range(H-1):
            if k % 2 == 1: 
                border.append(i+1)
                count += 1
            k //= 2
        border.append(H)
        bN = len(border)
        left = 0
        ng = False
        for right in range(1, W + 1):
            for i in range(bN - 1):  
                if sumS[border[i+1]][right] - sumS[border[i+1]][left] - sumS[border[i]][right] + sumS[border[i]][left] > K:
                    if right - 1 == left: ng = True
                    else: 
                        count += 1
                        left = right - 1
                    break
            if ng: break 
        else: minK = min(minK, count)
    print(minK)
    return 0

if __name__ == "__main__":
    solve()

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

ans = H+W
for b in range(1<<(H-1)):
    gs = [[0]]
    for k in range(H-1):
        if b&(1<<k):
            gs.append([k+1])
        else:
            gs[-1].append(k+1)
    tmp = bin(b).count('1')
    ws = [0] * len(gs)
    for x in range(W):
        for i,g in enumerate(gs):
            for h in g:
                if S[h][x] == '1':
                    ws[i] += 1
        if any(w>K for w in ws):
            tmp += 1
            ws = [0] * len(gs)
            for i,g in enumerate(gs):
                for h in g:
                    if S[h][x] == '1':
                        ws[i] += 1
            if any(w>K for w in ws):
                tmp = H+W
                break
    ans = min(ans,tmp)
print(ans)

Solution (Python):
import math

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

if h == 1:
    print(math.ceil("1".count(s[0])/k))
    exit()

for i in range(2 ** (h-1)):
    ss = str(format(i,"b").zfill(h-1))
    cnt = 0
    zero = 0
    key = 1
    for j in range(len(ss)):
        if ss[j] == "0":
            zero += 1
    now = [0 for i in range(zero+1)]

    for j in range(w):
        next = []
        num = 0
        for n in range(h):
            if s[n][j] == "1":
                num += 1
            if num > k:
                key = 0
            if n < h-1 and ss[n] == "0":
                next.append(num)
                num = 0
        next.append(num)
        
        keykey = 1
        for n in range(zero+1):
            if keykey:
                if now[n] + next[n] > k:
                    now = next
                    cnt += 1
                    keykey = 0
                else:
                    now[n] += next[n]
                    
    if key:ans = min(ans,cnt+zero)
print(ans)

Solution (Python):
h,w,k = map (int,input().split())
s = [0] * h
aans =10000000
for i in range(h):
    s[i] = [int(i) for i in str(input())]
for i in range(2 ** (h - 1)):
    ans = 0

    kugiri = [0] * (h - 1)
    for j in range(h - 1):  
        if ((i >> j) & 1):  
            kugiri[j] = 1

    box = [0] * (sum(kugiri) + 1)
    ans += sum(kugiri)
    for j in range(w): 
        
        box[0] += s[0][j]
        num = 0
        for l in range(1,h): 
            num += kugiri[l-1]

            box[num] = s[l][j] + box[num]

        for l in range(len(box)):
            if box[l] > k and j != 0:
                box = [0 for _ in range(sum(kugiri) + 1)]
                num = 0
                box[0] += s[0][j]
                for m in range(1, h):
                    num += kugiri[m - 1]
                    box[num] = s[m][j] + box[num]
                ans += 1
                break
            elif box[l] > k and j == 0:
                ans += 10000000000

    aans =min(aans,ans)


print(aans)

Solution (Python):
'''

'''

INF = float('inf')

def main():
    H, W, K = map(int, input().split())
    S = [input() for _ in range(H)]
    S = [''.join(S[row][col] for row in range(H)) for col in range(W)]
    ans = INF
    for b in range(0, 2**H, 2):
        sections = [(0, H)]
        for shift in range(1, H):
            if (1<<shift) & b:
                sections.append((sections.pop()[0], shift))
                sections.append((shift, H))
        t_ans = len(sections) - 1
        count = {(l, r): 0 for l, r in sections}
        for col in range(W):
            if any(count[(l, r)] + S[col][l:r].count('1') > K for l, r in sections):
                for key in count.keys():
                    count[key] = 0
                t_ans += 1
            for l, r in sections:
                count[(l, r)] += S[col][l:r].count('1')
            if max(count.values()) > K:
                t_ans = INF
                break
        ans = min(ans, t_ans)
    print(ans)


main()

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

s=[input() for _ in range(h)]



count=10**9

for i in range(2**(h-1)):
    cnt=bin(i).count("1")

    
    y=[]
    for j in range(h-1):
        if (i>>j) &1:
            y.append(j)
    y.append(h-1)
    ruiseki=[0]*(cnt+1)
    
    test=0
    flag2=0
    for xx in range(w):
        yyy=0
        flag=0
        for index,yy in enumerate(y):
            while yyy<=yy:
                if s[yyy][xx]=="1":
                    ruiseki[index]+=1
                yyy+=1
        
        if max(ruiseki)>k:
            
            cnt+=1
            yyy=0
            ruiseki=[0]*(bin(i).count("1")+1)
            for index,yy in enumerate(y):
                while yyy<=yy:
                    if s[yyy][xx]=="1":
                        ruiseki[index]+=1
                    yyy+=1
            if max(ruiseki)>k:
                
                flag2=1
                break
        
        
    if flag2==0:
        count=min(count,cnt)
print(count)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

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

    ans = 10 ** 9
    for bit in range(1 << (H-1)):
        canSolve = True
        order = [0] * (H + 1)
        tmp_ans = 0
        for i in range(H):
            if bit & 1 << i:
                order[i+1] = order[i] + 1
                tmp_ans += 1
            else:
                order[i+1] = order[i]
        sum_block = [0] * (H + 1)
        for w in range(W):
            one_block = [0] * (H + 1)
            overK = False
            for h in range(H):
                h_index = order[h]
                one_block[h_index] += S[h][w]
                sum_block[h_index] += S[h][w]
                if one_block[h_index] > K:
                    canSolve = False
                if sum_block[h_index] > K:
                    overK = True
            if not canSolve:
                break
            if overK:
                tmp_ans += 1
                sum_block = one_block
            if tmp_ans >= ans:
                canSolve = False
                break
        if canSolve:
            ans = tmp_ans
    print(ans)

if __name__ == '__main__':
    main()

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

H,W,K = map(int,readline().split())
grid = [None] * (H+1)
grid[0] = [0] * (W+1)
for i in range(1,H+1):
  grid[i] = [0] + list(map(int,list(input())))
  





for i in range(len(grid)-1):
  for j in range(len(grid[i])):
    grid[i+1][j] = grid[i][j] + grid[i+1][j]

for i in range(len(grid)):
  for j in range(len(grid[i])-1):
    grid[i][j+1] = grid[i][j] + grid[i][j+1]
  
def get_choco_cnt(i,j,p,q):
  return grid[i][j] - grid[i][q] - grid[p][j] + grid[p][q]
  





def isOk(x,lastq,cond,K,H,W):
  
  lastp = 0 
  for j in range(H-1):
    if (cond >> j) & 1: 
      if get_choco_cnt(j+1,x,lastp,lastq) > K:
        return False
      lastp = j+1
  
  if get_choco_cnt(H,x,lastp,lastq) > K:
    return False
  return True
  
def decide_cut(cond,lastq,K,H,W):
  ok = lastq
  ng = W+1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if isOk(mid,lastq,cond,K,H,W):
      ok = mid
    else:
      ng = mid
  return ok

ans = 10000
for cond in range(2 ** (H-1)):
  cut_num = (bin(cond)[2:]).count("1") 
  lastq = 0 
  while lastq < W+1:
    new_lastq = decide_cut(cond,lastq,K,H,W)
    if new_lastq == W:
      break
    if new_lastq == lastq:
      cut_num = 10000
      break
    cut_num += 1
    lastq = new_lastq
  if ans > cut_num:
    ans = cut_num
print(ans)

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

H,W,K = map(int,readline().split())
grid = [None] * (H+1)
grid[0] = [0] * (W+1)
for i in range(1,H+1):
  grid[i] = [0] + list(map(int,list(input())))
  





for i in range(len(grid)-1):
  for j in range(len(grid[i])):
    grid[i+1][j] = grid[i][j] + grid[i+1][j]

for i in range(len(grid)):
  for j in range(len(grid[i])-1):
    grid[i][j+1] = grid[i][j] + grid[i][j+1]
  
def get_choco_cnt(i,j,p,q):
  return grid[i][j] - grid[i][q] - grid[p][j] + grid[p][q]
  





def isOk(x,lastq,cond,K,H,W):
  
  lastp = 0 
  for j in range(H-1):
    if (cond >> j) & 1: 
      if get_choco_cnt(j+1,x,lastp,lastq) > K:
        return False
      lastp = j+1
  
  if get_choco_cnt(H,x,lastp,lastq) > K:
    return False
  return True
  
def decide_cut(cond,lastq,K,H,W):
  ok = lastq
  ng = W+1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if isOk(mid,lastq,cond,K,H,W):
      ok = mid
    else:
      ng = mid
  return ok

ans = 10000
for cond in range(2 ** (H-1)):
  cut_num = (bin(cond)[2:]).count("1") 
  lastq = 0 
  while lastq < W+1:
    new_lastq = decide_cut(cond,lastq,K,H,W)
    if new_lastq == W:
      break
    if new_lastq == lastq:
      cut_num = 10000
      break
    cut_num += 1
    lastq = new_lastq
  if ans > cut_num:
    ans = cut_num
print(ans)

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

def vertical_line(h, w, k, s):
    ans = 0
    mark = [0 for _ in range(h)]
    for i in range(w):
        for j in range(h):
            mark[j] += s[j][i]
            if mark[j] > k:
                ans += 1
                mark = [s[l][i] for l in range(h)]
                break
    return ans

from copy import deepcopy
ans = []
for i in range(2 ** (h - 1)):
    s_copy = deepcopy(s)
    flag = False
    h_copy = h
    for j in range(h - 2, -1, -1):
        if i % 2 == 1:
            h_copy -= 1
            for l in range(w):
                s_copy[j][l] += s_copy[j+1][l]

                if s_copy[j][l] > k:
                    flag = True
                    break

            del s_copy[j+1]

        if flag:
            break

        i //= 2

    if flag:
        continue

    ans.append(h_copy - 1 + vertical_line(h_copy, w, k, s_copy))
print(min(ans))

Solution (Python):
import math

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

if h == 1:
    print(math.ceil("1".count(s[0])/k))
    exit()

for i in range(2 ** (h-1)):
    ss = str(format(i,"b").zfill(h-1))
    cnt = 0
    zerocnt = 0
    key = 1
    for j in range(len(ss)):
        if ss[j] == "0":
            zerocnt += 1
    now = [0 for i in range(zerocnt+1)]

    for j in range(w):
        next = []
        num = 0
        for n in range(h):
            if s[n][j] == "1":
                num += 1
            if num > k:
                key = 0
            if n < h-1 and ss[n] == "0":
                next.append(num)
                num = 0
        next.append(num)
  
        keykey = 1
        for n in range(zerocnt+1):
            if keykey:
                if now[n] + next[n] > k:
                    now = next
                    cnt += 1
                    keykey = 0
                else:
                    now[n] += next[n]
  
  
    if key:ans = min(ans,cnt+zerocnt)
print(ans)

Solution (Python):
h,w,k=map(int,input().split())
ans=10**18
s=[input() for _ in range(h)]
for i in range(2**(h-1)):
    div=[0]
    for j in range(h-1):
        if (i>>j)&1:
            div.append(j)
    div.append(h-1)
    n=len(div)
    divcnt=[0]*(n-1)
    j=-1
    prev=-1
    cnt=n-2
    ok=True
    while 1:
        l=1
        j+=1
        if j==w:
            break
        for m in range(h):
            if m<=div[l]:
                
                if divcnt[l-1]+int(s[m][j])>k:
                    j-=1
                    
                    if j==prev:
                        
                        ok=False
                    else:
                        prev=j
                        cnt+=1
                        
                        divcnt=[0]*(n-1)
                    break
                else:
                    divcnt[l-1]+=int(s[m][j])
                if m==div[l]:
                    if l<n-1:
                        l+=1
                    else:
                      break
        if not ok:
            break
    if ok:
        ans=min(cnt,ans)
print(ans)

Solution (Python):
h, w, k = map(int, input().split())
S = [[int(s) for s in list(input())] for i in range(h)]
ans = 10**4
for b in range(2**(h-1)):
    cnt = bin(b).count('1')
    B = format(b, 'b').zfill(h-1)+'1'
    T = [[0]*w for i in range(cnt+1)]
    for j in range(w):
        t, c = 0, 0
        for i in range(h):
            t += S[i][j]
            if B[i] == '1':
                T[c][j] += t
                t = 0
                c += 1
    if max([max(T[i]) for i in range(cnt+1)]) > k:
        continue
    A = [T[i][0] for i in range(cnt+1)]
    tmp = cnt
    for j in range(1, w):
        A = [A[i]+T[i][j] for i in range(cnt+1)]
        if any([a > k for a in A]):
            A = [T[i][j] for i in range(cnt+1)]
            tmp += 1
    ans = min(ans, tmp)
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    S = [list(input().strip()) for _ in range(H)]

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10

        for i in range(H):
            if n >> i & 1:
                tmp += 1

        for i in range(W):
            f = False
            ni = 0
            for j in range(H):
                if wn[ni] + int(S[j][i]) > K:
                    tmp += 1
                    f = True
                    break
                else:
                    wn[ni] += int(S[j][i])
                if n >> j & 1:
                    ni += 1
            ff = False
            if f:
                if i == 0:
                    tmp = float("inf")
                    break
                for j in range(H):
                    wn[j] = 0
                ni = 0
                for j in range(H):
                    wn[ni] += int(S[j][i])
                    if wn[ni] > K:
                        tmp = float("inf")
                        ff = True
                        break
                    if n >> j & 1:
                        ni += 1
            if ff:
                break

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()