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 sys


def input():
    return sys.stdin.readline().strip()


def get_sum(x1, x2, y1, y2):
    return acc[x2][y2] - acc[x1][y2] - acc[x2][y1] + acc[x1][y1]


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

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

ans = h + w

for h_div in range(1 << (h - 1)):
    h_ranges = []
    h_begin = 0
    for i in range(h - 1):
        if h_div >> i & 1:
            h_ranges.append([h_begin, i + 1])
            h_begin = i + 1
    h_ranges.append([h_begin, h])
    div_cnt = len(h_ranges) - 1

    def is_addable():
        for h_range in h_ranges:
            if get_sum(h_range[1], h_range[0], j + 1, w_begin) > k:
                return False
        return True

    w_begin = 0
    for j in range(w):
        if not is_addable():
            w_begin = j
            div_cnt += 1
            if not is_addable():
                div_cnt = h + w
                break
    ans = min(ans, div_cnt)

print(ans)

Solution (Python):
from operator import add
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines




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


ans = 10 ** 5
for h in range(2 ** (H - 1)):
    
    ok = False

    
    row = 1
    for i in range(H - 1):
        row += (h >> i) & 1

    num_cut = row - 1
    cnt = [0] * row

    

    
    for c in range(W):
        idx = 0
        tmp_cnt = [0] * row
        for r in range(H):

            if r != 0 and (h >> r - 1) & 1:
                idx += 1

            tmp_cnt[idx] += MEIJI[r][c]

        
        new_cnt = list(map(add, cnt, tmp_cnt))

        if any([K < x for x in new_cnt]):
            cnt = tmp_cnt
            num_cut += 1
        else:
            ok = True
            cnt = new_cnt

        

    if ok:
        ans = min(num_cut, ans)

print(ans)

Solution (Python):
def main():
    H, W, K = map(int, input().split())
    S = [list(map(int, list(input()))) for _ in range(H)]
    ans = float('inf')
    for i in range(2 ** (H - 1)):
        group = 0
        h_id = [0] * H
        for j in range(H):
            h_id[j] = group
            if i >> j & 1:
                group += 1
        
        group += 1
        c = [[0] * W for _ in range(group)]
        for h in range(H):
            for w in range(W):
                c[h_id[h]][w] += S[h][w]
        g_flag = True
        for g in range(group):
            for w in range(W):
                if c[g][w] > K:
                    g_flag = False

        if not g_flag:
            continue

        cnt = group - 1
        now = [0] * group
        flag = True
        for w in range(W):
            for g in range(group):
                now[g] += c[g][w]
                if now[g] > K:
                    flag = False
                    cnt += 1
                    break
            
            if not flag:
                for g in range(group):
                    now[g] = c[g][w]
                flag = True
        ans = min(ans, cnt)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

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

    
    ans = (H - 1) * (W - 1)

    
    for i in range(2 ** (H - 1)):
        snap = 0

        
        hori_grid = [grid[0]]
        for j in range(H - 1):
            if ((i >> j) & 1):
                hori_grid.append(grid[j+1])
                snap += 1
            else:
                hori_grid[-1] = [a + b for a,b in zip(hori_grid[-1], grid[j+1])]

        
        wc_count = [hori_grid[y][0] for y in range(snap + 1)]

        
        if max(wc_count) > K:
            continue

        
        for x in range(1, W):
            now_wc_count = [hori_grid[y][x] for y in range(len(wc_count))]
            next_wc_count = [a+b for a,b in zip(wc_count, now_wc_count)]

            if max(next_wc_count) > K:
                
                snap += 1
                wc_count = now_wc_count
            else:
                
                wc_count = next_wc_count

        ans = min(ans, snap)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

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

    
    ans = (H - 1) * (W - 1)

    
    for i in range(2 ** (H - 1)):
        snap = 0

        hori_grid = [grid[0]]
        for j in range(H - 1):
            if ((i >> j) & 1):
                hori_grid.append(grid[j+1])
                snap += 1
            else:
                hori_grid[-1] = [a + b for a,b in zip(hori_grid[-1], grid[j+1])]

        wc_count = [hori_grid[y][0] for y in range(snap + 1)]

        
        if max(wc_count) > K:
            continue

        for x in range(1, W):
            now_wc_count = [hori_grid[y][x] for y in range(len(wc_count))]
            next_wc_count = [a+b for a,b in zip(wc_count, now_wc_count)]

            if max(next_wc_count) > K:
                snap += 1
                wc_count = now_wc_count
            else:
                wc_count = next_wc_count

        ans = min(ans, snap)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

 
def main():
    H,W,K = map(int,input().split())
    a = S = [list(map(int, list(input()))) for _ in range(H)]
    
    ans = 10**6
    for i in range(1<<H-1):
        cut,count = [-1],0
        for j in range(H-1):
            if (i>>j)&1 != 0:
                count += 1
                cut.append(j)
        cut.append(H-1)
        l = len(cut)-1
        use = [[0 for _ in range(W)] for _ in range(l)]
        for x in range(l):
            up,down = cut[x],cut[x+1]
            for y in range(up+1,down+1):
                for z in range(W):
                    use[x][z] += a[y][z]

        bl,yorn = [0 for _ in range(l)],True
        for right in range(W):
            st = [0 for _ in range(l)]
            for x in range(l):
                st[x] += use[x][right]
            if max(st) > K:
                yorn = False
                break
            else:
                for x in range(l):
                    bl[x] += st[x]
                if max(bl) > K:
                    count += 1
                    bl = st
        if yorn:
            ans = min(ans,count)
    
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
from itertools import accumulate

readline = sys.stdin.readline
INF = 10 ** 9
h, w, k = map(int, readline().split())
s = [readline() for _ in range(h)]

ans = INF
for bit in range(2**h-1):
    cut = bin(bit).count('1')
    group = 0
    peace = [[0] * (bin(bit).count('1') + 1) for _ in range(w)]

    for i in range(w):
        group = 0
        for j in range(h):
            if s[j][i] == '1':
                peace[i][group] += 1
            if bit >> j & 1:
                group += 1

    if any(max(col) > k for col in peace):
        continue
    current = [0] * (bin(bit).count('1') + 1)
    for i in range(w):
        current = list(map(sum, zip(current, peace[i])))
        if max(current) > k:
            cut += 1
            current = peace[i]
    if ans > cut:
        ans = cut

print(ans)

Solution (Python):
import sys
from itertools import accumulate, combinations

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


H, W, K = MI()
S = [[int(x) for x in list(input())] for _ in range(H)]


def fn(bits):
    slice = 0
    n = bin(bits).count("1")
    block_cnts = [0] * n
    for j in range(W):
        sec = 0
        col_cnts = [0] * n
        for i in range(H):
            col_cnts[sec] += S[i][j]
            if col_cnts[sec] > K:
                return -1
            if (bits >> i) & 1:
                sec += 1
        if all(block_cnts[sec] + col_cnts[sec] <= K for sec in range(n)):
            for sec in range(n):
                block_cnts[sec] += col_cnts[sec]
        else:
            slice += 1
            block_cnts = col_cnts
    return slice


ans = INF
for bits in range(1 << (H - 1)):
    hslice = bin(bits).count("1")
    wslice = fn(bits + (1 << (H - 1)))
    if wslice > -1:
        ans = min(ans, hslice + wslice)
print(ans)

Solution (Python):
def getChoco(choco, w, t):
  for h in range(H):
    if S[h][w] == '1':
      choco[t[h]] += 1
  return choco

def solve(i):
  t = dict()
  t[0] = 0
  g = 0 
  for h in range(H-1):
    if (i>>h)%2 == 1: 
      g += 1 
      t[h+1] = g
    else:
      t[h+1] = g
  
  ret = g
  choco = [0 for _ in range(g+1)]
  
  for w in range(W):
    choco = getChoco(choco,w,t)
    if any(c>K for c in choco):
      
      choco = getChoco([0 for _ in range(g+1)],w,t)
      if any(c>K for c in choco): 
        return 10**9 
      else:
        ret += 1
  return ret

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

ans = H + W - 2
for i in range(2**(H - 1)):
    ans = min(ans, solve(i))
print(ans)

Solution (Python):
import sys, itertools
input = sys.stdin.readline
H, W, K = list(map(int, input().split()))

choco = []
for i in range(H):
  s = input().strip()
  a = list(map(int, list(s)))
  choco.append(a)

def min_split(h):
  sum_cnt = [0] * H
  num_split = 0
  for j in range(W):
    c = 0
    cnt = [0] * H
    flag = False
    for i in range(H):
      if choco[i][j] == 1:
        cnt[c] += 1
        if cnt[c] > K:
          return float('inf')
        if cnt[c] + sum_cnt[c] > K:
          flag = True
      if i < H-1 and h[i] == 1:
        c += 1
    if flag:
      num_split += 1
      sum_cnt = cnt
    else:
      for i in range(len(cnt)):
      	sum_cnt[i] += cnt[i]
  return num_split + sum(h)

min_m = float('inf')
for h in itertools.product([0,1], repeat=H-1):
  m = min_split(h)
  min_m = min(min_m, m)
print(min_m)

Solution (Python):
H, W, K = map(int,input().split())
S = [list(map(int,input())) for _ in range(H)]
ans = float("inf")
for i in range(1<<(H - 1)):
    data = [S[0][0:]]
    for j in range(H - 1):
        if (i >> j) & 1:
            data.append([0] * W)
        for k in range(W):
            data[-1][k] += S[j + 1][k]
    if any([any([x > K for x in y]) for y in data]):
        continue
    cnt = len(data) - 1
    judge = [0] * len(data)
    for j in range(W):
        if any([judge[x] + data[x][j] > K for x in range(len(data))]):
            judge = [0] * len(data)
            cnt += 1
        judge = [judge[x] + data[x][j] for x in range(len(data))]
    ans = min(ans, cnt)
print(ans)

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, W, K = iim()
    S = [input() for i in range(H)]
    C = "1"

    H1, W1 = H+1, W+1
    S1 = [[0] * (W1) for i in range(H1)]
    ans = 0

    for i in range(1, H1):
        for j in range(1, W1):
            S1[i][j] = S1[i-1][j] + S1[i][j-1] - S1[i-1][j-1] + (1 if S[i-1][j-1] == C else 0)

    
    if S1[-1][-1] < K:
        print(0)
        return

    inf = H+W
    ans = inf
    ii = [0] + [1<<i for i in range(H)]
    cnt = 0
    H2 = 1<<H
    for i in range(H2>>1, H2):
        i0 = j0 = 0
        jx = W
        cnt = bin(i).count("1") - 1
        ng = False
        while j0 < W:
            i0 = 0
            for i1 in range(1, H1):
                k = ii[i1]
                if i & k:
                    for j1 in range(j0+1, W1):
                        cx = S1[i1][j1] - S1[i1][j0] - S1[i0][j1] + S1[i0][j0]
                        if cx > K:
                            j1 -= 1
                            break
                    break

            if j1 == j0:
                ng = True
                break


            i0, jx = i1, j1
            for i1 in range(i1, H1):
                k = ii[i1]
                if i & k:
                    for j1 in range(jx, j0, -1):
                        cx = S1[i1][j1] - S1[i1][j0] - S1[i0][j1] + S1[i0][j0]
                        if cx <= K:
                            jx = j1
                            break
                    else:
                        ng = True
                        break
                    i0 = i1
            if ng:
                break
            j0 = jx
            cnt += 1

            if ans <= cnt:
                ng = True
                break

        if not ng:
            ans = cnt
    print(ans-1)


if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
h, w, k = map(int, sys.stdin.readline().split())
graph = [list(sys.stdin.readline().rstrip()) for _ in range(h)]
ans = 10**9+1

for div in range(2**(h-1)):
    
    id = [0] * h 
    group = 0 
    for j in range(h):
        id[j] = group
        if (div >> j) & 1:
            group += 1
    group += 1

    
    c = [[0] * w for _ in range(group)]
    for j in range(w):
        for i in range(h):
            if graph[i][j] == '1':
                c[id[i]][j] += 1

    temp = group-1 
    now = [0] * group 

    def add(now, j):
        
        for i in range(group):
            now[i] += c[i][j]

    def judge(now):
        
        for i in range(group):
            if now[i] > k: return False
        return True

    
    for j in range(w):
        add(now, j)
        if not judge(now):
            
            temp += 1
            now = [0] * group

            
            add(now, j)
            if not judge(now):
                temp = 10**9 + 1
                break

    ans = min(ans, temp)

print(ans)

Solution (Python):
import itertools

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

divide = list(itertools.product([0, 1], repeat=h-1))

MIN = 10**10
for d in divide:
    SUM = [0]*(sum(d)+1)
    ans = 0
    reset = False
    ok = True

    for i in range(w):
        
        now = 0
        for g in range(h-1):
            if d[g] == 0:
                if s[g][i] == '1':
                    SUM[now] += 1

            elif d[g] == 1:
                if s[g][i] == '1':
                    SUM[now] += 1
                now += 1
        if s[-1][i] == '1':
            SUM[-1] += 1
        

        for l in SUM:
            if l > k:
                reset = True
                break

        if reset:
            reset = False
            ans += 1
            SUM = [0]*(sum(d)+1)
            
            now = 0
            for g in range(h-1):
                if d[g] == 0:
                    if s[g][i] == '1':
                        SUM[now] += 1

                elif d[g] == 1:
                    if s[g][i] == '1':
                        SUM[now] += 1
                    now += 1
            if s[-1][i] == '1':
                SUM[-1] += 1
            
            for l in SUM:
                if l > k:
                    ok = False
                    break
        if ok is False:
            break
    if ok:
        MIN = min(MIN, ans+sum(d))

print(MIN)

Solution (Python):

"""
(ループで変数kを使いたい為、入力kはgとして受け取っているので注意)
process1:
まず、Hの制約が10以下であることから、どこで分割するかをbit全探索する。(最大2**9回)
次にresを空のリストで用意し、分割数だけ累積和で圧縮した横方向のチョコレートを入れる。
分割されたそれぞれのチョコレートについて、累積和をとったので、例えば
1101
0101　のように分割されたチョコレートは、
↓
1202　というように1行に圧縮して表される。

process2-
次に、それぞれの部分チョコレートについて、それぞれの一列が条件を満たしているかどうかを調べる
必要があるが、これは後回しにする。

process3:
実際に縦方向に最低何分割する必要があるかをサーチする。この時、各部分チョコレートについて
回してしまうと、最適な分割数を求めることができない。
横方向にループを回して、すべての部分チョコレートについて並行にサーチし、初めてg > count
(countは1の数)となってしまった列で分割数を+1し、縦方向の分割数(これはblstの各要素の1の数
から求める。)との合計をとってansを更新する。

process2-
さてここで、process3の分割の条件は"各部分チョコレートについて、初めて条件を満たさなくなった時
に分割を増やす"であったが、既に1列がg >= countを満たさない場合、どのように縦方向で分割しても
条件を満たさないので、これは横方向の分割の時点で弾かなければならない。
例；
3 4 1
1101
0001
0001
横方向に必ず3分割しないと条件を満たさないので、他のものを弾く。
"""
import sys
readline = sys.stdin.buffer.readline

h,w,g = map(int,readline().split())

maze = []
for i in range(h):
    s = readline().rstrip().decode('utf-8')
    maze.append(s)


def bit_list(dig): 
    lst = []
    for i in range(2**dig):
        lst.append(list(format(i,"b").zfill(dig)))
    return lst


blst = bit_list(h-1) 
ans = 10**9

for i in range(len(blst)):
    res = []
    lst1 = [0]*w
    
    for k in range(w): 
                lst1[k] += 1 if maze[0][k] == "1" else 0
    
    for index,j in enumerate(blst[i],1):
        if j== "0": 
            for k in range(w):
                lst1[k] += 1 if maze[index][k] == "1" else 0
        else:
            res.append(lst1)
            lst1 = [0]*w
            for k in range(w):
                lst1[k] += 1 if maze[index][k] == "1" else 0
    
    res.append(lst1)

    
    
    flag = 0
    for j in res:
        if any(k > g for k in j):
            flag = 1
            break
    if flag:
        continue

    
    w_cut = 0
    count = [0]*len(res)
    for j in range(w):
        now_count = [0]*len(res)
        for index,k in enumerate(res):
            count[index] += k[j]
            now_count[index] += k[j]
        if any(l > g for l in count):
            count = now_count
            w_cut += 1


    ans = min(ans,blst[i].count("1")+w_cut)

print(ans)

Solution (Python):
import itertools

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

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

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

h,w,g = map(int,readline().split())

maze = []
for i in range(h):
    s = readline().rstrip().decode('utf-8')
    maze.append(s)


def bit_list(dig): 
    lst = []
    for i in range(2**dig):
        lst.append(list(format(i,"b").zfill(dig)))
    return lst


blst = bit_list(h-1)
ans = 10**9
for i in range(len(blst)):
    res = []
    lst1 = [0]*w

    for k in range(w): 
                lst1[k] += 1 if maze[0][k] == "1" else 0
    
    for index,j in enumerate(blst[i],1):
        if j== "0": 
            for k in range(w):
                lst1[k] += 1 if maze[index][k] == "1" else 0
        else:
            res.append(lst1)
            lst1 = [0]*w
            for k in range(w):
                lst1[k] += 1 if maze[index][k] == "1" else 0
    
    res.append(lst1)
    flag = 0
    
    for j in res:
        if any(k > g for k in j):
            flag = 1
            break
    if flag:
        continue

    w_cut = 0
    count = [0]*len(res)
    for j in range(w):
        now_count = [0]*len(res)
        for index,k in enumerate(res):
            count[index] += k[j]
            now_count[index] += k[j]
        if any(l > g for l in count):
            count = now_count
            w_cut += 1


    ans = min(ans,blst[i].count("1")+w_cut)

print(ans)

Solution (Python):
H,W,K = map(int, input().split())
S = []
ans = 10**9
for i in range(H):
  S.append(input())
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
  g += 1
  c = [[0]*W for i in range(g)]
  for i in range(H):
    for j in range(W):
      if S[i][j]=='1':
        c[ID[i]][j] += 1
  num = g-1
  now = [0]*g
  def add(j):
    for i in range(g):
      now[i] += c[i][j]
    for i in range(g):
      if now[i]>K:
        return False
    return True
  for j in range(W):
    if not add(j):
      num += 1
      now = [0]*g
      if not add(j):
        num = 10**9
        break
  ans = min(ans,num)
print(ans)

Solution (Python):
def main():
    h, w, k = map(int, input().split())
    s = [[int(i) for i in list(input())] for _ in range(h)]
    cnt = [bin(i).count("1") for i in range(2**(h - 1))]
    c = 0
    for ci in [sum(i) for i in zip(*s)]:
        if ci > k:
            cnt[0] = 100000
            break
        c += ci
        if c > k:
            cnt[0] += 1
            c = ci
    minc = cnt[0]
    for i in range(1, 2**(h - 1)):
        div = [j + 1 for j in range(h) if i & 2**j]
        ss = []
        l = 0
        for d in div:
            ss.append(s[l:d])
            l = d
        ss.append(s[l:])
        c = [0] * len(ss)
        t = [[sum(i) for i in zip(*si)] for si in ss]
        for j in range(w):
            if cnt[i] >= minc:
                break
            if max(ti[j] for ti in t) > k:
                cnt[i] = 100000
                break
            for tt, ti in enumerate(t):
                c[tt] += ti[j]
            if max(c) > k:
                cnt[i] += 1
                c = [ti[j] for ti in t]
    print(min(cnt))

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    h, w, k = map(int, input().split())
    s = [[int(i) for i in list(input())] for _ in range(h)]
    cnt = [bin(i).count("1") for i in range(2**(h - 1))]
    c = 0
    for ci in [sum(i) for i in zip(*s)]:
        if ci > k:
            cnt[0] = 100000
            break
        c += ci
        if c > k:
            cnt[0] += 1
            c = ci
    for i in range(1, 2**(h - 1)):
        div = [j + 1 for j in range(h) if i & 2**j]
        ss = []
        l = 0
        for d in div:
            ss.append(s[l:d])
            l = d
        ss.append(s[l:])
        c = [0] * len(ss)
        t = [[sum(i) for i in zip(*si)] for si in ss]
        for j in range(w):
            if max(ti[j] for ti in t) > k:
                cnt[i] = 100000
                break
            for tt, ti in enumerate(t):
                c[tt] += ti[j]
            if max(c) > k:
                cnt[i] += 1
                c = [ti[j] for ti in t]
    print(min(cnt))

if __name__ == '__main__':
    main()

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

ans = 10**9+7

for i in range(1<<(h-1)):
    group = [[0]*w]
    g_id = 0
    group[g_id] = [s+b for s, b in zip(S[0], group[0])]

    for j in range(1,h):
        if (i>>(j-1))&1:
            group.append([0]*w)
            g_id += 1
        group[g_id] = [s+b for s, b in zip(S[j], group[g_id])]
    
    if not all([all([i <= k for i in b]) for b in group]):
        continue
    
    cnt = len(group) - 1
    g_cnt = [0] * len(group)

    for jj in range(w):
        for g_id in range(len(group)):
            g_cnt[g_id] += group[g_id][jj]
        
        if any([c > k for c in g_cnt]):
            cnt += 1
            for g_id in range(len(group)):
                
                g_cnt[g_id] = group[g_id][jj]
    ans = min(ans, cnt)
print(ans)

Solution (Python):
r=range
h,*s=open(0)
h,w,k=map(int,h.split())
m=9e9
for i in r(1<<h-1):
  t,v,l=[],-1,1
  for j in r(h):
    if i>>j&1:
      t+=j+1,
      l+=1
  t+=h,
  c=[0]*l
  for i in r(w):
    b=f=g=0
    u=[]
    for j in r(l):
      d,b=sum(s[j][i]>'0'for j in r(b,t[j])),t[j]
      u+=d,
      g|=d>k
      c[j]+=d
      f|=c[j]>k
    v+=f
    if f:c=u
  if not g:m=min(m,v+l)
print(m)

Solution (Python):
r=range
h,*s=open(0)
h,w,k=map(int,h.split())
m=9e9
for i in r(1<<h-1):
  t,v,l=[],-1,1
  for j in r(h):
    if i>>j&1:
      t+=j+1,
      l+=1
  t+=h,
  c=[0]*l
  for i in r(w):
    b=f=g=0
    u=[]
    for j in r(l):
      d,b=sum(s[j][i]=='1'for j in r(b,t[j])),t[j]
      u+=d,
      if d>k:
        g=1
        break
      c[j]+=d
      f|=c[j]>k
    else:
      v+=f
      if f:c=u
    if g:break
  else:m=min(m,v+l)
print(m)

Solution (Python):
h, w, k = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(h)]
ans = 10**9+7

for i in range(1<<(h-1)):
    group  = [[0] * w]
    g_id = 0
    group[g_id] = [s + b for s, b in zip(S[0], group[0])]

    for j in range(1, h):
        if (i >> (j-1)) & 1:
            g_id += 1
            group.append([0]*w)
        group[g_id] = [s + b for s, b in zip(S[j], group[g_id])]


    
    if not all([all([i<=k for i in b]) for b in group]):
        continue
    
    cnt = len(group) - 1
    g_cnts = [0] * len(group)

    for jj in range(w):
        for g_id in range(len(group)):
            g_cnts[g_id] += group[g_id][jj]
        if any([c > k for c in g_cnts]):
            cnt += 1
            for g_id in range(len(group)):
                g_cnts[g_id] = group[g_id][jj]
    ans = min(ans, cnt)
print(ans)

Solution (Python):
def main():
  h,*s=open(0)
  h,w,k=map(int,h.split())
  s=[list(map(int,t[:w]))for t in s]
  m=9e9
  for i in range(1<<h-1):
    t=[]
    b=v=l=0
    for j in range(h):
      if i>>j&1:
        t+=map(sum,zip(*s[b:j+1])),
        b=j+1
        l+=1
    t+=map(sum,zip(*s[b:])),
    l+=1
    c=[0]*l
    for i in range(w):
      f=g=0
      u=[]
      for j,d in enumerate(t):
        d=d.__next__()
        u+=d,
        if d>k:
          g=1
          break
        c[j]+=d
        f|=c[j]>k
      else:
        if f:
          c=u
          v+=1
      if g:break
    else:
      if v+l-1<m:m=v+l-1
  print(m)
main()

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

def divide(pattern):
    lenP = len(pattern)
    divided = [0]*lenP
    count = lenP - 1
    for i in range(lenP):
        if K < pattern[i][0]:
            return H+W
    for i in range(1,W):
        for j in range(lenP):
            if K < pattern[j][i] - divided[j]:
                for l in range(lenP):
                    divided[l] = pattern[l][i-1]
                count += 1
                break
    return count

ans = H+W
for i in range(2**H):
    pattern = []
    line = [0] * W
    for j in range(H):
        for k in range(W):
            line[k] += S[j][k]
        if 2**j & i:
            pattern.append(line)
            line = [0] * W
    pattern.append(line)
    ans = min(divide(pattern),ans)
print(ans)

Solution (Python):

import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    H,W,K = LMIIS()
    from itertools import accumulate
    S = [list(accumulate(map(int,input()))) for _ in range(H)]
    


    def divide(pattern):
        lenP = len(pattern)
        divided = [0]*lenP
        count = lenP - 1
        for i in range(lenP):
            if K < pattern[i][0]:
                return H+W
        for i in range(1,W):
            
            for j in range(lenP):
                if K < pattern[j][i] - divided[j]:
                    for l in range(lenP):
                        divided[l] = pattern[l][i-1]
                    count += 1
                    break
        
        return count
                    

            
        



    ans = H+W

    for i in range(2**H):
        pattern = []
        line = [0] * W
        for j in range(H):
            for k in range(W):
                line[k] += S[j][k]
            if 2**j & i:
                pattern.append(line)
                line = [0] * W
        pattern.append(line)
        
        ans = min(divide(pattern),ans)
    print(ans)
    return
        
    

                

                
                

    

    

if __name__ == '__main__':
    main()

Solution (Python):
h,*s=open(0)
h,w,k=map(int,h.split())
s=[list(map(int,t[:w]))for t in s]
m=9e9
for i in range(1<<h-1):
  t=[]
  b=v=l=0
  for j in range(h):
    if i>>j&1:
      t+=s[b:j+1],
      b=j+1
      l+=1
  t+=s[b:],
  l+=1
  c=[0]*l
  for i in range(w):
    f=g=0
    u=[]
    for j in range(l):
      d=sum(t[i]for t in t[j])
      u+=d,
      if d>k:
        g=1
        break
      c[j]+=d
      f|=c[j]>k
    else:
      v+=f
      if f:c=u
    if g:break
  else:m=min(m,v+l-1)
print(m)

Solution (Python):
def main():
    H,W,K = map(int,input().split())
    S = [input()for _ in range(H)]
    ans = 10**9
    for i in range(2**(H-1)):
        aa = 0
        for j in range(H-1):
            if (i>>j)&1 == 1:
                aa+=1
        c = aa
        b = [0]*(c+1)
        OK = True
        for j in range(W):
            k = 0
            for h in range(H):
                if S[h][j] == "1":b[k] += 1
                if (i>>h)&1==1:k+=1
            
            ok = True
            for p in b:
                if p > K:ok = False
            if not ok:
                aa += 1
                b = [0]*(c+1)
                
                k = 0
                for h in range(H):
                    if S[h][j]=="1":b[k] += 1
                    if (i>>h)&1==1:k+=1
                ok = True
                for p in b:
                    if p > K:ok = False
                if not ok:OK = False;break                
        if OK:ans = min(ans,aa)
    print(ans)

if __name__ == "__main__":
    main()