Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03760 (python)

Fixed submission:
s1=input()

s2=input()

ans = []

for i in range(len(s1)+len(s2)):
    if i%2==0:
        ans.append(s1[i//2])
    else:
        ans.append(s2[i//2])

print(''.join(map(str,ans)))

Buggy submission (verdict: Runtime Error):
a = list(input())
b = list(input())

ans = []

for i in range(len(a)):
    ans.append(a[i])
    if b[i]:
        ans.append(b[i])
print(''.join(ans))

Buggy submission (verdict: Runtime Error):
a = list(input())
b = list(input())

ans = []

for i in range(len(a)):
    ans.append(a[i])
    ans.append(b[i])
print(''.join(ans))
Problem p03818 (python)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
memo = {}
for a in A:
    if a in memo:
        memo[a] += 1
    else:
        memo[a] = 1
memo_sorted = sorted(memo.items(), key=lambda x:-x[1])
memo = []
for a,b in memo_sorted:
    memo.append([a,b])

for key,val in enumerate(memo):
    val_1, val_2 = val
    if val_2 <= 1:
        continue
    else:
        if val_2%2 == 1:
            memo[key][1] = 1
        elif val_2%2 == 0:
            if key < len(memo)-1:
                memo[key+1][1] -= 1
                memo[key][1] = 1
            else:
                memo[key][1] = 0
ans = 0
for a,b in memo:
    ans += b
print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int,input().split()))
memo = {}
for a in A:
    if a in memo:
        memo[a] += 1
    else:
        memo[a] = 1
memo_sorted = sorted(memo.items(), key=lambda x:-x[1])
memo = []
for a,b in memo_sorted:
    memo.append([a,b])

for key,val in enumerate(memo):
    val_1, val_2 = val
    if val_2 <= 1:
        continue
    else:
        if val_2%2 == 1:
            memo[key][1] = 1
        elif val_2%2 == 0:
            if key < N-1:
                memo[key+1][1] -= 1
            memo[key][1] = 1
ans = 0
for a,b in memo:
    ans += b
print(ans)
Problem p02658 (python)

Fixed submission:
def main():
    N = int(input())
    A = list(map(int,input().split()))
    if 0 in A:
      print(0)
      return
    prod = 1
    for a in A:
      prod *= a
      if prod > 1000000000000000000:
        print(-1)
        return
    print(prod)

main()

Buggy submission (verdict: Runtime Error):
def main():
N = int(input())
A = list(map(int,input().split()))
if 0 in A:
  print(0)
  return
prod = 1
for a in A:
  prod *= a
  if prod > 1000000000000000000:
    print(-1)
    return
print(prod)

main()

Buggy submission (verdict: Runtime Error):
N=int(input())
result=1
A=input().split()
for j in range(N):
  result=result*int(A[j])
  if(result>10**18):
    print(-1)
    return
print(result)

Buggy submission (verdict: Runtime Error):
N=int(input())
A=[]
result=1
for i in range(N):
  A.append(int(input().split()))
for j in range(N):
  result=result*A[j]
if(result>10**18):
  print(-1)
else:
  print(result)

Buggy submission (verdict: Runtime Error):
N=int(input())
A=[]
result=1
for i in range(N):
  A.append(int(input()))
for j in range(N):
  result=result*A[j]
if(result>10**18):
  print(-1)
else:
  print(result)
Problem p02681 (python)

Fixed submission:
S=input()
T=input()
if(T[:-1]==S):
  print("Yes")
else:
  print("No")

Buggy submission (verdict: Runtime Error):
S=input()
T=input()
T.pop(len(str))
if(T==S):
  print("Yes")
else:
  print("No")

Buggy submission (verdict: Runtime Error):
S=input()
T=input()
T.pop()
if(T==S):
  print("Yes")
else:
  print("No")
Problem p02812 (python)

Fixed submission:
count=0
N=input()
S=input()
N=int(N)
for i in range(N-2):
  if(S[i]=="A" and S[i+1]=="B" and S[i+2]=="C"):
    count+=1
print(count)

Buggy submission (verdict: Runtime Error):
count=0
N=input()
S=input()
N=int(N)
for i in range(N-2):
  if(S[i]=="A" and S[i+1]=="B" and S[i+2]=="C"):
    count++
print(count)
Problem p02922 (python)

Fixed submission:
A,B=map(int,input().split())
for i in range(B):
  if(i*A-i+1>=B):
    ans=i
    break
print(ans)

Buggy submission (verdict: Runtime Error):
A,B=map(int,input().split())
for i in range(B):
  if(i*A>=B):
    ans=i
    break
print(ans)
Problem p03106 (python)

Fixed submission:
A,B,K=map(int,input().split())
list=[]
for i in range(1,min(A,B)+1):
  if A%i==0 and B%i==0 :
    list.append(i)
print(list[len(list)-K])

Buggy submission (verdict: Runtime Error):
A,B,K=map(int,input().split())
list=[]
for i in range(1,min(A,B)+1):
  if A%i==0 and B%i==0 :
    list.append(i)
print(list[len(list)-K+1])

Buggy submission (verdict: Runtime Error):
A,B,K=map(int,input().split())
list=[]
for i in range(1,min(A,B)):
  if A%i==0 and B%i==0 :
    list.append(i)
print(list[len(list)-K+1])

Buggy submission (verdict: Runtime Error):
A,B,K=map(int,input().split())
list=[]
for i in range(1,min(A,B)):
  if A%i==0 and B%i==0 :
    list.append(i)
print(list[K-1])
Problem p03126 (python)

Fixed submission:
N,M=map(int,input().split())
KA=[0]*N
count=[0]*(M+1)
for i in range(N):
  KA[i]=list(map(int,input().split()))
for i in range(N):
  for j in range(1,len(KA[i])):
    count[KA[i][j]]+=1
ans=0
for i in range(1,M+1):
  if count[i]==N :
    ans+=1
print(ans)

Buggy submission (verdict: Runtime Error):
N,M=map(int,input().split())
A=[]*N
for i in ragne(N):
  A[i]=list(map(int,input().split()))
Problem p03155 (python)

Fixed submission:
N=int(input())
H=int(input())
W=int(input())
print((N-H+1)*(N-W+1))

Buggy submission (verdict: Runtime Error):
N,H,W=map(int,input().split())
print((N-H+1)*(N-W+1))
Problem p03206 (python)

Fixed submission:
D=int(input())
if D==25 :
  print("Christmas")
elif D==24 :
  print("Christmas Eve")
elif D==23 :
  print("Christmas Eve Eve")
else :
  print("Christmas Eve Eve Eve")

Buggy submission (verdict: Runtime Error):
D=int(input())
if D=25 :
  print("Christmas")
elif D=24 :
  print("Christmas Eve")
elif D=23 :
  print("Christmas Eve Eve")
else :
  print("Christmas Eve Eve Eve")
Problem p03239 (python)

Fixed submission:
N,T=map(int,input().split())
ct=[0]*N
cost=[]
for i in range(N):
  ct[i]=list(map(int,input().split()))
  if ct[i][1]<=T :
    cost.append(ct[i][0])
if cost==[] :
  print("TLE")
else :
  print(min(cost))

Buggy submission (verdict: Runtime Error):
N,T=map(int,input().split())
ct=[0]*N
cost=[]
for i in range(N):
  ct[i]=list(map(int,input().split()))
  if ct[i][1]<T :
    cost.append(ct[i][0])
print(min(cost))
Problem p03260 (python)

Fixed submission:
A,B=map(int,input().split())
if A*B%2==0 :
  print("No")
else :
  print("Yes")

Buggy submission (verdict: Runtime Error):
A,B=map(int,input())
if A*B%2==0 :
  print("No")
else :
  print("Yes")
Problem p03469 (python)

Fixed submission:
S=input()
print(S.replace("2017","2018"))

Buggy submission (verdict: Runtime Error):
S=input()
S[3]="8"
print(S)
Problem p03738 (python)

Fixed submission:
A=int(input())
B=int(input())
if A>B :
  print("GREATER")
elif A==B :
  print("EQUAL")
else :
  print("LESS")

Buggy submission (verdict: Runtime Error):
A,B=map(int,input().split())
if A>B :
  print("GREATER")
elif A==B :
  print("EQUAL")
else :
  print("LESS")
Problem p02579 (python)

Fixed submission:
from collections import deque
from itertools import product


def bfs(S):
    x, y = S
    dist = [[10 ** 9] * w for _ in range(h)]
    dist[y][x] = 0
    que = deque([S])

    while len(que) > 0:
        x, y = que.popleft()
        near_a = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        num = product([-2, -1, 0, 1, 2], repeat=2)
        near_b = [(x + dx, y + dy) for dx, dy in num]

        for i, j in near_a:
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > dist[y][x] and s[j][i] == '.'):
                dist[j][i] = dist[y][x]
                que.appendleft((i, j))
        for i, j in near_b:
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > dist[y][x] + 1 and s[j][i] == '.'):
                dist[j][i] = dist[y][x] + 1
                que.append((i, j))
    return dist


h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [input() for _ in range(h)]

ans = bfs((Cw - 1, Ch - 1))[Dh - 1][Dw - 1]
print(-1 if ans == 10 ** 9 else ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
from itertools import product


def bfs(x, y):
    dist = [[10 ** 9] * w for _ in range(h)]
    dist[y][x] = 0
    for i, si in enumerate(s):
        for j, sij in enumerate(si):
            if sij=='#':
                dist[j][i] = -1
    que = deque([(x, y)])

    while len(que) > 0:
        x, y = que.popleft()
        near_a = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        num = product([-2, -1, 0, 1, 2], repeat=2)
        near_b = [(x + dx, y + dy) for dx, dy in num]

        for cnt, l in enumerate((near_a, near_b)):
            for i, j in l:
                if (0 <= i < w and 0 <= j < h and
                        dist[j][i] > dist[y][x] + cnt and s[j][i] == '.'):
                    dist[j][i] = dist[y][x] + cnt
                    if cnt == 0:
                        que.appendleft((i, j))
                    elif cnt == 1:
                        que.append((i, j))
    return dist


h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [input() for _ in range(h)]

ans = bfs(Cw - 1, Ch - 1)[Dh - 1][Dw - 1]
print(-1 if ans == 10 ** 9 else ans)
Problem p02584 (python)

Fixed submission:
x, k, d = map(int, input().split())

cnt = abs(x) // d
x = abs(x)
if k % 2 == cnt % 2:
    ans = min(abs(x - d * min(k,cnt)), abs(x + d * min(k,cnt)))
elif k % 2 != cnt % 2:
    ans = min(abs(x - d * min(k,(cnt + 1))), abs(x - d * min(k,(cnt + 1))))
print(ans)

Buggy submission (verdict: Runtime Error):
x, k, d = map(int, input().split())

x, cnt = abs(x), abs(x) // d
if k % 2 == cnt % 2:
    ans = abs(x - d * min(k, cnt))
elif k % 2 != cnt % 2:
    ans = abs(x - d * min(k, cnt + 1)
print(ans)
Problem p02609 (python)

Fixed submission:
def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


n, x = int(input()), input()

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        ctmp = cnt - 1
        if ctmp == 0:
            print(0)
            continue
        tmp = num % ctmp - pow(2, n - (i + 1), ctmp)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

Buggy submission (verdict: Runtime Error):
def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


n, x = int(input()), input()

num, cnt = int(x, 2), x.count('1')
num0, num1 = num % (cnt + 1), num % max(cnt - 1, 1)
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        tmp = num0 + pow(2, n - (i + 1), cnt + 1)
    elif x[i] == '1':
        if cnt == 1:
            print(0)
            continue
        tmp = num1 - pow(2, n - (i + 1), cnt - 1)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

Buggy submission (verdict: Runtime Error):
def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


n, x = int(input()), input()

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = (num + pow(2, n - (i + 1), ctmp)) % ctmp
    elif x[i] == '1':
        ctmp = cnt - 1
        tmp = (num - pow(2, n - (i + 1), ctmp)) % ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

Buggy submission (verdict: Runtime Error):
def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


n, x = int(input()), input()

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = (num + pow(2, n - (i + 1), ctmp)) % ctmp
    elif x[i] == '1':
        ctmp = cnt - 1
        tmp = (num - pow(2, n - (i + 1), ctmp)) % ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)

Buggy submission (verdict: Runtime Error):
def bitcount(N):  # 立ってるbitの数
    bitcnt = [0]
    for _ in range(N):
        bitcnt += [i + 1 for i in bitcnt]
    return bitcnt


n, x = int(input()), input()

num, cnt = int(x, 2), x.count('1')
lbit = bitcount(18)
for i in range(n):
    ans = 1
    if x[i] == '0':
        ctmp = cnt + 1
        tmp = num % ctmp + pow(2, n - (i + 1), ctmp)
    elif x[i] == '1':
        ctmp = cnt - 1
        tmp = num % ctmp - pow(2, n - (i + 1), ctmp)
    tmp %= ctmp
    ctmp = lbit[tmp]
    while tmp > 0:
        ans += 1
        tmp %= ctmp
        ctmp = lbit[tmp]
    print(ans)
Problem p02615 (python)

Fixed submission:
from collections import deque

n = int(input())
a = sorted(map(int, input().split()), reverse=True)

ans, cnt = 0, deque([a[0]])
for i in a[1:]:
    ans += cnt.popleft()
    cnt.append(i)
    cnt.append(i)
print(ans)

Buggy submission (verdict: Runtime Error):
n = int(input())
a = sorted(map(int, input().split()), reverse=True)

ans, que = 0, [a[0]]
for i in enumerate(a[1:]):
    ans += que[i]
    que += [i, i]
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque

n = int(input())
a = sorted(map(int, input().split()), reverse=True)

ans, cnt = 0, deque([a[0]])
for i in a[1:]:
    ans += cnt.popleft()
    cnt.append(a[i])
    cnt.append(a[i])
print(ans)
Problem p02618 (python)

Fixed submission:
d = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(d)]

for i in range(d):
    print(1)

Buggy submission (verdict: Runtime Error):
d = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(d)]
t = [int(input()) for _ in range(d)]

last = [0] * 26
ans = 0
for di in range(d):
    ans += s[di][t[di] - 1]
    last[t[di] - 1] = di + 1
    ans -= sum(c[i] * (di + 1 - last[i]) for i in range(26))
    print(ans)
Problem p02647 (python)

Fixed submission:
from itertools import accumulate
from math import log2

n, k = map(int, input().split())
a = list(map(int, input().split()))

for j in range(k):
    a01 = [0] * (n + 1)
    for i, ai in enumerate(a):
        l, r = max(0, i - ai), min(i + ai + 1, n)
        a01[l] += 1
        a01[r] -= 1
    a = list(accumulate(a01))
    if all(ai == n for ai in a[:-1]):
        break
print(*a[:-1])

Buggy submission (verdict: Runtime Error):
from itertools import accumulate
from math import log2

n, k = map(int, input().split())
a = list(map(int, input().split()))

for j in range(k):
    a01 = [0] * (n + 1)
    for i, ai in enumerate(a):
        l, r = max(0, i - ai), min(i + ai + 1, n)
        a01[l] += 1
        a01[r] -= 1
    a = list(accumulate(a01))
    if all(ai == n for ai in ai[:-1]):
        break
print(*a[:-1])
Problem p02678 (python)

Fixed submission:
from collections import deque
import sys
input = sys.stdin.readline


def bfs(NEAR, S, N):  # 幅優先探索  # キュー
    pas = [-1 for _ in range(N)]
    pas[S] = 's'
    frag = set([S])
    que = deque([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:
            if i in frag:  # 処理済みか否か
                continue
            pas[i]=q
            que.append(i)
            frag.add(i)
    return pas


n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

near = [[] for _ in range(n)]
for a, b in ab:
    near[a - 1].append(b - 1)
    near[b - 1].append(a - 1)
pas = bfs(near, 0, n)

if all(pas[i] != -1 for i in range(n)):
    print('Yes')
    for i in range(1, n):
        print(pas[i] + 1)
else:
    print('No')

Buggy submission (verdict: Runtime Error):
def nearlist(N, LIST):
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


def dfs(NEAR, S, N):  # 深優先探索  # スタック
    dist = [n for _ in range(N)]  # 前処理
    PATH = [-1 for _ in range(N)]
    dist[S], PATH[S] = 0, 's'
    stack, frag = [S], set([S])

    while len(stack) > 0:
        q = stack.pop()
        for i in NEAR[q]:  # 移動先の候補
            if i != 0 and i in frag:
                dist[i] = dist[PATH[i]] + 1
            if dist[i] > dist[q] + 1:
                dist[i] = dist[q] + 1
                PATH[i] = q
            if i in frag:  # 処理済みか否か
                continue
            stack.append(i), frag.add(i)
        print(dist,PATH)
    return PATH


n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

near = nearlist(n, ab)
path = dfs(near, 0, n)

print('Yes')
for i in range(1, n):
    print(path[i] + 1)

Buggy submission (verdict: Runtime Error):
def nearlist(N, LIST):
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


def dfs(NEAR, S, N):  # 深優先探索  # スタック
    dist = [n for _ in range(N)]  # 前処理
    PATH = [-1 for _ in range(N)]
    dist[S], PATH[S] = 0, 's'
    stack, frag = [S], set([S])

    while len(stack) > 0:
        q = stack.pop()
        for i in NEAR[q]:  # 移動先の候補
            dist[i] = dist[PATH[i]] + 1
            if dist[i] > dist[q] + 1:
                dist[i] = dist[q] + 1
                PATH[i] = q
            if i in frag:  # 処理済みか否か
                continue
            stack.append(i), frag.add(i)
    return PATH


n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

near = nearlist(n, ab)
path = dfs(near, 0, n)

print('Yes')
for i in range(1, n):
    print(path[i] + 1)
Problem p02690 (python)

Fixed submission:
from itertools import combinations

x = int(input())
num = [i**5 for i in range(1000)]

for a, b in combinations(num, 2):
    if a - b == x:
        print(int(a**0.2), int(b**0.2))
    elif a + b == x:
        print(int(a**0.2), -int(b**0.2))
    elif b - a == x:
        print(int(b**0.2), int(a**0.2))
    elif b + a == x:
        print(int(b**0.2), -int(a**0.2))
    else:
        continue
    break

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

x = int(input())
num = [i**5 for i in range(-1000, 1000)]

for a, b in product(num, repeat=2):
    if a - b == x:
        print(int(a**0.2), int(b**0.2))
        break

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

x = int(input())

for a, b in product(list(range(-1000,1000)), repeat=2):
    if a - b == x:
        print(int(a**0.2), int(b**0.2))
        break
Problem p02702 (python)

Fixed submission:
s = str(input())

num = [int(s[-1])]
for i in range(1, len(s)):
    tmp = num[-1] + pow(10, i, 2019) * int(s[-i - 1])
    num.append(tmp % 2019)

mod = [1] + [0] * 2018
ans = 0
for i in num:
    m = i % 2019
    ans += mod[m]
    mod[m] += 1
print(ans)

Buggy submission (verdict: Runtime Error):
s = str(input())

num = [int(s[-1])]
for i in range(1, len(s)):
    tmp = num[-1] + pow(10, i, 2019) * int(s[-i - 1])
    num.append(tmp % 2019)

mod = [1] + [0] * 2018
ans = 0
for i in num:
    ans += mod[m]
    mod[m] += 1
print(ans)
Problem p02714 (python)

Fixed submission:
from itertools import product as pro

n = int(input())
s = str(input())

r = [i for i in range(n) if s[i] == 'R']
g = [i for i in range(n) if s[i] == 'G']
b = [i for i in range(n) if s[i] == 'B']
cnt = len(r)*len(g)*len(b)

length = max(len(r), len(g), len(b))
if length == len(r):
    max1 = set(r)
    min1 = g
    min2 = b

if length == len(g):
    max1 = set(g)
    min1 = r
    min2 = b

if length == len(b):
    max1 = set(b)
    min1 = g
    min2 = r

for i, j in pro(min1, min2):
    if 2*j-i in max1:
        cnt -= 1
    if 2*i-j in max1:
        cnt -= 1
    if (i+j)/2 in max1:
        cnt -= 1

print(cnt)

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

n = int(input())
s = str(input())

r = [i for i in range(n) if s[i] == 'R']
g = [i for i in range(n) if s[i] == 'G']
b = [i for i in range(n) if s[i] == 'B']
cnt = len(r)*len(g)*len(b)

len = max(len(r), len(g), len(b))
if len == len(r):
    max1 = set(r)
    min1 = g
    min2 = b

if len == len(g):
    max1 = set(g)
    min1 = r
    min2 = b

if len == len(b):
    max1 = set(b)
    min1 = g
    min2 = r

for i, j in pro(min1, min2):
    if 2*j-i in max1:
        cnt -= 1
    if 2*i-j in max1:
        cnt -= 1
    if (i+j)/2 in max1:
        cnt -= 1

print(cnt)
Problem p02733 (python)

Fixed submission:
from itertools import product


def makelist(BIT):
    LIST, tmp = [], s[0]
    for i, bi in enumerate(BIT, 1):
        if bi == 1:
            LIST.append(tmp)
            tmp = s[i]
        elif bi == 0:
            tmp = [p + q for p, q in zip(tmp, s[i])]
    else:
        LIST.append(tmp)
    return LIST


def solve(LIST):
    CNT, tmp = 0, [l[0] for l in LIST]
    if any(num > k for num in tmp):
        return h * w
    for i in range(1, w):
        cal = [tmp[j] + LIST[j][i] for j in range(len(LIST))]
        if any(num > k for num in cal):
            CNT += 1
            tmp = [l[i] for l in LIST]
        else:
            tmp = cal
    return CNT


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

ans = h * w
for bit in product([0, 1], repeat=(h - 1)):
    numlist = makelist(bit)
    ans = min(ans, solve(numlist) + sum(bit))
print(ans)

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


def makelist(BIT):
    LIST, tmp = [], s[0]
    for i, bi in enumerate(BIT, 1):
        if bi == 1:
            LIST.append(tmp)
            tmp = s[i]
        elif bi == 0:
            tmp = [p + q for p, q in zip(tmp, s[i])]
    else:
        LIST.append(tmp)
    return LIST


def solve(LIST):
    CNT, tmp = 0, [l[0] for l in LIST]
    for i in range(1, w):
        cal = [tmp[j] + LIST[j][i] for j in range(len(LIST))]
        if any(num > k for num in cal):
            CNT += 1
            tmp = [l[i] for l in LIST]
        else:
            tmp = cal
    return CNT


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

for bit in product([0, 1], repeat=(h - 1)):
    numlist = makelist(bit)
    ans = min(ans, solve(numlist) + sum(bit))
print(ans)