Рассылка закрыта
При закрытии подписчики были переданы в рассылку "физика YES" на которую и рекомендуем вам подписаться.
Вы можете найти рассылки сходной тематики в Каталоге рассылок.
Конкурсы и Олимпиады по Машинному программированию (КОМП) Заморозки
| Информационный Канал Subscribe.Ru |
Очень скоро наступит календарная зима и все осенние дела нужно закончить. Подходит к концу и наш осенний конкурс. Вряд ли кто-то из участников успеет преодолеть 9 уровень. Поэтому, с наступлением зимы, будем все замораживать.
Начиная с 1 декабря, будут "замораживаться" результаты уровней.
1
Торопитесь! Осталось всего несколько дней.
Теперь немного слов участникам, которые подключились недавно. Эти участники повторяют те же ошибки, что и старые участники. Чтобы избежать многих ошибок, нужно прочитать все рассылки этого конкурса.
Сегодня разберёмся с задачей чётвёртого уровня. Это первая, по-настоящему интересная задача конкурса.
Палиндром одной вставкой
Эта задача имеет простое, быстрое и красивое решение. Нужно разбить заданную строку на части и одну из них перевернуть. Перевернуть --- значит записать все символы в обратном порядке.
Введём обозначение. Если X --- строка, то [X] --- перевёрнутая строка. Значит строки X[X] и [X]X --- палиндромы. S --- заданная строка. Тогда S=AB[A], где A и B --- какие-то строки, возможно пустые. Например, если S --- палиндром, то B --- пустая строка. Находим самую длинную А. После этого задача сводится к решению для B.
Строка B устроена так. B=C[C]D и B=EF[F]. Определим, что короче D или E, вставлять
нужно одну из них перевернутую.
Если короче D, то искомая строка A[D]С[С]D[A].
Если короче E, то искомая строка AEF[F][E][A].
|
|
| Subscribe.Ru
Поддержка подписчиков Другие рассылки этой тематики Другие рассылки этого автора |
Подписан адрес:
Код этой рассылки: comp.soft.prog.comp Архив рассылки |
Отписаться
Вспомнить пароль |
| В избранное | ||
