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



Sample input:
3 5 4
11100
10001
00111


Sample output:
2

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
s = [input() for _ in range(h)]
data_yoko = [[0]*(w+1) for _ in range(h)]
for i in range(w):
    for j in range(h):
        if s[j][i] == "1":
            data_yoko[j][i+1] = 1
        data_yoko[j][i+1] += data_yoko[j][i]
data_tate = [[0]*w for _ in range(h+1)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "1":
            data_tate[i+1][j] = 1
        data_tate[i+1][j] += data_tate[i][j]

ans = h*w
for case in range(2**(h-1)):
    now = 0
    use = []
    for bit in range(h-1):
        if case>>bit & 1:
            use.append(bit+1)
            now += 1
    use.append(h)
    left = [0]*len(use)
    pre = -1
    check1 = True
    check2 = True
    #print(*use)
    for i in range(w):
        for j in range(len(use)):
            to = data_tate[use[j]][i] if j == 0 else data_tate[use[j]][i]-data_tate[use[j-1]][i]
            if k < to:
                check1 = False
            if to + left[j] > k:
                check2 = False
            left[j] += to
        #print(left,check1,check2)
        if not check1:
            break
        if check2:
            continue
        for j in range(len(use)):
            left[j] = data_tate[use[j]][i] if j == 0 else data_tate[use[j]][i]-data_tate[use[j-1]][i]
        now += 1
        check2 = True
    if check1:
        #print(now,use)
        ans = min(ans,now)

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    last_res=float("inf")
    readline=stdin.readline
    H,W,K=map(int,readline().split())
    grid=[]
    for i in range(H):
        s=readline().strip()
        grid.append(s)

    for i in range(1<<(H-1)):
        output=[]
        for j in range(H-1):
            if(i>>j)&1:
                output.append(j)
        count=[0]*(len(output)+1)
        res=len(output)

        for b in range(W):
            now=0
            flag=False
            for a in range(H):
                if len(output)>now and  a>output[now]:
                    now+=1
                if grid[a][b]=="1":
                    count[now]+=1
                    if count[now]>K:
                        count=[0]*(len(output)+1)
                        res+=1
                        flag=True
                        break
            if flag:
                now=0
                flag=False
                for a in range(H):
                    if len(output)>now and  a>output[now]:
                        now+=1
                    if grid[a][b]=="1":
                        count[now]+=1
                        if count[now]>K:
                            res+=1
                            flag=True
                            break
                if flag:
                    break
        if flag:
            res=float("inf")
        last_res=min(last_res,res)
    print(last_res)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
# PyPy3 test

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)

Submission status: Accepted

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

# 横の割り方を全通り試す(2**(H-1))
ans = float('inf')
flag = False
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])
                if chocos[-1][w] > K:
                    flag = True
                    break
            if flag:
                break
    if flag:
        flag = False
        continue
    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 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)

Submission status: Accepted

Solution code:
import itertools

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

ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):
    # print("t:",t,"横ライン")
    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)
    # print("lst:",lst)
    # print(cnt,L)
    sum_lst = [0] * L
    for w in range(W):
        # print([lst[i][w] for i in range(L)])
        if max(lst[i][w] for i in range(L)) > K:
            # print("break")
            break
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        # print("w=",w,tmp)
        if max(tmp) > K:
            cnt += 1
            # print("切る!!")
            sum_lst = [lst[i][w] for i in range(L)]
            # print(sum_lst)
        else:
            sum_lst = tmp
    else: # for文がすべて回り切ったら、発動
        ans = min(ans, cnt)
print(ans)
"""
for t in itertools.product([0, 1], repeat=H - 1):
    print(t)
"""

Submission status: Accepted

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

count=[]
for i in range(h):
  L=[0]
  for j in range(w):
    L.append(int(l[i][j])+L[-1])
  count.append(L)

b=[]
for i in range(2**(h-1)):
  b.append(format(i,'0'+str(h-1)+'b'))

ans=[]
cut=0
for i in range(len(b)):
  cutct=0
  cut=0
  f=0
  for j in range(1,w+1):
    ct=[]
    for j2 in range(h):
      ct.append(count[j2][j]-count[j2][cut])
    check=[]
    x=ct[0]
    for j3 in range(h-1):
      if b[i][j3]=='0':
        x+=ct[j3+1]
      else:
        check.append(x)
        x=ct[j3+1]
    check.append(x)
    if max(check)>k:
      if cut-j<=1:
        ctcheck=[]
        for j2 in range(h):
          ctcheck.append(count[j2][j-1]-count[j2][cut])
        check=[]
        x=ctcheck[0]
        for j3 in range(h-1):
          if b[i][j3]=='0':
            x+=ctcheck[j3+1]
          else:
            check.append(x)
            x=ctcheck[j3+1]
        check.append(x)
        if max(check)>k:
          f=1
      cut=j-1
      cutct+=1
    if cut==w-1:
      ctcheck=[]
      for j2 in range(h):
        ctcheck.append(count[j2][w]-count[j2][cut])
      check=[]
      x=ctcheck[0]
      for j3 in range(h-1):
        if b[i][j3]=='0':
          x+=ctcheck[j3+1]
        else:
          check.append(x)
          x=ctcheck[j3+1]
      check.append(x)
      if max(check)>k:
        f=1
  ct1=0
  for j4 in range(h-1):
    if b[i][j4]=='1':
      ct1+=1
  if f==0:
    ans.append(cutct+ct1)
print(min(ans))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    h,w,k = LI()
    a = [list(map(int, input())) for i in range(h)]
    s = [[0]*(w+1)]+[[0]+list(accumulate(i)) for i in a]
    for j in range(w+1):
        for i in range(h):
            s[i+1][j] += s[i][j]
    ans = float("inf")
    for b in range(1<<(h-1)):
        l = [0]
        for i in range(h-1):
            if b&(1<<i):
                l.append(i+1)
        l.append(h)
        ll = len(l)-1
        su = [0]*ll
        m = bin(b).count("1")
        p = 0
        f = 0
        for j in range(1,w+1):
            for i in range(ll):
                u = l[i]
                d = l[i+1]
                su[i] += s[d][j]-s[d][p]-s[u][j]+s[u][p]
                if su[i] > k:
                    m += 1
                    p = j-1
                    su = [0]*ll
                    for ii in range(ll):
                        u = l[ii]
                        d = l[ii+1]
                        su[ii] = s[d][j]-s[d][p]-s[u][j]+s[u][p]
                        if su[ii] > k:
                            f = 1
                    break
            p = j
            if f:
                m = float("inf")
                break
        if m < ans:
            ans = m
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

n = H - 1
ans = H * W
for i in range(2 ** n):
    horizon = [0]
    length = 2
    for j in range(n):
        if ((i >> j) & 1):
            horizon.append(j + 1)
            length += 1
    horizon.append(H)
    vertical = 0
    y1 = 0
    for y2 in range(1, W + 1):
        for k in range(length - 1):
            x2 = horizon[k + 1]
            x1 = horizon[k]
            sq = s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]
            sq_pre = s[x2][y2 - 1] - s[x1][y2 - 1] - s[x2][y1] + s[x1][y1]

            if(sq > K):
                if(sq_pre > K):
                    vertical = 1e+9
                else:
                    vertical += 1
                    y1 = y2 - 1
                break
    if (vertical >= W):
        vertical = 1e+9
    ans = min(ans, (vertical) + (length - 2))
print(ans)

Submission status: Accepted

Solution code:
import itertools
H, W, K = map(int, input().split())

S = [0]*H
for i in range(H):
  S[i] = input()
Sdivs = []
mcnt = 1100
for b in itertools.product([0, 1], repeat=H-1):
  start = 0
  end = 1
  Sdivs=[]
  for a in b:
    if a==1:
      Sdivs.append(S[start:end])
      start = end
    end += 1
  Sdivs.append(S[start:end])
  cnt = sum(b)
  #print(b,cnt,Sdivs)
  ones_cum = [0]*len(Sdivs)
  mark1,mark2 = True,True
  ws = [0]
  w = 1
  while w<W+1 and mark2:
    for i,Sdiv in enumerate(Sdivs):
      #print(w,ws)
      for s in Sdiv:
        ones_cum[i] += s[w-1]=='1'
      if ones_cum[i] > K:
        #print(i,w,ones_cum[i])
        mark1 = False
        if w-1 == ws[-1]:
          #print(w-1)
          mark2 = False
          break
        ws.append(w-1)
        w -= 1
        break
    if mark1 == False:
      mark1 = True
      ones_cum = [0]*len(Sdivs)
    w+=1
  #print(cnt,mark2)
  if mark2 == False:
    continue
  cnt += len(ws)-1
  #print(cnt)
  mcnt = min(mcnt,cnt)
print(mcnt)

Submission status: Accepted

Solution code:
from collections import Counter


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

best = float("inf")
for cuts in range(2 ** H):
    # Initialize numCuts to the number of horizontal cuts
    hCutIndices = [r for r in range(H) if (1 << r) & cuts]
    numCuts = len(hCutIndices)

    # The count for each horizontal cut since last cut
    cumulativeCount = Counter()

    for c in range(W):
        # The count for each horizontal cut for this column
        columnCount = {}
        curr = 0
        for r in range(H):
            curr += grid[r][c]
            if (1 << r) & cuts or r == H - 1:  # Note: last row is always a cut
                columnCount[r] = curr
                curr = 0

        # Add column count to cumulative count if possible
        if all(cumulativeCount[r] + columnCount[r] <= K for r in columnCount):
            for r in columnCount:
                cumulativeCount[r] += columnCount[r]
        else:
            # Cut and reset cumulative count to this column
            numCuts += 1
            cumulativeCount = columnCount
            # If counts within just the column is no good, the current set of horizontal cuts is impossible
            if any(counts > K for r, counts in columnCount.items()):
                numCuts = float("inf")
                break
    best = min(best, numCuts)

print(best)

Submission status: Accepted

Solution code:
import itertools

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

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

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

for i in range(w):
  cnt[0][i] = int(s[0][i]) + (0 if i == 0 else cnt[0][i - 1])

for i in range(1, h):
  for j in range(1, w):
    cnt[i][j] = cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1] + int(s[i][j])

num = [i for i in range(h - 1)]
ans = 99999
for i in range(0, h):
  for v in itertools.combinations(num, i):
    n = list(v)
    n.append(h - 1)
    
    _ans = i
    _left = -1
    for j in range(w):
      for _k in range(len(n)):
        if cnt[n[_k]][j] - (0 if _left < 0 else cnt[n[_k]][_left]) - (0 if _k == 0 else cnt[n[_k - 1]][j]) + (0 if _left < 0 or _k == 0 else cnt[n[_k - 1]][_left]) > k:
          if j - _left == 1:
            _ans = 99999
            break
          _left = j - 1
          j -= 1
          _ans += 1
          break
    ans = min(ans, _ans)

print(ans)

Submission status: Accepted

Solution code:
import sys 
MOD = 10**9 +7
INF = 10**5

def main():
    h,w,k = map(int,input().split())
    grid = [[0] * (w + 1)] + [[0] + [int(i) for i in list(input())] for _ in range(h)]
    

    for i in range(h + 1):
        for j in range(1,w + 1):
            grid[i][j] += grid[i][j - 1]
    
    for i in range(1,h + 1):
        for j in range(w + 1):
            grid[i][j] += grid[i - 1][j]
    #print(grid)
    ans = INF
    for bit in range(1<<(h - 1)):
        flag = False
        cut = [0]
        for i in range(h - 1):
            if (bit>>i)&1:
                    cut.append(i + 1)
        cut.append(h)
        #print(cut)
        l = len(cut)
        cnt = l - 2
        c = 0
        for j in range(1,w + 1):
            for i in range(1,l):
                #print(c)
                a = cut[i - 1]
                b = cut[i]
                if grid[b][j] - grid[b][c] - grid[a][j] + grid[a][c] > k:
                    if j != 1:
                        c = j - 1
                        cnt += 1
                        break
                    else:
                        flag = True
                        break
            if flag:
                break
        if flag == False:
            ans = min(ans,cnt)
    
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

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

S = [0] * H
data = [[0]*W for i in range(H)]

for i in range(H):
    S[i] = list(map(int,list(str(input()))))

data[0][0] = S[0][0]

for i in range(1,W):
    data[0][i] = data[0][i-1] + S[0][i]

for i in range(1,H):
    data[i][0] = data[i-1][0] + S[i][0]

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

#print(S)
#print(data)

m = 10**4
for i in range(2**(H-1)):
    cross = []
    tate = []
    for j in range(H-1):
        if i&(2**j) == 2**j:
            cross.append(j)
    #print(cross)
    
    det2 = 0
    start = 0
    for j in range(W):
        det = 0
        if len(cross) > 0:
            for k in range(len(cross)):
                if (k == 0 and start == 0 and data[cross[k]][j] > K):
                    det = -1
                    break
                elif (k == 0 and start != 0 and data[cross[k]][j] - data[cross[k]][start-1] > K):
                    det = -1
                    break
                elif (start == 0 and k != 0 and data[cross[k]][j]-data[cross[k-1]][j] > K):
                    det = -1
                    break
                elif (start != 0 and k != 0 and data[cross[k]][j]-data[cross[k]][start-1]-data[cross[k-1]][j]+data[cross[k-1]][start-1] > K):
                    det = -1
                    break
            if (start == 0 and data[H-1][j] - data[cross[-1]][j]> K):
                det = -1
            elif (start != 0 and data[H-1][j]-data[cross[-1]][j]-data[H-1][start-1]+data[cross[-1]][start-1] > K):
                det = -1
        #if i == 2**(H-1)-1:
        #    print("k",k,start,det)
        else:
            if (start == 0 and data[H-1][j] > K):
                det = -1
            elif (start != 0 and data[H-1][j] - data[H-1][start-1] > K):
                det = -1
        if det == -1:
            if j == start:
                det2 = -1
                break
            else:
                tate.append(j-1)
                start = j
        #if i == 2**(H-1)-1:
        #    print("tate",tate)
    
    if det2 == 0:
        #print(start,len(cross)+len(tate))
        m = min(m,len(cross)+len(tate))

print(m)

Submission status: Accepted

Solution code:
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+1):
    if max(list(cut(sep[x],j,sep[x-1],left) for x in range(1,len(sep)))) > k:
      break
    if j<w and max(list(cut(sep[x],j+1,sep[x-1],left) for x in range(1,len(sep)))) > k:
      anstmp += 1
      left = j
  else:
    ans = min(ans,anstmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
def ass(v):
    if not v:
        print(-1)
        sys.exit(0)

h, w, k = map(int, input().split())
grid = [[1 if v == '1' else 0 for v in input()] for _ in range(h)]


ass(h > 0 and w > 0 and k > 0)
for row in grid:
    ass(len(row) == w)


def count_ones(i):
    cnt = 0
    while i:
        if i & 1:
            cnt += 1
        i >>= 1
    return cnt

ans = h + w

for state in range(1 << h):
    j = 0
    vcnt = 0
    counters = [0] * (h + 1)
    is_ok = True
    while j < w:
        hi = 0
        i = 0
        local_counters = [0] * (h + 1)
        ass(len(counters) == len(local_counters))
        while i < h:
            if (1 << i) & state:
                hi = i
            # print(hi, i, j)
            # print(grid[i])
            ass(len(local_counters) > hi)
            ass(i < h and j < w)
            ass(len(grid) > i)
            ass(len(grid[i]) > j)
            local_counters[hi] += grid[i][j]
            i += 1
        for i, v in enumerate(local_counters):
            if v > k:
                is_ok = False
                break
            counters[i] += local_counters[i]
        if not is_ok:
            break
        # ass(len(counters))
        # ass(k)
        if max(counters) > k:
            counters = local_counters[:]
            vcnt += 1

        j += 1


    if is_ok and ans > count_ones(state) + vcnt:
        ans = count_ones(state) + vcnt
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
def main():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    S = [list(map(int, input().rstrip())) for _ in range(H)]

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

    def sm(a,b): #b:exclusive
        i1,j1 = a
        i2,j2 = b
        return C[i2][j2] - C[i1][j2] - C[i2][j1] + C[i1][j1]
    
    ans = 10**9
    for p in range(1<<(H-1)):
        ha = []
        i = 1
        tmp = 0
        p1 = p
        while p1:
            if p1&1: ha.append(i)
            i += 1
            p1 >>= 1
        tmp += len(ha)
        ha.append(H)
        #print(ha,tmp)
        j1, j2 = 0, 1
        flag = False
        while j2 <= W:
            mx = 0
            i1 = 0
            for i2 in ha:
                mx = max(mx, sm((i1,j1),(i2,j2)))
                i1 = i2
            #print(mx,j1,j2)
            if mx > K:
                if j2-j1==1:
                    flag = True
                    break
                tmp += 1
                j1 = j2-1
            else:
                j2 += 1
        if flag: continue
        #print(tmp,p)
        ans = min(ans, tmp)

    print(ans)

if __name__ == '__main__':
    main()