Problem p02733 (python)

Fixed submission:

def main():
    from itertools import product
    import numpy as np

    H,W,K = map(int, input().split())
    S = (np.array([list(map(int,list(input()))) for _ in range(H)]).T).tolist()

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.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 s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()

Buggy submission (verdict: Runtime Error):

def main():
    from itertools import product

    H,W,K = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    
    i = 0
    while i < len(S):
        if '1' in S[i]:
            i += 1
        else:
            del S[i]
    H = len(S)
 
    S = [[int(s[i]) for s in S] for i in range(W)]

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.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 s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()

Buggy submission (verdict: Runtime Error):

def main():
    from itertools import product

    H,W,K = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    
    i = 0
    while i < len(S):
        if '1' in S[i]:
            i += 1
        else:
            del S[i]
    H = len(S)
 
    S = [[int(s[i]) for s in S] for i in range(W)]

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = np.array([0]*len(M))
            for s in S:
                D[:] += [sum(s[i] for i in m) for m in M]
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    D[:] = [sum(s[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)

main()

Buggy submission (verdict: Runtime Error):
import numpy as np
from itertools import product

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

if sum(sum(s) for s in S)<=K:
    print(0)
else:
    answer = (H-1) * (W-1)
    for X in product([False,True], repeat=H-1):
        ans = np.sum(X)
        if ans >= answer:
            continue
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])
            M[-1].append(i+1)
        D = np.array([0]*len(M))
        for s in S:
            D[:] += [sum(s[i] for i in m) for m in M]
            if any(d > K  for d in D):
                ans += 1
                if ans >= answer:
                    break
                D[:] = [sum(s[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)

Buggy submission (verdict: Runtime Error):
import numpy as np
from itertools import product

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

if sum(sum(s) for s in S)<=K:
    print(0)
else:
    answer = (H-1) * (W-1)
    for X in product([False,True], repeat=H-1):
        ans = np.sum(X)
        if ans >= answer:
            continue
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])
            M[-1].append(i+1)
        D = np.array([0]*len(M))
        for s in S:
            D[:] += [sum(s[i] for i in m) for m in M]
            if any(d > K  for d in D):
                ans += 1
                if ans >= answer:
                    break
                D[:] = [sum(s[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