Отправляет email-рассылки с помощью сервиса Sendsay
  Все выпуски  

Конкурсы и Олимпиады по Машинному программированию (КОМП) Заморозки


Информационный Канал Subscribe.Ru

Очень скоро наступит календарная зима и все осенние дела нужно закончить. Подходит к концу и наш осенний конкурс. Вряд ли кто-то из участников успеет преодолеть 9 уровень. Поэтому, с наступлением зимы, будем все замораживать.

Начиная с 1 декабря, будут "замораживаться" результаты уровней. 1 декабря --- 1 уровень, 2 декабря --- 2 уровень, и т.д., 9 декабря --- 9 уровень. "Замораживаться" --- значит, что участники оказавшиеся на этом уровне в этот день больше на другие уровни не переходят и их программы не тестируются. Для них конкурс закончен.

Торопитесь! Осталось всего несколько дней.


Теперь немного слов участникам, которые подключились недавно. Эти участники повторяют те же ошибки, что и старые участники. Чтобы избежать многих ошибок, нужно прочитать все рассылки этого конкурса.

Сегодня разберёмся с задачей чётвёртого уровня. Это первая, по-настоящему интересная задача конкурса.

Палиндром одной вставкой

Эта задача имеет простое, быстрое и красивое решение. Нужно разбить заданную строку на части и одну из них перевернуть. Перевернуть --- значит записать все символы в обратном порядке.

Введём обозначение. Если 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].



Автор: Пупышев Вячеслав Викторович   
e-mail: pvv@uni.udm.ru   
Web: http://colymp.da.ru   

Subscribe.Ru
Поддержка подписчиков
Другие рассылки этой тематики
Другие рассылки этого автора
Подписан адрес:
Код этой рассылки: comp.soft.prog.comp
Архив рассылки
Отписаться
Вспомнить пароль

В избранное