-4

Задача: B. Палиндромный фактор Ограничение по времени: 1 секунда Ограничение памяти: 512 МБ Ввод: стандартный ввод или input.txt Вывод: стандартный вывод или output.txt

Напомним, что палиндром - это строка, которая одинаково читается от начала до конца и от конца до начала. Для каждой строки в своей базе данных Аркадий хочет найти самую короткую подстроку, состоящую как минимум из двух символов и являющуюся палиндромом. Если таких подстрок несколько, Аркадий хочет выбрать лексикографически минимальную.

Формат ввода: Одна строка входных данных содержит одну строку из базы данных Аркадия — непустую последовательность строчных букв английского алфавита. Длина строки не менее 2 и не превышает 200000 символов.

Формат вывода: Выведите подстроку минимальной длины строки из входных данных, состоящую как минимум из двух символов и являющуюся палиндромом. Если такой подстроки нет, выведите -1. Напомним вам, что среди всех таких строк Аркадий хочет найти лексикографически минимальную. Примечание о лексикографическом минимуме . Ссылка на сайт с заданием, задача В: Yandex Cup 2021. Ссылка на симулятор: Сontest.yandex (Требуется авторизация)

Решение от разработчиков: Пусть есть какая-то подстрока, которая является палиндромом. Если мы удалим первый и последний символы палиндрома, оставшаяся строка также будет палиндромом. Мы будем повторять процесс до тех пор, пока не появится строка из двух или трех букв (в зависимости от четности).

Всегда существует линейное число подстрок длиной два или три, и их общая длина также линейна, поэтому среди таких строк ответ может быть выбран наивным алгоритмом. Если ни одна из подстрок этой длины не является палиндромом, то мы выводим -1.

Симулятор не принимает мой код и пишет неправильный ответ, но я не могу найти ошибку, кто-нибудь решал подобную проблему или знает, где у меня ошибка?

Мой код:

word = input('Write: ')
palindrome = []
palindrome2 = []
palindrome3 = {}
palindrome4 = []


def checking(word1):
    if 2 <= len(word1) <= 200000:
        comput(word1)
    else:
        word1 = input('Write: ')
        checking(word1)


def comput(word2):
    for i in range(len(word2)):
        if i == (len(word2) - 1):
            break
        elif word2[i - 1] == word2[i + 1] and i != 0:
            count1 = i - 1
            count2 = i + 1
            while count2 != len(word2) and count1 >= 0 and word2[count1] == word2[count2]:
                count1 -= 1
                count2 += 1
            else:
                word_count = word2[count1 + 1:count2]
                palindrome.append(word_count)
        elif word2[i] == word2[i + 1]:
            count1 = i
            count2 = i + 1
            while count2 != len(word2) and count1 >= 0 and word2[count1] == word2[count2]:
                count1 -= 1
                count2 += 1
            else:
                word_count = word2[count1 + 1:count2]
                palindrome.append(word_count)
    last_action(palindrome)


def last_action(list1):
    if len(list1) != 0:
        for pal in list1:
            while len(pal) != 2 and len(pal) != 3:
                pal = pal[1:-1]
            else:
                palindrome2.append(pal)
        for i in palindrome2:
            palindrome3[i] = len(i)
        min_val = min(palindrome3.values())
        for i in palindrome3:
            if palindrome3[i] == min_val:
                palindrome4.append(i)
        palindrome4.sort()
        print(palindrome4[0])
    else:
        print(-1)


checking(word)

1 ответ 1

0

Привествие к вводу убери), он мешает. Надо просто:

word = input()

И проверять длину введённой строки не надо, строка всегда валидна. Ограничения даны для строго типизированных языков

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.