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 __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    h, w, k = [int(s) for s in input().strip().split()]
    grid = [input().strip() for _ in range(h)]

    result = float("inf")
    for hcut in range(1 << (h - 1)):
        vcut = 0
        cnt = [0] * h
        for j in range(w):
            delta = [0] * h
            for i in range(h):
                delta[i] += grid[i][j] == "1"
                if i > 0 and not (hcut >> (i - 1)) & 1:
                    delta[i] += delta[i - 1]
            if any(x > k for x in delta):
                vcut = float("inf")
                break
            if any(a + b > k for a, b in zip(cnt, delta)):
                cnt = delta
                vcut += 1
            else:
                for idx, x in enumerate(delta):
                    cnt[idx] += x
            
        result = min(result, vcut + bin(hcut).count("1"))
        
    print(result)




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

Solution (Python):
h,w,kk=map(int,input().split())
G=[[0]*w for i in range(h)]
for i in range(h):
  G[i]=list(input())
for i in range(h):
  for j in range(w):
    G[i][j]=int(G[i][j])
ans=10**5
for i in range(2**(h-1)):
  s=format(i,'12b')
  A=[-1]
  for j in range(h-1):
    if s[-1-j]=="1":
      A.append(j)
  A.append(h-1)
  ans1=len(A)-2
  B=[0]*(len(A)-1)
  c=0
  i=0
  while i<w:
    j=0
    while j<len(A)-1:
      for k in range(A[j]+1,A[j+1]+1):
        B[j]+=G[k][i]
      if B[j]>kk:
        c=c+1
        B=[0]*(len(A)-1)
        j=0
        if c>1010:
          j=100
          i=10000
      else:
        j=j+1
    i=i+1
  if ans1+c<ans:
    ans=ans1+c
print(ans)

Solution (Python):
h,w,k=map(int,input().split())
l=[[0 for i in range(w+1)]]+[[0]+[int(j) for j in input()] for i in range(h)]
a=[[0 for i in range(w+1)] for i in range(h+1)]
for i in range(1,h+1):
    for j in range(1,w+1):
        a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+l[i][j]
ans=h*w
def ink(h2,h1,w2,w1):
    return a[h2][w2]-a[h1][w2]-(a[h2][w1]-a[h1][w1])
for i in range(2**(h-1)):
    tl=[0]
    for j in range(h-1):
        if i>>j&1:
            tl.append(j+1)
    tl.append(h)
    t=len(tl)-2
    w1=0
    for w2 in range(1,w+1):
        for h1,h2 in zip(tl,tl[1:]):
            if ink(h2,h1,w2,w1)>k:
                if w2-1==w1:
                    t=h*w
                    break
                w1=w2-1
                t+=1
                break
    ans=min(ans,t)
print(ans)

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

Acum = [[0] * (W+1) for i in range(H+1)]
for i in range(H):
    for j in range(W):
        Acum[i+1][j+1] = Acum[i][j+1] + Acum[i+1][j] - Acum[i][j] + fields[i][j]
"""

h1,h2,w1,w2 = 1,3,1,5 
ans = Acum[h2][w2] - Acum[h1][w2] - Acum[h2][w1] + Acum[h1][w1]
print("aaa",ans)
for i in range(H+1):
    print(Acum[i])
"""


ans = 10**10
for i in range(2**(H-1)):
    
    s = bin(i)[2:]
    s_zero = s.zfill(H-1)
    
    
    a = [0]+[i+1 for i,s in enumerate(s_zero) if int(s) == 1]
    a += [H]
    
    w_cnt = 0
    w1 = 0
    w = 1
    m = 0
    while w <= W:
        m = 0
        for j in range(1,len(a)):
            h1 = a[j-1]
            h2 = a[j]
            cnt = Acum[h2][w] - Acum[h1][w] - Acum[h2][w1] + Acum[h1][w1]
            
            m = max(m,cnt)
        if m > K:
            if w - 1 == w１:
                w_cnt = 10**10
                break
            w_cnt += 1
            w1 = w -1         
        w += 1
    
    ans = min(ans,sum(map(int,list(s)))+w_cnt)
print(ans)

Solution (Python):

def create_groups(H):
    F = "{:0" + str(H) + "b}"
    ret = set()
    for n in range(2 ** H):
        g = create_group(F.format(n))
        ret.add(tuple(g))
    return list(sorted(ret))


def create_group(s):
    ret = []
    n = 0
    for i in range(len(s)):
        if i == 0:
            ret.append(0)
        else:
            if s[i-1] == s[i]:
                ret.append(n)
            else:
                n += 1
                ret.append(n)
    return ret







def solve(H, W, K, fields):
    ans = H * W + 1
    for g in create_groups(H):
        M = len(set(g))
        s = [0 for _ in range(M)]
        tans = M - 1
        for w in range(W):
            for h in range(H):
                if fields[h][w] == "1":
                    s[g[h]] += 1
            if any([a > K for a in s]):
                s = [0 for _ in range(M)]
                tans += 1
                for h in range(H):
                    if fields[h][w] == "1":
                        s[g[h]] += 1
            if any([a > K for a in s]):
                tans = H * W + 1
                break
        ans = min(ans, tans)
    return ans













if __name__ == "__main__":
    H, W, K = tuple(map(int, input().split(" ")))
    fields = []
    for _ in range(H):
        fields.append(input())
    print(solve(H, W, K, fields))

Solution (Python):
def main():

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

    div = [[]]
    for i in range(1, H+1):
        temp = []
        for lv in div:
            temp.append(lv + [i])
            if i < H:
                temp.append(lv)
        div = temp

    ans = float('inf')
    for lv in div:
        accum = [0 for _ in range(len(lv))]
        count = 0
        chk = []
        is_invalid = False
        for j in range(W):
            k = 0
            to_add = []
            v = 0
            for i in range(H):
                if i == lv[k]:
                    k += 1
                    to_add.append(v)
                    v = 0
                if S[i][j] == '1':
                    v += 1
            to_add.append(v)
            if any(to_add[i] > K for i in range(len(lv))):
                is_invalid = True
                break
            elif any((accum[i] + to_add[i]) > K for i in range(len(lv))):
                count += 1
                accum = to_add
                chk.append(j)
            else:
                for i in range(len(lv)):
                    accum[i] += to_add[i]
        if not is_invalid:
            ans = min(ans, count + len(lv)-1)
    return ans


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

Solution (Python):
class CumulativeSum2D:
  def __init__(self,a):
    self.h=len(a)
    self.w=len(a[0])
    self.s=[(self.w+1)*[0]for _ in range(self.h+1)]
    for i in range(self.h):
      for j in range(self.w):
        self.s[i+1][j+1]=self.s[i+1][j]+self.s[i][j+1]-self.s[i][j]+a[i][j]
  def su(self,i1,j1,i2,j2):
    return self.s[i2+1][j2+1]-self.s[i1][j2+1]-self.s[i2+1][j1]+self.s[i1][j1]
  def prin(self):
    for i in self.s:print(i)
h,w,kk=map(int,input().split())
b=[list(map(int,list(input())))for _ in range(h)]
h-=1
bs=CumulativeSum2D(b)
ans=h+w-1
for i in range(2**h):
  bi=[-1]+[j for j in range(h)if(1<<j)&i]+[h]
  anss=len(bi)-2
  flag=False
  cut=[0]
  for k in range(w):
    for j in range(len(bi)-1):
      up=bi[j]+1
      down=bi[j+1]
      s=bs.su(up,cut[-1],down,k)
      if s>kk:
        if k==cut[-1]:flag=True
        else:cut.append(k);anss+=1
        break
    if flag:break
  if flag:continue
  ans=min(ans,anss)
print(ans)

Solution (Python):
h,w,K=map(int,input().split())
data=[[0 for i in range(w+1)]]
for i in range(h):
    x=list(input())
    x.insert(0,0)
    for j in range(w+1):
        x[j]=int(x[j])
    data.append(x)
    
for i in range(h+1):
    for j in range(1,w+1):
        data[i][j]+=data[i][j-1]
        
for i in range(w+1):
    for j in range(1,h+1):
        data[j][i]+=data[j-1][i]
        


ans=10**10
for _ in range(2**(h-1)):
    st=choice=format(_,"0%ib"%(h-1))
    div=[0]
    sub=0
    for j in range(h-1):
        if st[j]=="1":
            div.append(j+1)
            sub+=1
    div.append(h)
    cnt=0
    nowindex=0
    for j in range(1,w+1):
        flag=True
        if nowindex==0:
            for k in range(1,len(div)):
                if data[div[k]][j]-data[div[k-1]][j]>K:
                    flag=False
                    break
            if flag is False:
                nowindex=j-1
                cnt+=1
                 
        else:
            for k in range(1,len(div)):
                if (data[div[k]][j]-data[div[k]][nowindex])-(data[div[k-1]][j]-data[div[k-1]][nowindex])>K:
                    flag=False
                    break
            if flag is False:
                nowindex=j-1
                cnt+=1
    subflag=True
    for k in range(1,len(div)):
        if (data[div[k]][w]-data[div[k]][nowindex])-(data[div[k-1]][w]-data[div[k-1]][nowindex])>K:
            subflag=False
    if subflag is True:
        ans=min(ans,sub+cnt)
print(ans)

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


ans = float('inf')
for i in range(2**(H-1)):
    _ans = bin(i).count('1')
    chocos = [list(map(int, S[0]))]
    for j in range(H-1):
        if i >> j & 1:
            chocos.append(list(map(int, S[j+1])))
        else:
            for w in range(W):
                chocos[-1][w] += int(S[j+1][w])
    
    ns = len(chocos)
    nums = [0] * ns
    is_next = False
    for w in range(W):
        for j in range(ns):
            nums[j] += chocos[j][w]
            if chocos[j][w] > K:
                _ans = float('inf')
            if nums[j] > K:
                _ans += 1
                is_next = True
                break
        
        if is_next:
            for j in range(ns):
                nums[j] = chocos[j][w]
            is_next = False
    
    ans = min(ans, _ans)

print(ans)

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

def main():
    h,w,k=map(int,input().split())
    S=[]
    for _ in range(h):
        S.append(list(int(x) for x in list(input().strip())))
    
    ans=float('inf')
    for bit in range(1<<(h-1)):
        cut=0
        tmp=bit
        while tmp:
            cut+=tmp&1
            tmp>>=1
        C=[]
        Tmp=S[0][:]
        for i in range(h-1):
            if (bit>>i)&1==1:
                C.append(Tmp)
                Tmp=S[i+1][:]
            else:
                for j in range(w):
                    Tmp[j]+=S[i+1][j]
        C.append(Tmp)
        
        m=0
        for c in C:
            m=max(m,max(c))
        if m>k:
            continue
        W=[0]*(cut+1)
        l=len(W)
        for i in range(l):
            W[i]+=C[i][0]
        for i in range(w-1):
            for j in range(l):
                W[j]+=C[j][i+1]
            
            if max(W)>k:
                cut+=1
                for j in range(l):
                    W[j]=C[j][i+1]
        
        ans=min(ans,cut)
    print(ans)
    
if __name__=='__main__':
    main()

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

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

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

def count(x1,y1,x2,y2):
    res = c[x2][y2]
    res -= c[x2][y1-1]
    res -= c[x1-1][y2]
    res += c[x1-1][y1-1]
    return res

ans = 10**9
for n in range(2**(H-1)):
    h = [0]
    cuts = 0
    for k in range(H-1):
        if 2**k&n:
            h.append(k+1)
            cuts += 1
    h.append(H)
    w1 = 0
    for w2 in range(W):
        ok = True
        for i in range(len(h)-1):
            h1 = h[i]
            h2 = h[i+1]-1
            if count(h1,w1,h2,w2)>K:
                ok = False
                break
        if not ok:
            cuts += 1
            if w1==w2:
                cuts = 10**9
            w1 = w2
    
    ans = min(ans,cuts)

print(ans)

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)):
    tmp = bin(b).count('1')
    ks = [0]*H
    valid = True
    for col in zip(*S):
        j = 0
        for i,c in enumerate(col):
            if c=='1':
                ks[j] += 1
            if b&(1<<i):
                j = i+1
        if any(k > K for k in ks):
            tmp += 1
            ks = [0]*H
            j = 0
            for i,c in enumerate(col):
                if c=='1':
                    ks[j] += 1
                if b&(1<<i):
                    j = i+1
            if any(k > K for k in ks):
                valid = False
                break
    if valid:
        ans = min(ans,tmp)
print(ans)

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

res = 10**9

for i in range(2**(H-1)):
    yoko = []
    for j in range(H-1):
        if (i>>j) & 1:
            yoko.append(j+1)
    yoko.append(H)
    
    sen = len(yoko)-1

    rS = [[0]*W for _ in range(sen+1)]

    flag = False

    for w in range(W):
        b = 0
        for j in range(sen+1):
            t = b
            b = yoko[j]
            for h in range(t, b):
                if S[h][w] == "1":
                    rS[j][w] += 1
            if rS[j][w] > K:
                flag = True
                break
        if flag:
            break
    
    if flag:
        continue
    
    x = [r[0] for r in rS]
    for w in range(1, W):
        for h in range(len(yoko)):
            x[h] += rS[h][w]
            if x[h] > K:
                x = [r[w] for r in rS]
                sen += 1
                break
    
    res = min(sen, res)
    if res == 0:
        break

print(res)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w,K = LI()
s = [input() for _ in range(h)]

ans = inf
for i in range(2**(h-1)):
    bit = [0]*(h-1)
    cnt = 0
    for j in range(h-1):
        if (i >> j) & 1:
            bit[j] = 1
            cnt += 1
    lst = [[0]*w for _ in range(cnt+1)]
    preans = cnt
    C = cnt
    tmp = 0
    cnt = 0
    for j in range(h-1):
        if bit[j]:
            for l in range(w):
                for k in range(tmp, j+1):
                    if s[k][l] == '1':
                        lst[cnt][l] += 1
            tmp = j+1
            cnt += 1

    for j in range(w):
        for k in range(tmp,h):
            if s[k][j] == '1':
                lst[-1][j] += 1
    T = [0]*(C+1)
    flg = True
    for k in range(w-1):
        for j in range(C+1):
            T[j] += lst[j][k]
            if lst[j][k] > K:
                flg = False
            if T[j] + lst[j][k+1] > K:
                preans += 1
                T = [0]*(C+1)
                break
    for j in range(C+1):
        if lst[j][-1] > K:
            flg = False
    if flg:
        ans = min(ans, preans)
print(ans)

Solution (Python):
H,W,K = map(int,input().split())
S = []
for i in range(H):
	s = list(map(int, list(input())))
	S.append(s)
A = [[0 for i in range(W+1)] for j in range(H+1)]
for i in range(H):
	for j in range(W):
		A[i+1][j+1] = A[i+1][j] + A[i][j+1] - A[i][j] + S[i][j]

def f(x1,y1,x2,y2):
	return A[x2][y2] - A[x1-1][y2] - A[x2][y1-1] + A[x1-1][y1-1]

if f(1,1,H,W) <= K:
	print(0)
	exit()

m = 100000

def int2bit(n):
	ret = [0 for i in range(H-1)]
	c = 0
	while n > 0:
		ret[c] = n % 2
		n = n // 2
		c += 1
	return ret

def getx1x2(b):
	ret = []
	x1 = 1
	for i in range(H-1):
		if b[i] == 1:
			ret.append((x1, i+1))
			x1 = i+2
	ret.append((x1, H))
	return ret

def check(x1x2):
	for y in range(1, W+1):
		for x1, x2 in x1x2:
			if(f(x1,y,x2,y) > K):
				return False
	return True

for i in range(2**(H-1)):
	x1x2 = getx1x2(int2bit(i))
	if not check(x1x2):
		continue
	cnt = len(x1x2) - 1
	y1 = 1
	for y2 in range(2, W+1):
		flag = False
		for x1, x2 in x1x2:
			if f(x1,y1,x2,y2) > K:
				flag = True
				break
		if flag:
			y1 = y2
			cnt += 1
	m = min(m, cnt)
print(m)

Solution (Python):
import copy

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

s1 = [[0]*(w+1) for _ in range(h)]
s12 = [[0]*(w+1) for _ in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == '1':
            s1[i][j+1] = s1[i][j] + 1
        else:
            s1[i][j+1] = s1[i][j]

for i in range(h):
    for j in range(w+1):
        if i == 0:
            s12[i][j] = s1[i][j]
        else:
            s12[i][j] = s12[i-1][j] + s1[i][j]

li = []
ans = 10**10

def make_list():
    global li, h
    if len(li) != h - 1:
        li.append(0)
        make_list()
        li.pop(-1)
        li.append(1)
        make_list()
        li.pop(-1)
    else:
        hantei()

def hantei():
    global li, ans
    tmp = li.count(1)
    tmp_1 = -1
    s2 = []
    s3 = []
    for i in range(h-1):
        if li[i] == 1:
            if tmp_1 == -1:
                s2.append(s12[i])
                tmp_1 = i
            else:
                for j in range(w+1):
                    s3.append(s12[i][j] - s12[tmp_1][j])
                s2.append(s3)
                tmp_1 = i
                s3 = []
    if tmp_1 == -1:
        s2.append(s12[-1])
    else:
        for j in range(w+1):
            s3.append(s12[-1][j] - s12[tmp_1][j])
        s2.append(s3)

    tmp_2 = 0
    for i in range(w+1):
        for j in range(len(s2)):
            if s2[j][i] - s2[j][tmp_2] > k:
                tmp += 1
                tmp_2 = i - 1
                if s2[j][i] - s2[j][tmp_2] > k:
                    tmp += 10**5
                break

    ans = min(ans, tmp)

make_list()

print(ans)

Solution (Python):
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class v:
    def __init__(self, f):
        self.f = f
        self.v = None
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n) 

def f(i, H):
    B = format(i, "0" + str(H - 1) + "b")
    R = []
    left = 0
    right = 1
    for b in B:
        if b == "1":
            R.append((left, right))
            left = right
        right += 1
    R.append((left, right))
    
    return R


def g(S, H, W, K, block):
    wl = 0
    wr = 1
    res = 0
    while wr != W + 1:
        T = max(S[hr][wr] - S[hl][wr] - S[hr][wl] + S[hl][wl] for hl, hr in block)
        
        if T > K:
            if wr - wl == 1:
                return 10 ** 10

            res += 1
            wl = wr - 1
            continue
        wr += 1
    
    return res + len(block) - 1


def main():
    H, W, K = read_values()
    C = [input() for _ in range(H)]

    S = [[0 for _ in range(W + 1)] for __ in range(H + 1)]
    for h in range(H):
        for w in range(W):
            r = int(C[h][w])
            S[h + 1][w + 1] = S[h][w + 1] + S[h + 1][w] - S[h][w] + r

    r = v(min)
    for i in range(1 << (H - 1)):
        block = f(i, H)
        t = g(S, H, W, K, block)
        r.ud(t)
    
    print(r)
        

if __name__ == "__main__":
    main()

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

h,w,k = inm()
s = []
for i in range(h):
    s.append(ins())
mn = 20000
for t in range(2**(h-1)):
    lbl = [0]*h
    top = 0
    for i in range(1,h):
        if (t>>(i-1))%2==1:
            top += 1
        lbl[i] = top
    
    
    sm = [0]*(top+1)
    ans = top
    pos = True
    for j in range(w):
        ok = True
        tmp = [x for x in sm]
        for i in range(h):
            if s[i][j]=='1':
                tmp[lbl[i]] += 1
        if max(tmp)>k:
            ans += 1
            sm = [0]*(top+1)
        for i in range(h):
            if s[i][j]=='1':
                sm[lbl[i]] += 1
        if max(sm)>k:
            pos = False
            break
    if pos and ans<mn:
        mn = ans
print(mn)

Solution (Python):
"""
NTC here
"""
import sys
inp = sys.stdin.readline


def input(): return inp().strip()


flush = sys.stdout.flush





def iin(): return int(input())


def lin(): return list(map(int, input().split()))





def main():
    def cnt_ones(n):
        ch = 0
        x = n
        ans = []
        while x:
            if x&1:
                ans.append(ch)
            x>>=1
            ch+=1
        return ans
    ans = []
    h, w, K = lin()
    a = [list(map(int, list(input()))) for _ in range(h)]
    h1 = 2**(h-1)
    for i in range(h1):
        ch = cnt_ones(i)+[h-1]
        l1 = len(ch)
        a1 = [0]*(l1)
        ch2 = 0
        for j in range(w):
            ch1 = 0
            a2 = [0]*(l1)
            for k in range(h):
                a2[ch1]+=a[k][j]
                if ch[ch1]==k:
                    ch1+=1
            for k in range(l1):
                if a1[k]+a2[k]>K:
                    ch2 += 1
                    a1 = a2[:]
                    break
            else:
                for k in range(l1):
                    a1[k]+=a2[k]
            
            for i in a1:
                if i>K:
                    ch2 = w*10
                    break
            else:
                continue
            break
        ans.append(l1-1+ch2)
    
    print(min(ans))

"""
TEST-
4 4 1
1111
1111
1111
1111
"""


main()

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

ans = float('inf')
for i in range(1 << (h - 1)):
    cut_h = []
    for j in range(h - 1):
        if (i >> j) & 1:
            cut_h.append(j)

    blocks = []
    before = 0
    for cut in cut_h:
        blocks.append([before, cut])
        before = cut + 1
    blocks.append([before, h - 1])

    counts = [[0] * w for _ in range(len(blocks))]
    for b in range(len(blocks)):
        for j in range(blocks[b][0], blocks[b][1] + 1):
            for k in range(w):
                if s[j][k] == '1':
                    counts[b][k] += 1

    
    
    

    maxcounts = 0
    for j in range(len(counts)):
        for k in range(len(counts[0])):
            maxcounts = max(maxcounts, counts[j][k])
    if maxcounts > K:
        continue

    tmpans = len(cut_h)
    cumsums = [0] * len(blocks)
    for k in range(w):
        for b in range(len(blocks)):
            cumsums[b] += counts[b][k]

        if max(cumsums) > K:
            
            tmpans += 1
            cumsums = [counts[b][k] for b in range(len(blocks))]


    ans = min(ans, tmpans)
    
print(ans)

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

h,w,k = get_nums_l()
grid = [ input() for _ in range(h)]

ruiseki_white = [ [0] * (w+1) for _ in range(h) ]
for y in range(h):
    for x in range(w):
        ruiseki_white[y][x+1] = ruiseki_white[y][x] + (1 if grid[y][x] == "1" else 0)



def num_whites(l,r,t,b):
    ret = 0
    for y in range(t, b):
        ret += ruiseki_white[y][r] - ruiseki_white[y][l]
    
    return ret

ans = 999999999999999999

for bits in range(2**(h-1)):
    h_breaks=[0]
    for i in range(h-1):
        if bits &  2**i != 0:
            h_breaks.append(i+1)
    h_breaks.append(h)

    

    w_break_count = 0
    prev_w_break = 0
    ok = True
    for x in range(1,w+1):
        for i in range(len(h_breaks) - 1):
            top = h_breaks[i]
            bottom = h_breaks[i+1]
            left = prev_w_break
            right = x
            if num_whites(left, right, top, bottom) > k:
                
                
                if prev_w_break + 1 == x:
                    
                    ok = False
                prev_w_break = x-1
                w_break_count += 1
                break
        if not ok:
            break
    if ok:
        
        ans = min(ans, len(h_breaks)-2 + w_break_count)

print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, K, S):
    ans = 0
    S = [list(map(int, [c for c in r])) for r in S]
    
    
    
    


    ans = INF
    for p in product([0, 1], repeat=H-1):
        spl = [i+1 for i, v in enumerate(p) if v == 1]
        cand = len(spl)
        spl.append(H)
        rs = []
        p = 0
        for si in spl:
            r = [0] * W
            for j in range(W):
                for k in range(p, si):
                    r[j] += S[k][j]
            rs.append(r)
            p = si
        
        
        

        sr = [0] * len(rs)
        impossible = False
        for i in range(W):
            if any([sr[j] + rs[j][i] > K for j in range(len(rs))]):
                cand += 1
                for j in range(len(rs)):
                    sr[j] = rs[j][i]
                    if sr[j] > K:
                        impossible = True
            else:
                for j in range(len(rs)):
                    sr[j] += rs[j][i]
        if not impossible:
            ans = min(ans, cand)



    return ans


def main():
    H, W, K = read_int_n()
    S = [read_str() for _ in range(H)]
    print(slv(H, W, K, S))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter, defaultdict, deque

H, W, K = [int(x) for x in input().split()]
grid = [[int(x) for x in input()] for r in range(H)]


counts1 = Counter()
for cuts in range(2 ** H):
    numCuts = len([r for r in range(H) if (1 << r) & cuts])
    

    counts1[cuts] = numCuts
    counts2 = Counter()
    for c in range(W):
        counts3 = {}
        curr = 0
        for r in range(H):
            curr += grid[r][c]
            
            if (1 << r) & cuts or r == H - 1:
                counts3[r] = curr
                curr = 0

        if all(counts2[r] + counts3[r] <= K for r, counts in counts3.items()):

            
            for r, counts in counts3.items():
                counts2[r] += counts3[r]
        else:
            

            counts1[cuts] += 1
            if c == W - 1:
                if any(counts3[r] > K for r, counts in counts3.items()):
                    
                    counts1[cuts] = float("inf")
            counts2 = counts3
    
    

print(min(counts1.values()))