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
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *

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

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

def _max(iterable):
    ma = 0
    for i in iterable:
        ma = max(ma, i)
    return ma

for i in range(2 ** (H - 1)):
    
    div = [(i & (1 << j)) > 0 for j in range(H - 1)]
    group = [0] * H
    for j in range(H - 1):
        group[j + 1] = group[j] + 1 if div[j] else group[j]
    count = Counter()
    ans = div.count(True)
    ok = True
    for j in range(W):
        tmp = Counter()
        for k in range(H):
            if S[k][j] == '1':
                tmp[group[k]] += 1
        if _max(tmp.values()) > K:
            ok = False
        elif _max((tmp + count).values()) <= K:
            count += tmp
        else:
            count = tmp
            ans += 1
    if ok and (mi is None or ans < mi):
        mi = ans

print(mi)

Solution (Python):
from collections import defaultdict
h,w,k = map(int,input().split())

s = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
    s[i] = [int(s) for s in list(input())]



def num_to_g(num):
    
    g_index = {}
    index = 1
    for i in range(h+1):
        g_index[i] = index
        bl = (num>>i)%2
        if(bl == 1):
            index += 1
    
    return g_index
    


def get_white(choco_tmp,w,group_num):
    
    for i in range(h):
        if(s[i][w]==1):
            choco_tmp[group_num[i]] += 1
    
    return choco_tmp


def greedy(num):
    div = num_to_g(i)
    res = max(div.values())-1
    choco = defaultdict(int)
    for j in range(w):
        choco = get_white(choco,j,div)
        
        if any(c>k for c in choco.values()):
            choco = defaultdict(int)
            choco = get_white(choco,j,div)
            
            if any(c>k for c in choco.values()):
                return 10**9 + 1
            else:
                res += 1
       
    return res        
            
                
        


mx = 2**(h-1)                
ans = h+w-1
for i in range(mx):
    ans = min(ans,greedy(i))

print(ans)

Solution (Python):
from itertools import product

INF = float("inf")

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

T = [t for t in zip(*S)]
if sum(map(sum, T)) <= K:
    print(0)
    quit()

ans = INF
for P in product([0, 1], repeat=H - 1):
    cnt = sum(P)
    if cnt >= ans:
        continue

    II = [[0]]
    for i, p in enumerate(P, 1):
        if p:
            II.append([])
        II[-1].append(i)

    A = [0] * len(II)
    for t in T:
        for i, I in enumerate(II):
            A[i] += sum(t[x] for x in I)

        if any(a > K for a in A):
            cnt += 1
            if cnt >= ans:
                break

            A = [sum(t[x] for x in I) for I in II]
            if any(a > K for a in A):
              cnt = INF
              break

    ans = min(ans, cnt)

print(ans)

Solution (Python):
from itertools import product

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

T = [t for t in zip(*S)]
if sum(map(sum, T)) <= K:
    print(0)
    quit()

ans = float("inf")
for P in product([0, 1], repeat=H - 1):
    cnt = sum(P)

    II = [[0]]
    for i, p in enumerate(P, 1):
        if p:
            II.append([])
        II[-1].append(i)

    A = [0] * len(II)
    for t in T:
        for i, I in enumerate(II):
            A[i] += sum(t[x] for x in I)

        if any(a > K for a in A):
            cnt += 1
            if cnt >= ans:
                break

            A = [sum(t[x] for x in I) for I in II]
            if any(a > K for a in A):
              cnt = 1 + ans
              break

    ans = min(ans, cnt)

print(ans)

Solution (Python):
from itertools import product

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

T = [t for t in zip(*S)]
if sum(map(sum, T)) <= K:
    print(0)
    quit()

ans = float("inf")
for P in product([0, 1], repeat=H - 1):
    cnt = sum(P)
    if cnt >= ans:
        continue

    II = [[0]]
    for i, p in enumerate(P, 1):
        if p:
            II.append([])
        II[-1].append(i)

    A = [0] * len(II)
    for t in T:
        for i, I in enumerate(II):
            A[i] += sum(t[x] for x in I)

        if any(a > K for a in A):
            cnt += 1
            if cnt >= ans:
                break

            A = [sum(t[x] for x in I) for I in II]
            if any(a > K for a in A):
              cnt = 1 + ans
              break

    ans = min(ans, cnt)

print(ans)

Solution (Python):
import copy

h, w, k = map(int, input().split())
s = [[0] * w for _ in range(h)]
for i in range(h):
    inp = input()
    for j in range(w):
        s[i][j] = int(inp[j])


ans = h + w - 2

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

    
    div = []
    cut_row_begin, cut_row_end = 0, 1
    for j in range(h-1):
        if cutIdx[j] == 0:
            
            cut_row_end += 1
        else:
            
            div.append((cut_row_begin, cut_row_end))
            cut_row_begin = cut_row_end
            cut_row_end += 1
    div.append((cut_row_begin, cut_row_end))
    

    
    cnt = sum(cutIdx)
    

    
    whiteCnt = [0] * len(div)

    
    for a in range(len(div)):
        cal = 0
        for b in range(div[a][0], div[a][1]):
            cal += s[b][0]
        whiteCnt[a] = cal
    

    
    
    if max(whiteCnt) > k:
        continue

    
    if w == 1:
        ans = min(ans, cnt)

    
    search = [0] * len(div)

    
    for a in range(1, w):
        
        for b in range(len(div)):
            cal = 0
            for c in range(div[b][0], div[b][1]):
                cal += s[c][a]
            search[b] = cal

        
        
        if max(search) > k:
            break

        
        for b in range(len(div)):
            if whiteCnt[b] + search[b] > k:
                
                cnt += 1
                whiteCnt = copy.copy(search)
                break
            else:
                whiteCnt[b] += search[b]
    
    ans = min(ans, cnt)

print(ans)

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

def main():
    H,W,K = map(int, readline().split())
    S = [readline().strip() for j in range(H)]

    white = []
    for line in S:
        white.append(line.count("1"))
    white_total = sum(white)

    if white_total <= K:
        print(0)
        exit()

    ans = 10**5
    for i in range(2**(H-1)):
        impossible = False
        x = 0
        ly = bin(i).count("1")
        y_sum = [0]*(ly + 1)
        j = 0
        while j < W:
            m = 0
            y = [0]*(ly + 1)
            for k in range(H):
                if S[k][j] == "1":
                    y[m] += 1
                    if y[m] > K:
                        impossible = True
                        break
                    y_sum[m] += 1
                    if y_sum[m] > K:
                        x += 1
                        y_sum = [0]*(ly + 1)
                        j -= 1
                        break
                if (i >> k) & 1:
                    m += 1
            j += 1
            if impossible:
                x = 10**6
                break

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
h,w,k=map(int,input().split())
ans=10**9
choco=[list(input()) for i in range(h)]
sumL=[[0 for i in range(w+1)] for j in range(h+1)]
for i in range(h):
    for j in range(w):
        sumL[i][j]=sumL[i-1][j]+sumL[i][j-1]-sumL[i-1][j-1]+int(choco[i][j])
for stat in range(2**(h-1)):
    cnt=0;previous=-1
    flg=0
    cut=format(stat,"b").zfill(h-1)
    cutl=[]
    for hi in range(h-1):
        if cut[hi]=="1":
            cutl.append(hi)
            cnt+=1
    cutl.append(h-1)
    cutl.append(-1)
    for yoko in range(w):
        for seg in range(len(cutl)):
            if sumL[cutl[seg]][yoko]-sumL[cutl[seg]][previous]-sumL[cutl[seg-1]][yoko]+sumL[cutl[seg-1]][previous]>k and yoko-previous<=1:flg=1
            elif sumL[cutl[seg]][yoko]-sumL[cutl[seg]][previous]-sumL[cutl[seg-1]][yoko]+sumL[cutl[seg-1]][previous]>k:previous=yoko-1;cnt+=1
            
    if not flg and cnt < ans:ans=cnt
    
print(ans)

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

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

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

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

    count = [yoko[i][0] for i in range(cut+1)]

    if max(count) > K:
        continue

    for x in range(1, W):
        now_count = [yoko[y][x] for y in range(len(count))]
        next_count = [a + b for a, b in zip(now_count, count)]
        if max(next_count) > K:
            
            count = now_count
            cut += 1
        else:
            
            count = next_count

    ans = min(ans, cut)

print(ans)

Solution (Python):
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
input=lambda :sys.stdin.readline().rstrip()


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

value=H+W-1
if H==1:
    count=0
    countL=0
    w=0
    while w<W:
        if S[0][w]=="1":
            count+=1
        if count>K:
            countL+=1
            count=0
        else:
            w+=1
    print(countL)
else:
    for i in range(2**(H-1)):
        lst=[i>>m&1 for m in range(H-1)]
        count=[0 for i in range(lst.count(0)+1)]
        count_zero=copy.copy(count)
        idx={}
        c=0
        for h in range(H-1):
            idx[h]=c
            if lst[h]==0:
                c+=1
        idx[H-1]=c
        flag=0
        w=0
        pre_w=0
        countL=lst.count(0)
        while w<W:
            for h in range(H):

                if S[h][w]=="1":
                    count[idx[h]]+=1
            if max(count)>K:
                if pre_w==w:
                    flag=1
                    break

                pre_w=w
                countL+=1
                count=copy.copy(count_zero)
            else:
                w+=1

        if not flag:
            value=min(value,countL)
    print(value)

Solution (Python):
from itertools import product

h, w, k = list(map(int, input().split()))
s = [list(map(int, list(input()))) for i in range(h)]
INF = float("inf")
ans = INF
for bits in product([0, 1], repeat=h-1):
    cnt = sum(bits)
    cuts = [0]+[i + 1 for i, x in enumerate(bits) if x == 1]+[h]
    data = [[0]*w for _ in range(len(cuts)-1)]
    for i in range(len(cuts)-1):
        target = s[cuts[i]:cuts[i+1]]
        for tt in target:
            for j, t in enumerate(tt):
                data[i][j] += t
    check = [[0]*(w+1) for _ in range(len(data))]
    flag = False
    for j in range(w):
        if flag:
            continue
        change = False
        for i in range(len(data)):
            if check[i][j] + data[i][j] > k:
                change = True
                break
        if change:
            for i in range(len(data)):
                if data[i][j] <= k:
                    check[i][j+1] = data[i][j]
                else:
                    flag = True
                    break
            cnt += 1
        else:
            for i in range(len(data)):
                check[i][j+1] = check[i][j] + data[i][j]
    if flag:
        continue
    ans = min(ans, cnt)
print(ans)

Solution (Python):
def main():
	H, W, K = map(int, input().split())
	g = [input() for _ in range(H)]
	ans = 1 << 100
	for i in range(1 << H - 1):
		need = bin(i).count("1")
		sz = need + 1
		cnt = [0] * sz
		f = 1
		for j in range(W):
			c = 0
			for k in range(H):
				cnt[c] += g[k][j] == "1"
				if cnt[c] > K:
					break
				c += (i >> k) & 1
			else:
				continue
			cnt = [0] * sz
			need += 1
			if need > ans:
				f = 0
				break
			c = 0
			for k in range(H):
				cnt[c] += g[k][j] == "1"
				if cnt[c] > K:
					break
				c += (i >> k) & 1
			else:
				continue
			f = 0
			break
		if f:
			ans = min(ans, need)
	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
def main():
    from itertools import product

    H, W, K = map(int, input().split())
    S = [input() for _ in range(H)]
    S_T = [[int(s[w]) for s in S] for w in range(W)]
    sumS = sum(map(sum, S_T))
    ans = (H - 1) * (W - 1)

    if sumS <= K:
        print(0)
    else:
        for i in product([True, False], repeat=H-1):
            cnt = sum(i)
            if cnt >= ans:
                continue
            M = [[0]]
            for j, k in enumerate(i):
                if k:
                    M.append([])
                M[-1].append(j+1)
            A = [0] * len(M)
            for s_t in S_T:
                for l, m in enumerate(M):
                    A[l] += sum(s_t[i] for i in m)
                if any(a > K for a in A):
                    cnt += 1
                    if cnt >= ans:
                        break
                    A = [sum(s_t[i] for i in m) for m in M]
                    if any(a > K for a in A):
                        cnt = ans + 1
                        break
            ans = min(cnt, ans)
        print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import product

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
S_T = [[int(s[w]) for s in S] for w in range(W)]
sumS = sum(map(sum, S_T))
ans = (H - 1) * (W - 1)

if sumS <= K:
    print(0)
else:
    for i in product([True, False], repeat=H-1):
        cnt = sum(i)
        if cnt >= ans:
            continue
        M = [[0]]
        for j, k in enumerate(i):
            if k:
                M.append([])
            M[-1].append(j+1)
        A = [0] * len(M)
        for s_t in S_T:
            for l, m in enumerate(M):
                A[l] += sum(s_t[i] for i in m)
            if any(a > K for a in A):
                cnt += 1
                if cnt >= ans:
                    break
                A = [sum(s_t[i] for i in m) for m in M]
                if any(a > K for a in A):
                    cnt = ans + 1
                    break
        ans = min(cnt, ans)
    print(ans)

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


def count_col_whites(choco, j):
    res = 0
    for c in choco:
        if c[j]=="1":
            res += 1
    return res


def cut_chocolate(i):
    if i == 0:
        return [S]
    else:
        res = []
        pre = 0
        tmp = 0
        while i > 0:
            tmp += 1
            if i%2 == 1:
                res.append(S[pre:tmp])
                pre = tmp
            i //= 2
        res.append(S[pre:len(S)])
        return res

def is_less_than_or_equal_to_K(cut):
    for c in cut:
        for j in range(W):
            tmp = 0
            for i in range(len(c)):
                if c[i][j] == "1":
                    tmp += 1
            if tmp > K:
                return False
    return True

ans = 10**10
for i in range(2**(H-1)):
    
    cut = cut_chocolate(i)
    tmp_ans = len(cut)-1
    
    if not is_less_than_or_equal_to_K(cut):
        continue
    
    current_white_nums = [0 for _ in range(len(cut))]
    for j in range(W):
        for i in range(len(cut)):
            white_num = count_col_whites(cut[i], j)
            if white_num + current_white_nums[i] <= K:
                current_white_nums[i] += white_num
            else:
                current_white_nums = [count_col_whites(cut[_], j) for _ in range(len(cut))]
                tmp_ans += 1
                break
    ans = min(ans, tmp_ans)
print(ans)

Solution (Python):



H, W, K = map(int, input().split())
board = [['']*W for i in range(H)]
for i in range(H):
    s = list(input())
    for j in range(W):
        board[i][j] = s[j]


min_divide = 10**10
s = [0]*(H-1) 
is_ok = True


for i in range(2**(H-1)): 
    
    h_count = 0
    w_count = 0
    for j in range(H-1):
        if ((i>>j)&1):
            s[j] = 1
            h_count += 1
        else:
            s[j] = 0

    
    s_score = [0]*H 
    s_cur = [0]*H
    for j in range(W):
        c = 0
        s_cur = [0]*H

        for k in range(H):
            if board[k][j]=='1':
                s_cur[c] += 1

            
            if s_cur[c]>K:
                is_ok = False
                break

            
            if k+1<H:
                if s[k]==1:
                    c += 1
        
        if not is_ok:
            break
        
        
        group_smaller = True
        if j>0:
            for c_num in range(c+1):
                if s_score[c_num]+s_cur[c_num]>K:
                    group_smaller = False
        else:
            group_smaller = True

        if group_smaller:
            for c_num in range(c+1):
                s_score[c_num] += s_cur[c_num]
        else:
            w_count += 1
            for c_num in range(c+1):
                s_score[c_num] = s_cur[c_num]

    if not is_ok:
        is_ok = True
        continue

    for c_num in range(h_count+1):
        if s_score[c_num]>K:
            h_count = 10 ** 6

    
    min_divide = min(min_divide, w_count + h_count)


print(min_divide)

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

H,W,K = map(int,input().split())
choco = [input() for _ in range(H)]
num =(2**(H-1))

white_count = list()
min_div_count =10**6
for i in range(num):
    bin_str = format(i, 'b')
    zero = str()
    if H != len(bin_str):
        for _ in range(H-len(bin_str)):
            zero += "0"
        bin_str = zero + bin_str
    white_count = [0 for s in bin_str if s == "1"]
    white_count.append(0)
    div_count=len(white_count)-1
    
    for j in range(W):
        block_count = 0
        white_list = [0]*len(white_count)
        
        is_over = False
        for k in range(len(bin_str)):
            if bin_str[k] == "1":
                block_count += 1
            
            white_list[block_count] += int(choco[k][j])
            white_count[block_count] += int(choco[k][j])
            if white_count[block_count] > K:
                is_over = True

        if max(white_list)>K:
            break


        if is_over:
            div_count += 1
            white_count = white_list


        
        
        
        if div_count >= min_div_count:
            break
    else:
        min_div_count = div_count
print(min_div_count)

Solution (Python):
from itertools import accumulate
from operator import add


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

white_count = [0] * (w+1)
prev = [0] * (w+1)
for _ in range(h):
    line = iter('0'+input())
    cumsum_1d = accumulate(map(int, line))
    cumsum_2d = list(map(add, prev, cumsum_1d))
    prev = cumsum_2d
    white_count += cumsum_2d


def get_white(sy, sx, ny, nx):
    a = sy*(w+1) + sx
    b = sy*(w+1) + nx
    c = ny*(w+1) + sx
    d = ny*(w+1) + nx
    return white_count[d] - white_count[c] - white_count[b] + white_count[a]


ans = []
for pattern in range(2**(h-1)):
    dived = [0] + [y+1 for y in range(h-1) if (pattern>>y) & 1] + [h]
    slash_count = len(dived) - 2

    prev_x = 0
    for div_x in range(1, w + 1):
        for idx in range(len(dived)-1):
            prev_y = dived[idx]
            div_y = dived[idx+1]
            white = get_white(prev_y, prev_x, div_y, div_x)
            if white > k:
                break
        else:
            continue

        slash_count += 1
        if prev_x == div_x - 1:
            break
        prev_x = div_x - 1

    else:
        ans.append(slash_count)

print(min(ans))

Solution (Python):
from itertools import accumulate
from operator import add


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

white_count = [0] * (w+1)
prev = [0] * (w+1)
for _ in range(h):
    line = iter('0'+input())
    cumsum_1d = accumulate(map(int, line))
    cumsum_2d = list(map(add, prev, cumsum_1d))
    prev = cumsum_2d
    white_count += cumsum_2d


def get_white(sy, sx, ny, nx):
    a = sy*(w+1) + sx
    b = sy*(w+1) + nx
    c = ny*(w+1) + sx
    d = ny*(w+1) + nx
    return white_count[d] - white_count[c] - white_count[b] + white_count[a]


ans = []
for pattern in range(2**(h-1)):
    dived = [0] + [y+1 for y in range(h-1) if (pattern>>y) & 1] + [h]
    slash_count = len(dived) - 2

    prev_x = 0
    for div_x in range(1, w + 1):
        white_include = 0
        for idx in range(len(dived)-1):
            prev_y = dived[idx]
            div_y = dived[idx+1]
            white = get_white(prev_y, prev_x, div_y, div_x)
            if white > white_include:
                white_include = white

        if white_include > k:
            slash_count += 1
            if prev_x == div_x - 1:
                break
            prev_x = div_x - 1

    else:
        ans.append(slash_count)

print(min(ans))

Solution (Python):
def f(nums, K, w):
  h=len(nums)
  counter=[nums[x][0] for x in range(h)]
  if max(counter)>K:
    return float('inf')
  
  out=0
  for i in range(1, w):
    for x in range(h):
      counter[x]+=nums[x][i]
      
    if max(counter)>K:
      out+=1
      counter=[nums[x][i] for x in range(h)]
      
  return out

H, W, K=map(int, input().split())
S=[input() for _ in range(H)]
S=[[int(S[i][j]) for j in range(W)] for i in range(H)]
ans=float('inf')
for p in range(2**(H-1)):
  q='0'+format(p, '0'+str(H-1)+'b')+'1'
  i=0
  c=0
  nums=[]
  while i<H:
    j=1
    while i+j<H and q[i+j]=='0':
      j+=1
    tmp=S[i:i+j]
    nums.append([sum([tmp[y][x] for y in range(j)]) for x in range(W)])
    i+=j
    
  cand=f(nums, K, W)+q.count('1')-1
  if ans>cand:
    ans=cand
    
print(ans)

Solution (Python):
import re

H,W,K = map(int,input().split())
grid = [[0 for i in range(W+1)]]
for i in range(H):
  S = input()
  grid.append([0]+[ int(S[i]) for i in range(W) ])



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

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

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

for h in range(2**(H-1)):
  cnt = 0
  
  bin_str = format(h,"0{}b".format(H-1)) 
  
  l_p =[1]+[ x.start()+2 for x in re.finditer("1",bin_str) ] +[H+1]

  
  cnt = cnt + len(l_p) - 2
  
  ws = 0
  for w in range(1,W+1):
    for k in range(len(l_p)-1):
      if grid[l_p[k+1]-1][w]-grid[l_p[k+1]-1][w-1] > K:
        min_cnt=(H-1)*(W-1)+1
      if grid[l_p[k+1]-1][w]- (grid[l_p[k]-1][w]+grid[l_p[k+1]-1][ws]-grid[l_p[k]-1][ws]) > K:
        cnt = cnt + 1
        ws = w-1
        break    
  min_cnt = min(min_cnt,cnt)


print(min_cnt)

Solution (Python):
h,w,k = map(int,input().split())
s = [list(map(int,input())) for _ in range(h)]
    
ans = h*w
for div in range(1<<(h-1)):
    row = 0
    S = [[0]*w]
    S[row] = [s[0][i] for i in range(w)]
    for i in range(1,h):
        if 1&(div>>i-1):
            row += 1
            S.append([s[i][j] for j in range(w)])
        else:
            S[row] = [S[row][j]+s[i][j] for j in range(w)]
            
    count = [0]*(row+1)
    ans_ = row
    a = True
    for i in range(w):
        for j in range(row+1):
            if S[j][i] > k:
                a = False
                break
            count[j] += S[j][i]
            if count[j] > k:
                ans_+=1
                count = [0]*(row+1)
                for l in range(row+1):
                    count[l] += S[l][i]
                break
        if ans_ >= ans or a==False:
            break
    
    if a:
        ans = min(ans,ans_)

print(ans)

Solution (Python):
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,W,K=MI()
    S=[[]for _ in range(H)]
    for i in range(H):
        S[i]=list(input())
        
    ans=10**10
    
    import itertools
    import bisect
    
    for ite in itertools.product([0,1], repeat=H):
        
        g=[]
        cnt=[]
        cnt2=[]
        now=-1
        for i in range(len(ite)):
            if ite[i]!=now:
                g.append(i-1)
                cnt.append(0)
                cnt2.append(0)
                now=ite[i]
        g.append(H-1)
        cnt.append(0)
        cnt2.append(0)
        temp=len(g)-2
        last=[0]
        fl=0
        fl2=0
        for j in range(W):
            for k in range(len(cnt2)):
                cnt2[k]=0
            if fl2==1:
                break
            for i in range(H):
                if S[i][j]=="1":
                    num=bisect.bisect_left(g,i)
                    cnt[num]+=1
                    cnt2[num]+=1
                    if cnt[num]>K:
                        fl=1
                    
            if fl==1:
                for k in range(len(cnt)):
                    cnt[k]=cnt2[k]
                    cnt2[k]=0
                fl=0
                temp+=1
                last.append(j)
                if last[-1]==last[-2]:
                    temp=10**10
                    fl2=1
                    break
                
        
        ans=min(ans,temp)
        
    print(ans)
                
                
                    
                    
                
        
        
    

main()

Solution (Python):
    



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

s= [list(map(int,list(input()))) for i in range(h)]

bit = 1<<h
ans = 10000
for b in range(bit):
    cut = [0]+[j for j in range(1,h) if (b>>j)&1]+[h]
    tmp = len(cut)-2
    white = [0]*h
    for j in range(w):
        for i in range(h): 
            white[i] += (s[i][j])&1
        for u in range(1,len(cut)):
            tmp2 = 0
            for t in range(cut[u-1],cut[u]):
                tmp2 += white[t]
            if tmp2>k and j:
                tmp += 1
                white = [s[x][j] for x in range(h)]
            
        for u in range(1,len(cut)):
            tmp2 = 0
            for t in range(cut[u-1],cut[u]):
                tmp2 += white[t]
            if tmp2>k and j:
                tmp = 100000
                white = [s[x][j] for x in range(h)]
                break
    if ans > tmp:
        ans = tmp
print(ans)

Solution (Python):
def main():
  H,W,K = map(int,input().split())
  S = [[] for _ in range(H)]
  for i in range(H):
    for s in input():
      S[i].append(int(s))
  
  
  ans = 10000
  for i in range(2**(H-1)):
    
    
    th = bin(i).count('1')
    T = [[0 for _ in range(W)] for _ in range(th+1)]
    ti = 0
    for j in range(H):
      for k in range(W):
        T[ti][k] += S[j][k]
      if (i>>j)&1 == 1:
        ti += 1
    

    
    
    f = True
    for k in range(W):
      for j in range(th+1):
        if T[j][k] > K:
          f = False
    if not f:
      continue

    
    ans0 = th
    T0 = [0 for _ in range(th+1)]
    for k in range(W):
      f = True
      for j in range(th+1):
        T0[j] += T[j][k]
        if T0[j] > K:
          f = False
      if not f:
        ans0 += 1
        
        for j in range(th+1):
          T0[j] = T[j][k]
    ans = min(ans0,ans)
  print(ans)

main()

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

Solution (Python):
from collections import defaultdict
from itertools import product
 
H,W,K = map(int,input().split())
S = [input() for i in range(H)]

C = [[int(S[i][k]) for i in range(H)] for k in range(W)]
answer = H*W 
for X in product([True,False],repeat = H-1):
  M = [[0]]
  ans = sum(X)
  if ans > answer:
    continue
  for i,x in enumerate(X):
    if x:
      M.append([])
    M[-1].append(i+1)
  D = [0]*len(M)
  for c in C:
    for k,m in enumerate(M):
      D[k] += sum(c[i] for i in m)
      
    if any(d>K for d in D):
      ans += 1
      if ans >answer:
        break
      D = [sum(c[i] for i in m) for m in M]
      if any(d>K for d in D):
        ans = answer + 1
        
        break
  answer = min(answer,ans)
print(answer)

Solution (Python):
import itertools

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

def solve(blocks):
    n_block = len(blocks)
    n_cut = n_block - 1
    sums = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(a > K for a in adds):
            return H * W
        
        sums = [s + a for s, a in zip(sums, adds)]
        if any(s > K for s in sums):
            n_cut += 1
            sums = adds
    
    return n_cut

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    ans = min(ans, solve(blocks))
print(ans)

Solution (Python):
from collections import defaultdict
from itertools import product
 
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
 
C = [[int(s[i]) for s in S] for i in range(W)]

total = sum(sum(c) for c in C)
 
answer = H * W
for X in product([False, True], repeat=H-1):
  
  ans = sum(X)
  if ans > answer:
    continue
  M = [[0]]
  for i, x in enumerate(X):
    if x:
      M.append([])
    M[-1].append(i+1)
  D = [0] * len(M)
  for c in C:
    for k, m in enumerate(M):
      D[k] += sum(c[i] for i in m)
      
    if any(d > K for d in D):
      ans += 1
      if ans > answer:
        break
      D = [sum(c[i] for i in m) for m in M]
      if any(d > K for d in D):
        ans = answer + 1
        break
  answer = min(answer, ans)

print(answer)