Problem p02609 (python)

Fixed submission:
import sys
read = sys.stdin.read
from collections import defaultdict
def main():
    n = int(input())
    x = list(input())
    # 0除算よけ。
    if n == 1:
        if x[0] == '1':
            print(0)
        else:
            print(1)
        sys.exit()
    # xの10進数換算と１の数カウント。
    x10 = int("".join(x), 2)
    xcount1 = x.count('1')
    # 2**i(mod 1の数)をケースごとに用意する。
    mod2plus = [0] * n
    mod2plus[0] = (1 % (xcount1+1)) # 必ず1になる。xcount1=0はありえない。
    for j1 in range(1, n):
        mod2plus[j1] = (mod2plus[j1 - 1] * 2) % (xcount1+1)
    mod2minus = [0] * n
    if xcount1 > 1:
        mod2minus[0] = 1
        for j1 in range(1, n):
            mod2minus[j1] = (mod2minus[j1 - 1] * 2) % (xcount1-1)
    # x(mod 1の数)をケースごとに用意する。
    modx_plus = x10 % (xcount1 + 1)
    if xcount1 == 1:
        modx_minus = 0
    else:
        modx_minus = x10 % (xcount1 - 1)
    popcount = defaultdict(int)
    for i1 in range(n):
        if x[i1] == '1':
            if xcount1 == 1:
                print(0)
                continue
            else:
                x3 = modx_minus - mod2minus[n - 1 - i1]
                if x3 < 0:
                    x3 += (xcount1 - 1)
                elif x3 > (xcount1 - 1):
                    x3 -= (xcount1 - 1)
                elif x3 == (xcount1 - 1):
                    print(1)
                    continue
        else:
            x3 = modx_plus + mod2plus[n - 1 - i1]
            if x3 < 0:
                x3 += (xcount1 + 1)
            elif x3 > (xcount1 + 1):
                x3 -= (xcount1 + 1)
            elif x3 == (xcount1 + 1):
                print(1)
                continue
        r = 1
        while x3:
            r += 1
            if popcount[x3] == 0:
                p = bin(x3).count('1')
                popcount[x3] = p
                x3 = x3 % p
            else:
                x3 = x3 % popcount[x3]
        print(r)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import defaultdict

def main():
    def from10to2(p):
        res = []
        while p:
            p, t = divmod(p, 2)
            res.append(str(t))
        return "".join(res[::-1])

    def from2to10(p):
        res = 0
        num2 = 1
        for c in p[::-1]:
            if c == '1':
                res += num2
            num2 *= 2
        return res

    def f(p):
        if p == 0:
            return 0
        elif d1[p] > 0:
            return d1[p]
        else:
            ppop = from10to2(p).count('1')
            p2 = p % ppop
            fp = f(p2) + 1
            d1[p] = fp
            return fp

    n = int(input())
    x = list(input())

    numof1 = x.count('1')
    bin2_p = [0] * n
    num2 = 1
    for i1 in range(1, n+1):
        bin2_p[-i1] = num2
        num2 = (num2 * 2) % (numof1 + 1)

    bin2_m = [0] * n
    num2 = 1
    if numof1 == 1:
        pass
    else:
        for i1 in range(1, n+1):
            bin2_m[-i1] = num2
            num2 = (num2 * 2) % (numof1 - 1)

    xas10 = from2to10(x)
    xas10_p = xas10 % (numof1 + 1)
    if numof1 == 1:
        xas10_m = 0
    else:
        xas10_m = xas10 % (numof1 - 1)
    d1 = defaultdict(int)
    d1[0] = 0
    for j1 in range(n):
        if x[j1] == '1':
            t0 = xas10_m - bin2_m[j1]
            t0 = t0 % (numof1 - 1)
            if t0 == 0:
                print(1)
            else:
                print(f(t0) + 1)
        else:
            t0 = xas10_p + bin2_p[j1]
            t0 = t0 % (numof1 + 1)
            if t0 == 0:
                print(1)
            else:
                print(f(t0) + 1)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import defaultdict

def main():
    def from10to2(p):
        res = []
        while p:
            p, t = divmod(p, 2)
            res.append(str(t))
        return "".join(res[::-1])

    def from2to10(p):
        res = 0
        num2 = 1
        for c in p[::-1]:
            if c == '1':
                res += num2
            num2 *= 2
        return res

    def f(p):
        if p == 0:
            return 0
        elif d1[p] > 0:
            return d1[p]
        else:
            ppop = from10to2(p).count('1')
            p2 = p % ppop
            fp = f(p2) + 1
            d1[p] = fp
            return fp

    n = int(input())
    x = list(input())

    numof1 = x.count('1')
    bin2_p = [0] * n
    num2 = 1
    for i1 in range(1, n+1):
        bin2_p[-i1] = num2
        num2 = (num2 * 2) % (numof1 + 1)

    bin2_m = [0] * n
    num2 = 1
    for i1 in range(1, n+1):
        bin2_m[-i1] = num2
        num2 = (num2 * 2) % (numof1 - 1)

    xas10 = from2to10(x)
    xas10_p = xas10 % (numof1 + 1)
    xas10_m = xas10 % (numof1 - 1)
    d1 = defaultdict(int)
    d1[0] = 0
    for j1 in range(n):
        if x[j1] == '1':
            t0 = xas10_m - bin2_m[j1]
            t0 = t0 % (numof1 - 1)
            if t0 == 0:
                print(1)
            else:
                print(f(t0) + 1)
        else:
            t0 = xas10_p + bin2_p[j1]
            t0 = t0 % (numof1 + 1)
            if t0 == 0:
                print(1)
            else:
                print(f(t0) + 1)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import defaultdict

def main():
    def from10to2(p):
        res = []
        while p:
            p, t = divmod(p, 2)
            res.append(str(t))
        return "".join(res[::-1])

    def from2to10(p):
        res = 0
        num2 = 1
        for c in p[::-1]:
            if c == '1':
                res += num2
            num2 *= 2
        return res

    def f(p):
        if p == 0:
            return 0
        elif d1[p] > 0:
            return d1[p]
        else:
            ppop = from10to2(p).count('1')
            p2 = p % ppop
            fp = f(p2) + 1
            d1[p] = fp
            return fp

    n = int(input())
    x = list(input())

    numof1 = x.count('1')
    bin2_p = [0] * n
    num2 = 1
    for i1 in range(1, n+1):
        bin2_p[-i1] = num2
        num2 = (num2 * 2) % (numof1 + 1)

    bin2_m = [0] * n
    num2 = 1
    for i1 in range(1, n+1):
        bin2_m[-i1] = num2
        num2 = (num2 * 2) % (numof1 - 1)

    xas10 = from2to10(x)
    xas10_p = xas10 % (numof1 + 1)
    xas10_m = xas10 % (numof1 - 1)
    d1 = defaultdict(int)
    d1[0] = 0
    for j1 in range(n):

        if x[j1] == '1':
            t0 = xas10_m - bin2_m[j1]
            if t0 < 0:
                t0 += bin2_m[j1]
            print(f(t0) + 1)
        else:
            t0 = xas10_p + bin2_p[j1]
            t0 = t0 % (numof1 + 1)
            print(f(t0) + 1)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import defaultdict

def main():
    def from10to2(p):
        res = []
        while p:
            p, t = divmod(p, 2)
            res.append(str(t))
        return "".join(res[::-1])

    def from2to10(p):
        res = 0
        num2 = 1
        for c in p[::-1]:
            if c == '1':
                res += num2
            num2 *= 2
        return res

    def f(p):
        if p == 0:
            return 0
        elif d1[p] > 0:
            return d1[p]
        else:
            ppop = from10to2(p).count('1')
            p2 = p % ppop
            fp = f(p2) + 1
            d1[p] = fp
            return fp

    n = int(input())
    x = list(input())

    numof1 = x.count('1')
    bin2 = [0] * n
    num2 = 1
    for i1 in range(1, n+1):
        bin2[-i1] = num2
        num2 = (num2 * 2) % numof1

    xas10 = from2to10(x)
    xas10 = xas10 % numof1
    d1 = defaultdict(int)
    d1[0] = 0
    for j1 in range(n):
        if x[j1] == '1':
            print(f(xas10 - bin2[j1]) + 1)
        else:
            print(f(xas10 + bin2[j1]) + 1)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import defaultdict

def main():
    def from10to2(p):
        res = []
        while p:
            p, t = divmod(p, 2)
            res.append(str(t))
        return "".join(res[::-1])

    def from2to10(p):
        res = 0
        num2 = 1
        for c in p[::-1]:
            if c == '1':
                res += num2
            num2 *= 2
        return res

    def f(p):
        if p == 0:
            return 0
        elif d1[p] > 0:
            return d1[p]
        else:
            ppop = from10to2(p).count('1')
            p2 = p % ppop
            fp = f(p2) + 1
            d1[p] = fp
            return fp

    n = int(input())
    x = list(input())

    bin2 = [0] * n
    num2 = 1
    for i1 in range(1, n+1):
        bin2[-i1] = num2
        num2 *= 2
    numof1 = x.count('1')
    xas10 = from2to10(x)
    d1 = defaultdict(int)
    d1[0] = 0
    for j1 in range(n):
        if x[j1] == '1':
            print(f((xas10 - bin2[j1]) % (numof1 - 1)) + 1)
        else:
            print(f((xas10 + bin2[j1]) % (numof1 + 1)) + 1)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.read
from collections import defaultdict
def main():
    n = int(input())
    x = list(input())
    # n=1だと0除算ありえるため対処。
    if n == 1:
        if x[0] == '1':
            print(0)
        else:
            print(1)
        sys.exit()
    # xの10進数換算と１の数カウント。
    x10 = int("".join(x), 2)
    xcount1 = x.count('1')
    # 2**i(mod 1の数)をケースごとに用意する。
    mod2plus = [0] * n
    mod2plus[0] = (1 % (xcount1+1))
    mod2plus[1] = (2 % (xcount1+1))
    for j1 in range(2, n):
        mod2plus[j1] = (mod2plus[j1 - 1] * 2) % (xcount1+1)
    mod2minus = [0] * n
    mod2minus[0] = (1 % (xcount1-1))
    mod2minus[1] = (2 % (xcount1-1))
    for j1 in range(2, n):
        mod2minus[j1] = (mod2minus[j1 - 1] * 2) % (xcount1-1)
    # x(mod 1の数)をケースごとに用意する。
    modx_plus = x10 % (xcount1 + 1)
    if xcount1 == 1:
        modx_minus = x10
    else:
        modx_minus = x10 % (xcount1 - 1)
    memo = defaultdict(int)
    for i1 in range(n):
        if x[i1] == '1':
            if xcount1 == 1:
                print(0)
                continue
            else:
                x3 = modx_minus - mod2minus[n - 1 - i1]
                if x3 < 0:
                    x3 += (xcount1 - 1)
                elif x3 > (xcount1 - 1):
                    x3 -= (xcount1 - 1)
                elif x3 == (xcount1 - 1):
                    x3 = 0
        else:
            x3 = modx_plus + mod2plus[n - 1 - i1]
            if x3 < 0:
                x3 += (xcount1 + 1)
            elif x3 > (xcount1 + 1):
                x3 -= (xcount1 + 1)
            elif x3 == (xcount1 + 1):
                x3 = 0
        r = 1
        while x3:
            r += 1
            if memo[x3] == 0:
                p = bin(x3).count('1')
                if p == 0:
                    break
                else:
                    memo[x3] = p
                    x3 = x3 % p
            else:
                x3 = x3 % memo[x3]
        print(r)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.read
from collections import defaultdict
def main():
    n = int(input())
    x = list(input())
    if n == 1:
        if x[0] == '1':
            print(0)
        else:
            print(1)
        sys.exit()

    x10 = int("".join(x), 2)
    xcount1 = x.count('1')
    mod2plus = [0] * n
    mod2plus[0] = (1 % (xcount1+1))
    mod2plus[1] = (2 % (xcount1+1))
    for j1 in range(2, n):
        mod2plus[j1] = (mod2plus[j1 - 1] * 2) % (xcount1+1)
    mod2minus = [0] * n
    mod2minus[0] = (1 % (xcount1-1))
    mod2minus[1] = (2 % (xcount1-1))
    for j1 in range(2, n):
        mod2minus[j1] = (mod2minus[j1 - 1] * 2) % (xcount1-1)
    modx_plus = x10 % (xcount1 + 1)
    if xcount1 == 1:
        modx_minus = x10
    else:
        modx_minus = x10 % (xcount1 - 1)
    memo = defaultdict(int)
    for i1 in range(n):
        if x[i1] == '1':
            if xcount1 == 1:
                print(0)
                continue
            else:
                x3 = modx_minus - mod2minus[n - 1 - i1]
                if x3 < 0:
                    x3 += (xcount1 - 1)
                elif x3 > (xcount1 - 1):
                    x3 -= (xcount1 - 1)
                elif x3 == (xcount1 - 1):
                    x3 = 0
        else:
            x3 = modx_plus + mod2plus[n - 1 - i1]
            if x3 < 0:
                x3 += (xcount1 + 1)
            elif x3 > (xcount1 + 1):
                x3 -= (xcount1 + 1)
            elif x3 == (xcount1 + 1):
                x3 = 0
        r = 1
        while x3:
            r += 1
            if memo[x3] == 0:
                p = bin(x3).count('1')
                memo[x3] = p
                x3 = x3 % p
            else:
                x3 = x3 % memo[x3]
        print(r)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.read
from collections import defaultdict
def main():
    n = int(input())
    x = list(input())
    if n == 1:
        print(0)
        sys.exit()
    x10 = int("".join(x), 2)
    xcount1 = x.count('1')
    mod2plus = [0] * n
    mod2plus[0] = (1 % (xcount1+1))
    mod2plus[1] = (2 % (xcount1+1))
    for j1 in range(2, n):
        mod2plus[j1] = (mod2plus[j1 - 1] * 2) % (xcount1+1)
    mod2minus = [0] * n
    mod2minus[0] = (1 % (xcount1-1))
    mod2minus[1] = (2 % (xcount1-1))
    for j1 in range(2, n):
        mod2minus[j1] = (mod2minus[j1 - 1] * 2) % (xcount1-1)
    modx_plus = x10 % (xcount1 + 1)
    if xcount1 == 1:
        modx_minus = x10
    else:
        modx_minus = x10 % (xcount1 - 1)
    memo = defaultdict(int)
    for i1 in range(n):
        if x[i1] == '1':
            if xcount1 == 1:
                print(0)
                continue
            else:
                x3 = modx_minus - mod2minus[n - 1 - i1]
                if x3 < 0:
                    x3 += (xcount1 - 1)
                elif x3 > (xcount1 - 1):
                    x3 -= (xcount1 - 1)
                elif x3 == (xcount1 - 1):
                    x3 = 0
        else:
            x3 = modx_plus + mod2plus[n - 1 - i1]
            if x3 < 0:
                x3 += (xcount1 + 1)
            elif x3 > (xcount1 + 1):
                x3 -= (xcount1 + 1)
            elif x3 == (xcount1 + 1):
                x3 = 0
        r = 1
        while x3:
            r += 1
            if memo[x3] == 0:
                p = bin(x3).count('1')
                memo[x3] = p
                x3 = x3 % p
            else:
                x3 = x3 % memo[x3]
        print(r)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.read
from collections import defaultdict
def main():
    n = int(input())
    x = list(input())
    if n == 1:
        print(0)
        sys.exit()
    x10 = int("".join(x), 2)
    xcount1 = x.count('1')
    mod2plus = [0] * n
    mod2plus[0] = (1 % (xcount1+1))
    mod2plus[1] = (2 % (xcount1+1))
    for j1 in range(2, n):
        mod2plus[j1] = (mod2plus[j1 - 1] * 2) % (xcount1+1)
    mod2minus = [0] * n
    mod2minus[0] = (1 % (xcount1-1))
    mod2minus[1] = (2 % (xcount1-1))
    for j1 in range(2, n):
        mod2minus[j1] = (mod2minus[j1 - 1] * 2) % (xcount1-1)
    modx_plus = x10 % (xcount1 + 1)
    if xcount1 == 1:
        modx_minus = x10
    else:
        modx_minus = x10 % (xcount1 - 1)
    memo = defaultdict(int)
    for i1 in range(n):
        if x[i1] == '1':
            if xcount1 == 1:
                print(0)
                continue
            else:
                x3 = modx_minus - mod2minus[i1]
                if x3 < 0:
                    x3 += (xcount1 - 1)
                elif x3 > (xcount1 - 1):
                    x3 -= (xcount1 - 1)
                elif x3 == (xcount1 - 1):
                    x3 = 0
        else:
            x3 = modx_plus + mod2plus[i1]
            if x3 < 0:
                x3 += (xcount1 + 1)
            elif x3 > (xcount1 + 1):
                x3 -= (xcount1 + 1)
            elif x3 == (xcount1 + 1):
                x3 = 0
        r = 1
        while x3:
            r += 1
            if memo[x3] == 0:
                p = bin(x3).count('1')
                memo[x3] = p
                x3 = x3 % p
            else:
                x3 = x3 % memo[x3]
        print(r)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.read
from collections import defaultdict
def main():
    n = int(input())
    x = list(input())
    if n == 1:
        print(0)
        sys.exit()

    x10 = int("".join(x), 2)
    xcount1 = x.count('1')
    modx_plus = x10 % (xcount1 + 1)
    modx_minus = x10 % (xcount1 - 1)
    memo = defaultdict(int)
    for i1 in range(n):
        if x[i1] == '1':
            mod_e = (pow(2, (n - 1 - i1)) % (xcount1 - 1))
            x3 = modx_minus - mod_e
            if x3 < 0:
                x3 += (xcount1 - 1)
            elif x3 > (xcount1 - 1):
                x3 -= (xcount1 - 1)
            elif x3 == (xcount1 - 1):
                x3 = 0
        else:
            mod_e = (pow(2, (n - 1 - i1)) % (xcount1 + 1))
            x3 = modx_plus + mod_e
            if x3 < 0:
                x3 += (xcount1 + 1)
            elif x3 > (xcount1 + 1):
                x3 -= (xcount1 + 1)
            elif x3 == (xcount1 + 1):
                x3 = 0
        r = 1
        while x3:
            r += 1
            if memo[x3] == 0:
                p = bin(x3).count('1')
                memo[x3] = p
                x3 = x3 % p
            else:
                x3 = x3 % memo[x3]
        print(r)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.read
from collections import defaultdict
def main():
    n = int(input())
    x = list(input())
    x10 = int("".join(x), 2)
    xcount1 = x.count('1')
    modx_plus = x10 % (xcount1 + 1)
    modx_minus = x10 % (xcount1 - 1)
    memo = defaultdict(int)
    for i1 in range(n):
        if x[i1] == '1':
            mod_e = (pow(2, (n - 1 - i1)) % (xcount1 - 1))
            x3 = modx_minus - mod_e
            if x3 < 0:
                x3 += (xcount1 - 1)
            elif x3 > (xcount1 - 1):
                x3 -= (xcount1 - 1)
            elif x3 == (xcount1 - 1):
                x3 = 0
        else:
            mod_e = (pow(2, (n - 1 - i1)) % (xcount1 + 1))
            x3 = modx_plus + mod_e
            if x3 < 0:
                x3 += (xcount1 + 1)
            elif x3 > (xcount1 + 1):
                x3 -= (xcount1 + 1)
            elif x3 == (xcount1 + 1):
                x3 = 0
        r = 1
        while x3:
            r += 1
            if memo[x3] == 0:
                p = bin(x3).count('1')
                memo[x3] = p
                x3 = x3 % p
            else:
                x3 = x3 % memo[x3]
        print(r)

if __name__ == '__main__':
    main()