Код Python не работает

Question

Следующий код не работает. бросая исключение и не создавая выхода.

Ограничения на входе: 1 < = n < = 1000, 1 < = k < = n и s.length равно n. Также гарантируется, что вход в точности соответствует указанному.

Кроме того, код работает, когда 1 < = n < = 20.

def conforms(k,s): 
    k = k + 1 
    if s.find("0" * k) == -1 and s.find("1" * k) == -1: 
     return True 
    else: 
     return False 


def brute(n,k,s): 
    min_val = n + 1 
    min_str = "" 
    desired = long(s,2) 
    for i in range (2 ** n): 
     xor = desired^i # gives number of bit changes 
     i_rep = bin(i)[2:].zfill(n) # pad the binary representation with 0s - for conforms() 
     one_count = bin(xor).count('1') 
     if one_count < min_val and conforms(k, i_rep): 
      min_val = bin(xor).count('1') 
      min_str = i_rep 

    return (min_val,min_str) 

T = input() 
for i in range(T): 
    words = raw_input().split() 
    start = raw_input() 
    sol = brute(int(words[0]), int(words[1]), start) 
    print sol[0] 
    print sol[1] 

Answer 1

Дело в том, что range и xrange написаны на языке С, поэтому они склонны к переполнению. Вам нужно написать свой собственный генератор чисел, чтобы превзойти предел C long.

def my_range(end): 
    start = 0 
    while start < end: 
     yield start 
     start +=1 


def conforms(k,s): 
    k = k + 1 
    if s.find("0" * k) == -1 and s.find("1" * k) == -1: 
     return True 
    else: 
     return False 


def brute(n,k,s): 
    min_val = n + 1 
    min_str = "" 
    desired = long(s,2) 
    for i in my_range(2 ** n): 
     xor = desired^i # gives number of bit changes 
     i_rep = bin(i)[2:].zfill(n) # pad the binary representation with 0s - for conforms() 
     one_count = bin(xor).count('1') 
     if one_count < min_val and conforms(k, i_rep): 
      min_val = bin(xor).count('1') 
      min_str = i_rep 
    return (min_val,min_str) 


T = 1 
for i in range(T): 
    words = [100, 1] 
    start = '00000001' 
    sol = brute(words[0], words[1], start) 
    print sol[0] 
    print sol[1]