Problem p02609 (python)

Fixed submission:
def popcount(x):
    return bin(x).count("1")

n=int(input())
s=input()
X=int(s,2)

one_cnt=popcount(X)

modp=X%(one_cnt+1)
modm=X%(one_cnt-1) if one_cnt-1!=0 else 0

for i in range(n):
    if s[i]=="1":
        if one_cnt-1==0:
            print(0)
            continue
        else:
            num=(modm-pow(2,n-i-1,one_cnt-1))%(one_cnt-1)
    else:
        num=(modp+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)

    #print(i,"num",num)
    cnt=1
    while num!=0:
        num=num%popcount(num)
        cnt+=1
    print(cnt)

Buggy submission (verdict: Runtime Error):
def popcount(x):
    return bin(x).count("1")

n=int(input())
s=input()
X=int(s,2)



one_cnt=popcount(X)

modp=X%(one_cnt+1)
modm=X%(one_cnt-1) if one_cnt-1!=0 else 0

for i in range(n):
    if s[i]=="1":
        if cnt==1:
            print(0)
            continue
        else:
            num=(modm-pow(2,n-i-1,one_cnt-1))%(one_cnt-1)
    else:
        num=(modp+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)


    cnt=1
    while num!=0:
        num=num%popcount(num)
        cnt+=1
    print(cnt)

Buggy submission (verdict: Runtime Error):
n=int(input())

s=input()
X=int(s,2)

def popcount(x):
    return bin(x).count("1")

one_cnt=popcount(X)

modp=X%(one_cnt+1)
modm=X%(one_cnt-1) if cnt-1!=0 else 0

for i in range(n):
    if s[i]==1:
        if cnt==1:
            print(0)
            continue
        else:
            num=(modm-pow(2,n-i-1,one_cnt-1))%(one_cnt-1)
    else:
        num=(modp+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)

    if num==0:
        print(1)
    else:
        cnt=1
        while 1:
            num=num%popcount(num)
            cnt+=1
            if num==0:
                print(cnt)
                break

Buggy submission (verdict: Runtime Error):
n=int(input())

s=input()
X=int(s,2)

def popcount(x):
    return bin(x).count("1")

one_cnt=popcount(X)

modp=X%(one_cnt+1)
modm=X%(one_cnt-1)

for i in range(n):
    if s[i]==1:
        num=(modm-pow(2,n-i-1,one_cnt-1))%(one_cnt-1)
    else:
        num=(modp+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)

    if num==0:
        print(1)
    else:
        cnt=1
        while 1:
            num=num%popcount(num)
            cnt+=1
            if num==0:
                print(cnt)
                break

Buggy submission (verdict: Runtime Error):
n=int(input())

s=input()
X=int(s,2)

one_cnt=s.count("1")

modp=[0]*n
modm=[0]*n

for i in range(n):
    modp[i]=(pow(2,(n-i-1),one_cnt+1)*int(s[i]))%(one_cnt+1)
    modm[i]=(pow(2,(n-i-1),one_cnt-1)*int(s[i]))%(one_cnt-1)

ans=[]
memo_one=[0]*(n+10)

#print(modp,modm)

for i in range(n):
    cnt=0
    mod=0

    for j in range(n):
        if s[i]=="1":
            if one_cnt-1==0:
                ans.append(0)
                break

            if i!=j:
                mod=(mod+modm[j])%(one_cnt-1)
        else:
            if i!=j:
                mod=(mod+modp[j])%(one_cnt+1)
            else:
                mod=(mod+2**(n-i-1))%(one_cnt+1)
    cnt=1

   # print(i,mod)

    if mod==0:
        ans.append(cnt)
    else:
        while 1:
            cnt+=1
            if memo_one[mod]!=0:
                mod=mod%(memo_one[mod])
            else:
                tmp=(bin(mod).count("1"))
                memo_one[mod]=tmp
                mod=mod%(tmp)
            if mod==0:
                ans.append(cnt)
                break
            #print(mod,one_cnt,s[i],cnt)




#print(ans_memo)

for item in ans:
    print(item)

Buggy submission (verdict: Runtime Error):
n=int(input())

s=input()
X=int(s,2)

one_cnt=s.count("1")

modp=[0]*n
modm=[0]*n

for i in range(n):
    modp[i]=(pow(2,(n-i-1),one_cnt+1)*int(s[i]))%(one_cnt+1)
    modm[i]=(pow(2,(n-i-1),one_cnt-1)*int(s[i]))%(one_cnt-1)

ans=[]
memo_one=[0]*(n+1)

#print(modp,modm)

for i in range(n):
    cnt=0
    mod=0

    for j in range(n):
        if s[i]=="1":
            if i!=j:
                mod=(mod+modm[j])%(one_cnt-1)
        else:
            if i!=j:
                mod=(mod+modp[j])%(one_cnt+1)
            else:
                mod=(mod+2**(n-i-1))%(one_cnt+1)
    cnt=1

   # print(i,mod)

    if mod==0:
        ans.append(cnt)
    else:
        while 1:
            cnt+=1
            if memo_one[mod]!=0:
                mod=mod%(memo_one[mod])
            else:
                tmp=(bin(mod).count("1"))
                memo_one[mod]=tmp
                mod=mod%(tmp)
            if mod==0:
                ans.append(cnt)
                break
            #print(mod,one_cnt,s[i],cnt)




#print(ans_memo)

for item in ans:
    print(item)

Buggy submission (verdict: Runtime Error):
n=int(input())

s=input()
X=int(s,2)

one_cnt=s.count("1")

modp=[0]*n
modm=[0]*n

for i in range(n):
    modp[i]=(pow(2,(n-i-1),one_cnt+1)*int(s[i]))%(one_cnt+1)
    modm[i]=(pow(2,(n-i-1),one_cnt-1)*int(s[i]))%(one_cnt-1)

ans=[]

#print(modp,modm)
memo_one=[-1]*(n+1)
for i in range(n):
    cnt=0
    mod=0

    for j in range(n):
        if s[i]=="1":
            if i!=j:
                mod=(mod+modm[j])%(one_cnt-1)
        else:
            if i!=j:
                mod=(mod+modp[j])%(one_cnt+1)
            else:
                mod=(mod+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)
    cnt=1

   # print(i,mod)

    if mod==0:
        ans.append(cnt)
    else:
        while 1:
            cnt+=1
            if memo_one[mod]==-1:
                tmp=bin(mod).count("1")
                mod=mod%(tmo)
                memo_one[mod]=tmp
            else:
                mod=mod%memo_one[mod]

            if mod==0:
                ans.append(cnt)
                break
            #print(mod,one_cnt,s[i],cnt)




#print(ans_memo)

for item in ans:
    print(item)

Buggy submission (verdict: Runtime Error):
n=int(input())

s=input()
X=int(s,2)

one_cnt=s.count("1")

modp=[0]*n
modm=[0]*n

for i in range(n):
    modp[i]=(pow(2,(n-i-1),one_cnt+1)*int(s[i]))%(one_cnt+1)
    modm[i]=(pow(2,(n-i-1),one_cnt-1)*int(s[i]))%(one_cnt-1)

ans=[]

#print(modp,modm)

for i in range(n):
    cnt=0
    mod=0

    for j in range(n):
        if s[i]=="1":
            if i!=j:
                mod=(mod+modm[j])%(one_cnt-1)
        else:
            if i!=j:
                mod=(mod+modp[j])%(one_cnt+1)
            else:
                mod=(mod+2**(n-i-1))%(one_cnt+1)
    cnt=1

   # print(i,mod)

    if mod==0:
        ans.append(cnt)
    else:
        while 1:
            cnt+=1
            mod=mod%(bin(mod).count("1"))
            if mod==0:
                ans.append(cnt)
                break
            #print(mod,one_cnt,s[i],cnt)




#print(ans_memo)

for item in ans:
    print(item)

Buggy submission (verdict: Runtime Error):
n=int(input())

s=input()
X=int(s,2)

one_cnt=s.count("1")

modp=[0]*n
modm=[0]*n

for i in range(n):
    modp[i]=(pow(2,(n-i-1),one_cnt+1)*int(s[i]))%(one_cnt+1)
    modm[i]=(pow(2,(n-i-1),one_cnt-1)*int(s[i]))%(one_cnt-1)

ans=[]

#print(modp,modm)

for i in range(n):
    cnt=0
    mod=0

    for j in range(n):
        if s[i]=="1":
            if i!=j:
                mod=(mod+modm[j])%(one_cnt-1)
        else:
            if i!=j:
                mod=(mod+modp[j])%(one_cnt+1)
            else:
                mod=(mod+2**(n-i-1))%(one_cnt+1)
    cnt=1

   # print(i,mod)

    if mod==0:
        ans.append(cnt)
    else:
        while 1:
            cnt+=1
            mod=mod%(bin(mod).count("1"))
            if mod==0:
                ans.append(cnt)
                break
            #print(mod,one_cnt,s[i],cnt)




#print(ans_memo)

for item in ans:
    print(item)

Buggy submission (verdict: Runtime Error):
import sys #追加


n=int(input())
sys.setrecursionlimit(10**6*2)

s=input()
X=int(s,2)

one_cnt=s.count("1")
modp1=X%(one_cnt+1)
modm1=X%(one_cnt-1)

ans=[]

ans_memo=[0]*(2*(10**5)+2)
#print(ans_memo)
ans_memo[1]=1
ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if x==0:
        return 0
    if x<2*(10**5)+1:    
        if ans_memo[x]!=0:
            return ans_memo[x]
        else:
            if x%(str(bin(x)).count("1"))==0:
                ans_memo[x]=1
                return 1
            else:
                tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
                ans_memo[x]=tmp
                return tmp
    else:
        if x%(str(bin(x)).count("1"))==0:
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            return tmp


ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=X
    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        if tmp_num==0:
            ans.append(0)
        else:
            
            tmp_num=(modm1-tmp%(one_cnt-1))
            if tmp_num<0:
                tmp_num+=(one_cnt-1)

            ans.append(DEF(tmp_num,1)+1)
        
    else:
        tmp_nunm=(tmp%(one_cnt+1)+modp1)%(one_cnt+1)
        #print(bin(tmp_num),n-i-1)
        #tmp_num=tmp_num%(one_cnt+1)
        ans.append(DEF(tmp_num,1)+1)

#print(ans_memo)

for item in ans:
    print(item)

Buggy submission (verdict: Runtime Error):
import sys #追加

n=int(input())
sys.setrecursionlimit(10**6*2)

s=input()
X=int(s,2)
ans=[]

ans_memo=[0]*(2**(n+2))
#print(ans_memo)
ans_memo[1]=1
ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if x==0:
        return 0    
    if ans_memo[x]!=0:
        return ans_memo[x]
    else:
        if x%(str(bin(x)).count("1"))==0:
            ans_memo[x]=1
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            ans_memo[x]=tmp
            return tmp

ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=X
    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))
        
    else:
        tmp_num+=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))

#print(ans_memo)

for item in ans:
    print(item)

Buggy submission (verdict: Runtime Error):
import sys #追加

n=int(input())
sys.setrecursionlimit(10**5*2)

s=input()
x=int(s,2)
ans=[]

ans_memo=[0]*(2**(n+1))
#print(ans_memo)
ans_memo[1]=1
ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if ans_memo[x]!=0:
        return ans_memo[x]
    if x==0:
        return 0    
    else:
        if x%(str(bin(x)).count("1"))==0:
            ans_memo[x]=1
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            ans_memo[x]=tmp
            return tmp

ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=x
    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))
        
    else:
        tmp_num+=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))

#print(ans_memo)

for item in ans:
    print(item)

Buggy submission (verdict: Runtime Error):
import sys #追加

n=int(input())
sys.setrecursionlimit(10**5*2)

s=input()
x=int(s,2)
ans=[]

ans_memo=[0]*(2**(n+1))
#print(ans_memo)
#ans_memo[1]=1
#ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if ans_memo[x]!=0:
        return ans_memo[x]
    else:
        if x%(str(bin(x)).count("1"))==0:
            ans_memo[x]=1
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            ans_memo[x]=tmp
            return tmp

ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=x

    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        ans.append(DEF(tmp_num,0))
        
    else:
        tmp_num+=tmp
        ans.append(DEF(tmp_num,0))

#print(ans_memo)

for item in ans:
    print(item)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)


n=int(input())

s=input()
x=int(s,2)
ans=[]

ans_memo=[0]*(2**(n+2))
#print(ans_memo)
#ans_memo[1]=1
#ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if ans_memo[x]!=0:
        return ans_memo[x]
    else:
        if x%(str(bin(x)).count("1"))==0:
            ans_memo[x]=1
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            ans_memo[x]=tmp
            return tmp

ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=x

    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        ans.append(DEF(tmp_num,0))
        
    else:
        tmp_num+=tmp
        ans.append(DEF(tmp_num,0))

#print(ans_memo)

for item in ans:
    print(item)

Buggy submission (verdict: Runtime Error):
n=int(input())

s=input()
x=int(s,2)
ans=[]

ans_memo=[0]*(2**(n+1))
#ans_memo[1]=1
#ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if ans_memo[x]!=0:
        return ans_memo[x]
    else:
        if x%(str(bin(x)).count("1"))==0:
            ans_memo[x]=1
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            ans_memo[x]=tmp
            return tmp

ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=x

    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        ans.append(DEF(tmp_num,0))
        
    else:
        tmp_num+=tmp
        ans.append(DEF(tmp_num,0))

#print(ans_memo)

for item in ans:
    print(item)