Строковый декодер не работает должным образом

Question

Я преобразовываю буквы в строку в соответствующие номера и печатаю ДА, если результат делится на 6 или НЕТ. Например, ab равен 12 и даст ДА. Программа отлично работает для небольших строк, но дает неправильный ответ на очень длинные входы. Я попытался изменить тип данных для целых чисел до конца, но ничего не изменилось.

Тестовый пример, для которого он не работал: here#1

Edit: ограничения ввода позволяют только символы нижнего регистра «а» до «Я» Оригинал проблемусвязь: https://www.hackerearth.com/problem/algorithm/encoded-strings-3/

str = raw_input() 
n = len(str) 
value = 0L 
str = str[::-1] 

for i in arange(n): 
    value = value*1L + (10L**i)*(ord(str[i])-96) 

if value%6 == 0: 
    print "YES" 
else: 
    print "NO" 

Answer 1

Проблема с кодом оказалась в том, что длинный int, возможно, недостаточно длинный, чтобы удерживать целочисленное значение строки, декодированное как заданное.

Таким образом, проблему можно упростить, применяя математические правила делимости.

Проверьте, соответствует ли соответствующая цифра для последней буквы строки. Если не напечатать «НЕТ» и выйти.

Затем проверьте делимость на 3, используя свойство делимости суммы.

Вот код.

#Title: String decoding and divisibility by 6 
    #Author: Rtg 
    #Date: 29-05-16 

    str = raw_input() 
    n = len(str) 

    if (ord(str[n-1])-96)%2: 
     print "NO" 
     raise SystemExit 

    value = 0 
    for i in xrange(n): 
     value = value + ord(str[i])-96 

    if value%3 == 0: 
     print "YES" 
    else: 
     print "NO" 

Answer 2

Ваш код кажется работать так же, как в «правильных тестах, делится ли число на 6», если на входе нет каких-либо дополнительных символов, таких как пробелы, CR, вкладка и т. д. Указанный вами URL-адрес не работает, поэтому я не мог увидеть тест с ошибкой.

Две основные ошибки в коде:

1) вы вычитая 96 - почему? Если ord ('0') равен 48. Если вы хотите найти истинное целочисленное значение str, вы должны вычесть 48. Поскольку разность 96 и 48 сама делится на 6, эта ошибка все равно не нарушает " делится на 6 "тест, но я тоже не вижу никакого преимущества.

2) ваш код должен игнорировать символы, отличные от числа, в противном случае эти символы будут вызывать преобразование вне луча. Например, простой пробел добавит -64 к вашему окончательному значению, которое не делится на 6 и нарушит тест.

Я предлагаю вам просто придерживаться int (str), чтобы преобразовать строку в int (длинное целое генерируется автоматически для очень длинных чисел) и захватить исключение ValueError для недопустимых str.

Answer 3

dic = {} 
for i in xrange(97,123): 
    dic[chr(i)] = str(i-96) 

str = raw_input() 
new_str = "" 
for i in xrange(len(str)): 
    new_str += dic[str[i]] 

val = 0 
for i in xrange(len(new_str)): 
    val = ((val*10)%6 + ((int(new_str[i]))%6))%6 # without modular arithmetic val will turn to long data type 

print "NO" if val else "YES" 

Используя длинный тип данных и применение операций на нем потребуется время. Итак, сначала расшифруйте исходную строку и сохраните целочисленную форму в строковом типе данных. Затем примените базовую модульную арифметику i.e (a + b)% m = (a% m + b% m)% m.