--->
45 задач
<---
Источники
Дана непустая строка, длина которой не превышает 106. Требуется для каждой позиции символа в строке найти длину наибольшего палиндрома с центром в этом символе. Строка состоит из букв английского алфавита, большие и маленькие буквы считаются различными. Ограничение времени - 1 секунда.
Одна строка длины N, 0 < N ≤ 106.
N чисел, разделенные пробелами.
abcd
1 1 1 1
aaaaa
1 3 5 3 1
Дана непустая строка s. Нужно найти такое наибольшее число k и строку t, что s совпадает со строкой t, выписанной k раз подряд.
Ограничение времени - 1 секунда.
Одна строка длины N, 0 < N ≤ 106, состоящая только из маленьких латинских букв.
Одно число - наибольшее возможное k.
aaaaa
5
abcabcabc
3
abab
2
Петя нашел на чердаке старый телеграфный аппарат и приделал к нему хитроумное устройство, которое может печатать на телеграфной ленте определенное слово (обозначим его X). Петино устройство может напечатать на ленте это слово сколько угодно раз. Петя может заставить аппарат напечатать на ленте и любое другое сообщение, но для этого ему нужно разобрать свое хитроумное устройство, и после этого он уже не сможет печатать сообщение X. А самое главное, что напечатать даже один символ другого сообщения потребует от Пети больше усилий, чем напечатать на ленте слово X с помощью хитроумного устройства.
Петя хочет сделать так, чтобы всем казалось, что ему по телеграфу пришло сообщение Z. Для этого он может (строго в этой последовательности):
Поскольку набирать отдельные символы сообщения Y довольно сложно, Петя хочет, чтобы в сообщении Y было как можно меньше символов.
Для лучшего понимания задачи смотрите примеры и пояснения к ним.
В первой строке вводится слово X, которое Петя может печатать с помощью хитроумного устройства сколько угодно раз. Во второй строке вводится сообщение Z, которое хочет получить Петя. Каждое сообщение состоит только из маленьких латинских букв и имеет длину не более 100 символов.
Выведите минимальное по длине сообщение Y, которое Пете придется допечатать вручную.
Комментарии к примерам тестов
1. Сначала Петя два раза напечатает слово mama, потом к нему припечатает букву m, а затем отрежет и выбросит три начальных символа (mam). Ответом является допечатываемая отдельно буква m.
2. Казалось бы, Пете стоит сначала напечатать букву m, а затем слово ura, которое он умеет печатать. Однако для того, чтобы напечатать m, ему придется разобрать свое устройство, и печатать ura ему придется также посимвольно.
3. Казалось бы, Петя может напечатать слово computer, а затем отрезать и выбросить его конец — однако он не может так поступить, потому что отрезать и выбросить он может только начало ленты.
4. Пете достаточно один раз напечатать слово ejudge, а затем отрезать и выбросить букву e. Ничего посимвольно выводить ему не придется, поэтому ответом является пустая строка.
5. Достаточно трижды напечатать исходное слово и нужный результат будет получен. Ничего добавлять не надо, поэтому ответ – пустая строка.
mama amamam
m
ura mura
mura
computer comp
comp
ejudge judge
m mmm
Как вы знаете, ученые сформулировали главный вопрос жизни, вселенной и всего такого с помощью фишек для скрэббла (ответ на него равен \(42\), на его вычисление ушло семь с половиной миллионов лет). Вопрос формулируется так: «Что получится в результате умножения 6 на 9?». Однако, этот вопрос не совсем удовлетворил ученых и они решили сконструировать компьютер, который умеет отвечать на «вспомогательные» вопросы жизни, вселенной и всего такого.
Такой компьютер был построен, но, к несчастью (но не неожиданно), результат вычислений был поврежден и частично утерян. Наконец, создателям компьютера удалось извлечь строку, которая является частью корректного вопроса. Внимательно проанализировав строку, ученые пришли к выводу, что вопрос может быть восстановлен из строки путем добавления некоторых букв к строке, при этом исходные буквы строки не могут быть переставлены или удалены. Также они уверены, что корректный вопрос представляет собой арифметическое выражение (как и главный вопрос), но, поскольку вопрос вспомогательный, то он не может содержать умножения — только сложение. Точнее, вопрос должен удовлетворять следующей грамматике:
Вам необходимо восстановить вопрос, основываясь на его части.
Единственная строка входного файла содержит поврежденный вопрос. Это непустая строка, состоящая не более чем из \(1000\) символов. Строка содержит только символы '+', '(', ')' а также цифры от 0 до 9.
Выведите вопрос. Гарантируется, что существует корректный вопрос, длина которого не превышает \(5000\) символов, и вывод вашей программы также не должен превышать \(5000\) символов. Если вариантов восстановления вопроса несколько — выведите любой из них.