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):
h,w,k = map(int,input().split())

sl = []
for _ in range(h):
    s = list(input())
    s = [int(i) for i in s]
    sl.append(s)
import itertools
sl_ac = []
for s in sl:
     ac = [0] + list(itertools.accumulate(s))
     sl_ac.append(ac)

anss = float("inf")


from itertools import product
for bits in product([0, 1], repeat=h-1):
    ans = 0
    ans += sum(bits)
    p = 0
    group = [0 for i in range(h)]
    for idx, bit in enumerate(bits):
        group[idx] = p
        p += bit
    group[-1] = p
    sum_group = [0 for i in range(sum(bits) + 1)]
    reset = 0
    flag = "OK"
    for i in range(w):
        for j in range(h):
            sum_group[group[j]] += sl[j][i]
        if max(sum_group) > k:
            if i == 0:
                flag = "NG"
            else:
                ans += 1
                reset = i
                sum_group = [0 for i in range(sum(bits) + 1)]
                for j in range(h):
                    sum_group[group[j]] += sl[j][i]
                if max(sum_group) > k:
                    flag = "NG"

    if flag == "OK":
        anss = min(ans, anss)
print(anss)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



from itertools import product

H,W,K = LI()
S = [list(map(str, input())) for _ in range(H)]

A = product([0,1],repeat=H-1)
ans = float('inf')
for a in A:
    count = 0
    for a0 in a:
        if a0 == 1:
            count += 1
    List = []
    now = []
    for i in range(H):
        now.append(i)
        if i != H-1:
            if a[i] == 1:
                List.append(now)
                now = []
    List.append(now)
    n = len(List)
    nums = [0]*n
    now_nums = [0]*n
    for j in range(W):
        flag = False
        
        for k,L in enumerate(List):
            for l in L:
                if S[l][j] == '1':
                    now_nums[k] += 1
        
        for k in range(n):
            if now_nums[k] > K:
                flag = True
                break
        
        c_flag = False
        for k in range(n):
            if nums[k]+now_nums[k] > K:
                count += 1
                c_flag = True
                break
        
        if c_flag:
            nums = now_nums[:]
            now_nums = [0]*n
        else:
            for k in range(n):
                nums[k] += now_nums[k]
            now_nums = [0]*n

        if flag:
            break
    if flag:
        continue

    if count < ans:
        ans = count

print(ans)

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

h,w,KK = map(int,input().split())

if h == 1:
    s = input()
    res = 0
    cnt = 0
    for i in range(w):
        if s[i] == "1":
            cnt += 1
            if cnt == KK and i != w-1:
                res += 1
                cnt = 0
    print(res)
    exit()

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

res = 10**9

d = dict()
for i in range(1<<(h-1)):
    tmp = 0
    for j in range(h-1):
        d[j] = tmp
        if (i>>j)&1 == 1:
            tmp += 1
    d[h-1] = tmp
    cnt = [0]*h


    for j in range(w):
        r = [0]*h
        judge = False
        for k in range(h):
            if s[k][j] == "1":
                r[d[k]] += 1
                if r[d[k]] > KK:
                    tmp = 10**9
                    break
                if r[d[k]] + cnt[d[k]] > KK:
                    judge = True
        if tmp == 10**9:
            break
        if judge:
            tmp += 1
            for k in range(h):
                cnt[k] = r[k]
        else:
            for k in range(h):
                cnt[k] += r[k]



    if res > tmp:
        res = tmp
print(res)

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

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

ans = (H-1) * (W-1)
for bit in range(1<<(H-1)):
	hs = []
	cur = [0]
	res = 0
	for i in range(1, H):
		if bit & (1 << (i-1)) == 0:
			cur.append(i)
		else:
			res += 1
			hs.append(cur)
			cur = [i]
	hs.append(cur)
	
	ng = False
	whites = [0 for _ in range(len(hs))]
	for c, d in enumerate(hs):
		for h in d:
			if s[h][0] == "1":
				whites[c] += 1
		if whites[c] > k:
			ng = True
	

	for w in range(1, W):
		tmp = [0 for _ in range(len(hs))]
		for c, d in enumerate(hs):
			for h in d:
				if s[h][w] == "1":
					tmp[c] += 1
			if tmp[c] > k:
				ng = True

		over = False
		for c in range(len(hs)):
			if whites[c] + tmp[c] > k:
				over = True

		if over:
			res += 1
			whites = tmp
		else:
			whites = [wh + t for wh, t in zip(whites, tmp)]
		

	if not ng:
		ans = min(ans, res)

print(ans)

Solution (Python):
h,w,k = map(int,input().split())
a = [list(input()) for i in range(h)]
acc = [[0 for i in range(w+1)] for j in range(h+1)]
for i in range(1,h+1):
  for j in range(1,w+1):
    acc[i][j] = acc[i-1][j]
    if a[i-1][j-1] == "1":
      acc[i][j] += 1
for i in range(1,h+1):
  for j in range(1,w+1):
    acc[i][j] += acc[i][j-1]
ans = 1000000
def cut(x,y,up,left):
  return acc[x][y]-acc[x][left]-acc[up][y]+acc[up][left]
for i in range(2**(h-1)):
  sep = [0]
  for r in range(h-1):
    if i&1<<r:
      sep.append(r+1)
  sep.append(h)
  anstmp = len(sep)-2
  left = 0
  for j in range(1,w):

    if max(list(cut(sep[x],j,sep[x-1],left) for x in range(len(sep)))) > k:
      break
    if max(list(cut(sep[x],j+1,sep[x-1],left) for x in range(len(sep)))) > k:
      anstmp += 1
      left = j
  else:
    ans = min(ans,anstmp)
print(ans)

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

mi = 1 << 20
for i in range(1 << H - 1):
    X = []
    l = 0
    ii = i
    pc = 0
    while ii:
        a = ii & -ii
        ii -= a
        r = a.bit_length()
        X.append((l, r))
        l = r
        pc += 1
    X.append((l, H))
    Y = [0] * (pc + 1)
    l = 0
    cnt = 0
    r = l + 1
    ngflg = 0
    while r <= W + 1:
        for a, b in X:
            if S[b][r] - S[b][l] - S[a][r] + S[a][l] > K:
                if r == l + 1:
                    ngflg = 1
                    break
                l = r - 1
                cnt += 1
                break
        else:
            r += 1
        if ngflg: break
    if ngflg: continue
    mi = min(mi, pc + cnt)

print(mi)

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

H,W,K=map(int,input().split())
MAP=[input().strip() for i in range(H)]

ANS=1<<30
for i in range(1<<(H-1)):
    A=[]
    for j in range(H):
        if i & (1<<j) !=0:
            A.append(j+1)
    

    SCORE=len(A)
    B=[0]*(len(A)+1)

    for w in range(W):
        ind=0
        for i in range(H):           
            if ind<len(A) and i==A[ind]:
                ind+=1
            if MAP[i][w]=="1":
                B[ind]+=1

        
        if max(B)>K:
            SCORE+=1
            B=[0]*(len(A)+1)
            ind=0

            for i in range(H):           
                if ind<len(A) and i==A[ind]:
                    ind+=1
                if MAP[i][w]=="1":
                    B[ind]+=1

        
        if max(B)>K:
            break
    else:
        ANS=min(ANS,SCORE)

print(ANS)

Solution (Python):
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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


H, W, K = list(map(int, sys.stdin.buffer.readline().split()))
S = [list(map(int, list(sys.stdin.buffer.readline().decode().rstrip()))) for _ in range(H)]







def solve(counts):
    ts = [0] * len(counts)
    ret = 0
    for w in range(W):
        s = [0] * len(counts)
        div = False
        for i, cnts in enumerate(counts):
            s[i] += cnts[w]
            if s[i] > K:
                return INF
            if s[i] + ts[i] > K:
                div = True
        if div:
            ret += 1
            ts = s
        else:
            for i, c in enumerate(s):
                ts[i] += c
    return ret


if H == 1:
    ans = solve(S)
else:
    
    ans = INF
    for divs in itertools.product([True, False], repeat=H - 1):
        counts = []
        li = [0] * W
        for h, div in enumerate(divs):
            for w, c in enumerate(S[h]):
                li[w] += c
            if div:
                counts.append(li)
                li = [0] * W
        for w, c in enumerate(S[-1]):
            li[w] += c
        counts.append(li)
        ans = min(ans, solve(counts) + sum(divs))
print(ans)

Solution (Python):
from itertools import product,accumulate

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

grid = tuple(tuple(map(int,input())) for _ in range(H))

def check(gids):
    cnt = 0
    s = [0]*(gids[-1]+1)
    for i in range(W):
        for h,gid in enumerate(gids):
            s[gid] += grid[h][i]
        if any(v > K for v in s):
            cnt += 1
            s = [0]*(gids[-1]+1)
            for h,gid in enumerate(gids):
                s[gid] += grid[h][i]
            if any(v > K for v in s):
                return float('inf')
    return cnt

def it():
    for p in product(range(2),repeat=H-1):
        gids = [0]+list(accumulate(p))
        yield check(gids)+gids[-1]

print(min(it()))

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

ans = 1000000
for i in range(2**(h-1)):
    b = format(i, "0{}b".format(h-1))
    ans_temp = b.count("1")
    white_after = [0]*(ans_temp+1)
    index = 0
    flag = 1
    for j in range(w):
        for k in range(h):
            if grid[k][j] == "1":
                white_after[index] += 1
            if k != h-1:
                if b[k] == "1":
                    index += 1
        if max(white_after) <= K:
            white_before = white_after[:]
        else:
            try:
                for k in range(len(white_after)):
                    white_after[k] -= white_before[k]
                    if white_after[k] > K:
                        flag = 0
                white_before = white_after[:]
                ans_temp += 1
            except:
                flag = 0
                break
        index = 0
    if flag == 0:
        continue
    ans = min(ans, ans_temp)

print(ans)

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

ret = 10 ** 18
for bit_state in range(1 << (h - 1)):
    memo = {}
    pos = 0
    res = 0
    for i in range(h - 1):
        memo[i] = pos
        if bit_state & (1 << i):
            pos += 1
    memo[h - 1] = pos
    len_m = (pos + 1)
    ans = [0] * len_m
    
    flag = False
    for j in range(w):
        tmp = [0] * len_m
        for i in range(h):
            if s[i][j] == "1":
                tmp[memo[i]] += 1
        for i in range(len_m):
            if tmp[i] > k:
                flag = True
        for i in range(len_m):
            if tmp[i] + ans[i] > k:
                res += 1
                for i in range(len_m):
                    ans[i] = tmp[i]
                break
        else:
            for i in range(len_m):
                ans[i] += tmp[i]
    if not flag:
        ret = min(ret, res + len_m - 1)
print(ret)

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10**16

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

ans = INF
for bit in range(1<<(H-1)):
    zones = []
    tmp = [0]
    for h in range(H-1):
        if bit&(1<<h):
            zones.append(tmp)
            tmp = [h+1]
        else:
            tmp.append(h+1)
    zones.append(tmp)
    L = len(zones)
    Scores = [0]*L
    tmp_point = L-1
    for w in range(W):
        out = False
        C = []
        for l, z in enumerate(zones):
            p = 0
            for i in z:
                if state[i][w]:
                    p += 1
            C.append(p)
            if p + Scores[l] > K:
                out = True
            Scores[l] += p
        if max(C) > K:
            tmp_point = INF
            break
        if out:
            tmp_point += 1
            Scores = C[:]
    if tmp_point < ans:
        ans = tmp_point

print(ans)

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

h,w,k = nm()
s = [list(map(int, list(ns()))) for _ in range(h)]
ans = h*w
for bit in range(1<<(h-1)):
    d = dict()
    l = list()
    q = [0]
    for j in range(h-1):
        if bit & (1<<j):
            l.append(tuple(q))
            q = list()
        q.append(j+1)
    l.append(tuple(q))
    t = len(l)
    for i in range(t):
        for x in l[i]:
            d[x] = i
    cur = bin(bit).count('1')
    g = [0]*t
    for j in range(w):
        c = [0]*t
        for i in range(h):
            c[d[i]] += s[i][j]
        if max(c) > k:
            cur = h*w
            break
        for i in range(t):
            g[i] += c[i]
        if max(g) > k:
            cur += 1
            g = c[:]
    if ans > cur: ans = cur
print(ans)

Solution (Python):

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

A = []
for i in range(H):

    a = list(map(int,list(input())))
    A.append(a)


ans = float("inf")

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

    wtk = [0]
    cut = 0

    for j in range(H-1):

        if i & 2**j > 0:
            wtk.append(wtk[-1]+1)
            cut += 1
        else:
            wtk.append(wtk[-1])

    now = [0] * (H)

    for y in range(W):

        flag = True
        nnow = []
        for ll in now:
            nnow.append(ll)
        save = [0] * (H)

        for x in range(H):

            nnow[wtk[x]] += A[x][y]
            save[wtk[x]] += A[x][y]

        if max(save) > K:
            cut = float("inf")
            break
        if max(nnow) > K:
            cut += 1
            nnow = save

        now = nnow

    ans = min(ans,cut)
            
print (ans)

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

    H, W, K = map(int, input().split())
    grid = []
    for _ in range(H):
        line = input().rstrip('\n')
        grid.append([int(s) for s in line])

    ans = 10**9
    for i in range(2**(H-1)):
        tmp = 0
        h_list = [[0]]
        for j in range(H-1):
            if i >> j & 1:
                tmp += 1
                h_list.append([j+1])
            else:
                h_list[-1].append(j+1)
        L = len(h_list)
        white = [0] * L
        ok = 1
        for w in range(W):
            white_new = [0] * L
            for l in range(L):
                for h in h_list[l]:
                    if grid[h][w] == 1:
                        white_new[l] += 1
            if max(white_new) > K:
                ok = 0
            flg = 0
            for l in range(L):
                if white[l] + white_new[l] > K:
                    flg = 1
            if flg:
                tmp += 1
                white = white_new
            else:
                for l in range(L):
                    white[l] += white_new[l]
        if ok:
            ans = min(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n, m, K = na()
b = []
for i in range(n):
    b.append(ns())

ans = 999999999999999
for ptn in range(1<<n-1):
    lans = 0
    x = ptn
    while x > 0:
        lans += x&1
        x //= 2

    to = [0] * n
    for i in range(1,n):
        if ptn>>i-1&1:
            to[i] = i
        else:
            to[i] = to[i-1]
    f = [0] * n
    ok = True
    o = ord("0")
    for j in range(m):
        plus = [0] * n
        for r in range(n):
            plus[to[r]] += ord(b[r][j])-o
            if plus[to[r]] > K:
                ok = False
                break

        if not ok:
            break
        reset = any(f[r] + plus[r] > K for r in range(n))
        if reset:
            lans += 1
            f = plus
        else:
            for i in range(n):
                f[i] += plus[i]
    if not ok:
        continue
    ans = min(ans, lans)
print(ans)

Solution (Python):
h, w, kk = [int(i) for i in 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)
    ook = True
    for j in range(w):
        k = 0
        for l in range(h):
            if s[l][j] == "1":
                b[k] += 1
            if (i >> l) & 1 == 1:
                k += 1

        ok = True
        for l in b:
            if l > kk:
                ok = False

        if not ok:
            aa += 1
            b = [0] * (c + 1)

            k = 0
            for l in range(h):
                if s[l][j] == "1":
                    b[k] += 1
                if (i >> l) & 1 == 1:
                    k += 1

            ok = True
            for l in b:
                if l > kk:
                    ok = False
            if not ok:
                ook = False
                break
    if ook:
        ans = min(ans, aa)

print(ans)