Problem p02609 (python)

Fixed submission:
N = int(input())
X_bin = input()
#N = 10**5
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_cnt == 0:
        return 0
    if next_int == 0:
        return 1
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
f_p = X_int % (X_cnt+1)
if X_cnt-1 == 0:
    f_m = 0
else:
    f_m = X_int % (X_cnt-1)
for i in range(N):
    if X_bin[i] == '1':
        next_cnt = X_cnt - 1
        if next_cnt == 0:
            next_int = 0
        else:
            next_int = f_m - pow(2, (N-i-1), next_cnt)  # マイナスでも正しく求まる？
    else:
        next_cnt = X_cnt + 1
        next_int = f_p + pow(2, (N-i-1), next_cnt)
    print(calc_ans(next_int, next_cnt))
    #calc_ans(next_cnt, next_cnt)

Buggy submission (verdict: Runtime Error):
N = int(input())
X_bin = input()
#N = 10**5
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 1
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
f_p = X_int % (X_cnt+1)
if X_cnt-1 == 0:
    f_m = 0
else:
    f_m = X_int % (X_cnt-1)
for i in range(N):
    if X_bin[i] == '1':
        next_cnt = X_cnt - 1
        next_int = f_m - pow(2, (N-i-1), next_cnt)  # マイナスでも正しく求まる？
    else:
        next_cnt = X_cnt + 1
        next_int = f_p + pow(2, (N-i-1), next_cnt)
    print(calc_ans(next_int, next_cnt))
    #calc_ans(next_cnt, next_cnt)

Buggy submission (verdict: Runtime Error):
N = int(input())
X_bin = input()
#N = 10**5
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    if next_int == 0:
        return 0
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 1
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
f_p = X_int % (X_cnt+1)
if X_cnt-1 == 0:
    f_m = 0
else:
    f_m = X_int % (X_cnt-1)
for i in range(N):
    if X_bin[i] == '1':
        next_int = f_m - (2**(N-i-1))  # マイナスでも正しく求まる？
        next_cnt = X_cnt - 1
    else:
        next_int = f_p + (2**(N-i-1))
        next_cnt = X_cnt + 1
    print(calc_ans(next_int, next_cnt))
    #calc_ans(next_cnt, next_cnt)

Buggy submission (verdict: Runtime Error):
import math


N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    '''
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    '''
    cnt = 0
    n = int(math.log2(next_int))
    for i in range(n, -1, -1):
        if next_int >= 2**i:
            next_int -= 2**i
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Buggy submission (verdict: Runtime Error):
N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    '''
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    '''
    cnt = bin(next_int).count(1)
    return cnt


def calc_ans(next_int, cnt=None):
    if next_int == 0:
        return 0
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Buggy submission (verdict: Runtime Error):
N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Buggy submission (verdict: Runtime Error):
N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int


def calc_bin_cnt(next_int):
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    return ans


X_cnt = calc_bin_cnt(X_int)
for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Buggy submission (verdict: Runtime Error):
N = int(input())
X_bin = input()
#N = 2 * 10**4
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int
# popcount
X_cnt = 0
for i in X_bin:
    if i == '1':
        X_cnt += 1
dp = {0: 0, 1: 1}
bin_cnt = {}


def calc_bin_cnt(next_int):
    #if next_int in bin_cnt.keys():
    #    cnt = bin_cnt[next_int]
    #else:
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    key = next_int
    #if key in dp.keys():
    #    ans = dp[key]
    #else:
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    #else:
    #    bin_cnt[key] = cnt
    #bin_cnt[next_int] = cnt
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    #dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Buggy submission (verdict: Runtime Error):
N = int(input())
X_bin = input()
#N = 2 * 10**4
#X_bin = '1' * N

X_int = int(X_bin, 2)  # bin => int
# popcount
X_cnt = 0
for i in X_bin:
    if i == '1':
        X_cnt += 1
dp = {0: 0, 1: 1}
bin_cnt = {}


def calc_bin_cnt(next_int):
    #if next_int in bin_cnt.keys():
    #    cnt = bin_cnt[next_int]
    #else:
    next_bin = bin(next_int)[2:]
    # popcount
    cnt = 0
    for i in next_bin:
        if i == '1':
            cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    key = next_int
    #if key in dp.keys():
    #    ans = dp[key]
    #else:
    if cnt is None:
        cnt = calc_bin_cnt(next_int)
    #else:
    #    bin_cnt[key] = cnt
    #bin_cnt[next_int] = cnt
    next_int = next_int % cnt
    if next_int > 0:
        ans = calc_ans(next_int) + 1
    else:
        ans = 1
    #dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Buggy submission (verdict: Runtime Error):
import sys


N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int
# popcount
X_cnt = 0
for i in X_bin:
    if i == '1':
        X_cnt += 1
dp = {1: 1}
bin_cnt = {}

sys.setrecursionlimit(10**5)


def calc_bin_cnt(next_int):
    if next_int in bin_cnt.keys():
        cnt = bin_cnt[next_int]
    else:
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
    return cnt


def calc_ans(next_int, cnt=None):
    key = next_int
    if key in dp.keys():
        ans = dp[key]
    else:
        if cnt is None:
            cnt = calc_bin_cnt(next_int)
        else:
            bin_cnt[key] = cnt
        bin_cnt[next_int] = cnt
        next_int = next_int % cnt
        if next_int > 0:
            ans = calc_ans(next_int) + 1
        else:
            ans = 1
        dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))

Buggy submission (verdict: Runtime Error):
N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int
dp = {1: 1}
bin_cnt = {}

import sys
sys.setrecursionlimit(10**5)


def calc_bin_cnt(next_int):
    if next_int in bin_cnt.keys():
        cnt = bin_cnt[next_int]
    else:
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        bin_cnt[next_int] = cnt
    return cnt


def calc_ans(next_int):
    key = next_int
    if key in dp.keys():
        ans = dp[key]
    else:
        '''
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        '''
        cnt = calc_bin_cnt(next_int)
        bin_cnt[next_int] = cnt
        next_int = next_int % cnt
        if next_int > 0:
            ans = calc_ans(next_int) + 1
        else:
            ans = 1
        dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1))))
    else:
        print(calc_ans(X_int + (2**(N-i-1))))

Buggy submission (verdict: Runtime Error):
N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int
dp = {1: 1}
bin_cnt = {}


def calc_bin_cnt(next_int):
    if next_int in bin_cnt.keys():
        cnt = bin_cnt[next_int]
    else:
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        bin_cnt[next_int] = cnt
    return cnt


def calc_ans(next_int):
    key = next_int
    if key in dp.keys():
        ans = dp[key]
    else:
        '''
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        '''
        cnt = calc_bin_cnt(next_int)
        bin_cnt[next_int] = cnt
        next_int = next_int % cnt
        if next_int > 0:
            ans = calc_ans(next_int) + 1
        else:
            ans = 1
        dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1))))
    else:
        print(calc_ans(X_int + (2**(N-i-1))))

Buggy submission (verdict: Runtime Error):
N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int
dp = {1: 1}
bin_cnt = {}


def calc_bin_cnt(next_int):
    print('calc_bin')
    if next_int in bin_cnt.keys():
        print('bin dp')
        cnt = bin_cnt[next_int]
    else:
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        bin_cnt[next_int] = cnt
    return cnt


def calc_ans(next_int):
    key = next_int
    if key in dp.keys():
        print('dp')
        ans = dp[key]
    else:
        '''
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        '''
        cnt = calc_bin_cnt(next_int)
        bin_cnt[next_int] = cnt
        next_int = next_int % cnt
        if next_int > 0:
            ans = calc_ans(next_int) + 1
        else:
            ans = 1
        dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1))))
    else:
        print(calc_ans(X_int + (2**(N-i-1))))

Buggy submission (verdict: Runtime Error):
N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int
dp = {1: 1}
bin_cnt = {}


def calc_bin_cnt(next_int):
    if next_int in bin_cnt.keys():
        cnt = bin_cnt[next_int]
    else:
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        bin_cnt[next_int] = cnt
    return cnt


def calc_ans(next_int):
    key = next_int
    if key in dp.keys():
        ans = dp[key]
    else:
        '''
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        '''
        cnt = calc_bin_cnt(next_int)
        next_int = next_int % cnt
        if next_int > 0:
            ans = calc_ans(next_int) + 1
        else:
            ans = 1
        dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1))))
    else:
        print(calc_ans(X_int + (2**(N-i-1))))

Buggy submission (verdict: Runtime Error):
N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int
dp = {1: 1}


def calc_ans(next_int):
    key = next_int
    if key in dp.keys():
        ans = dp[key]
    else:
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        next_int = next_int % cnt
        if next_int > 0:
            ans = calc_ans(next_int) + 1
        else:
            ans = 1
        dp[key] = ans
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1))))
    else:
        print(calc_ans(X_int + (2**(N-i-1))))

Buggy submission (verdict: Runtime Error):
N = int(input())
X_bin = input()

X_int = int(X_bin, 2)  # bin => int

# popcount
X_cnt = 0
for i in X_bin:
    if i == '1':
        X_cnt += 1


def calc_ans(next_int, cnt):
    next_int = next_int % cnt
    ans = 1
    while next_int > 0:
        next_bin = format(next_int, 'b')
        # popcount
        cnt = 0
        for i in next_bin:
            if i == '1':
                cnt += 1
        next_int = next_int % cnt
        next_bin = format(next_int, 'b')
        ans += 1
    return ans


for i in range(N):
    if X_bin[i] == '1':
        print(calc_ans(X_int - (2**(N-i-1)), X_cnt-1))
    else:
        print(calc_ans(X_int + (2**(N-i-1)), X_cnt+1))