e-olymp 5062. Максимальный подпалиндром

Задача

Из данной строки удалите наименьшее количество символов так, чтобы получился палиндром (строка, одинаково читающаяся как справа налево, так и слева направо).

Входные данные: 

Непустая строка длиной не более [latex]100[/latex] символов. Строка состоит только из заглавных латинских букв.

Выходные данные:

Вывести строку-палиндром максимальной длины, которую можно получить из исходной вычёркиванием нескольких букв. При наличии нескольких решений необходимо вывести одно (любое) из них.

Тесты

 №  Входные данные  Выходные данные
 1 QWEERTYY YY
 2  QWEERT EE
 3 BAOBAB BAOAB
 4  ABCDCBA  ABCDCBA

Код программы

Засчитанное решение на e-olymp.

Решение

Так как палиндром читается одинаково как справа налево, так и слева направо, то максимальным подпалиндромом будет наибольшая общая подстрока двух строк: исходной строки [latex]s_1[/latex] и этой же строки, но записанной в обратном порядке [latex]s_2[/latex] (как, если бы мы её читали справа налево). Для нахождения их наибольшей общей подстроки следует заполнить таблицу [latex]D[/latex] размером [latex] (n+1)\times(n+1) [/latex], где [latex]n[/latex]-длина строки. Заполнять таблицу будем методом аналогичным поиску длины наибольшей общей подстроки, но в каждой ячейке [latex]D_{i j}[/latex] таблицы будем хранить наибольшую подстроку строки, содержащей только первые [latex]i[/latex] символов [latex]s_1[/latex], и строки, содержащей только [latex]j[/latex] первых символов [latex]s_2[/latex]. В ячейках [latex]D_{0 j}[/latex] и [latex]D_{i 0}[/latex] будем хранить пустые строки. Если [latex]i[/latex]-й символ строки [latex]s_1[/latex] равен [latex]j[/latex]-ому символу строки [latex]s_2[/latex], то в ячейку [latex]D_{i j}[/latex] запишем конкатенацию строки из ячейки [latex]D_{i-1 j-1}[/latex] и данного символа. Иначе в ячейке [latex]D_{i j}[/latex] будем хранить наибольшую из строк [latex]D_{i-1 j}[/latex] и [latex]D_{i j-1}[/latex]. Таким образом в ячейке [latex]D_{n n}[/latex] будет хранится наибольший подпалиндром исходной строки.

Ссылки

e-olymp 2162. Палиндром

Задача. Палиндром

Условие задачи

Палиндром — это строка, которая одинаково читается слева направо и справа налево. Составьте программу, которая проверяет, является ли заданный текст палиндромом. Не забудьте, что при чтении пробел никак не произносится.

Входные данные

Дана строка [latex]S[/latex], [latex]|S| \leq 255[/latex], состоящая из строчных латинских букв и пробелов. Под [latex]|S|[/latex] подразумевается длина строки.

Выходные данные

Требуется вывести «YES«, если текст является палиндромом, «NO» если не является.

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

Тестирование

Входные данные Выходные данные
1. palindrom NO
2. a roza upala na lapu azora YES
3. my gym YES
4. character NO

Реализация (с использованием c-string)

Алгоритм решения (c-string)

С помощью функции [latex]strcmp()[/latex] сравниваем символы строк [latex] s_1[/latex] и [latex]s_2[/latex], предварительно учтя тот факт, что пробел при чтении никак не произносится. Если они идентичны,  введенный текст одинаково читается слева направо и справа налево, то есть является палиндромом. В противном случае, текст палиндромом не является. Важно отметить, что функция [latex]strcmp()[/latex] учитывает регистр введенных символов, согласно условию мы должны использовать строчные латинские буквы.

Для запроса на выполнение следует перейти по ссылке.

Ссылка на засчитанное решение на e-olymp.com.

Реализация (с использованием string)

Алгоритм решения (string)

Сравниваем соответствующие символы строки до середины, проверяя тем самым, читается ли введенный текст одинаково справа налево и слева направо, то есть является палиндромом. Учитываем, что пробел при чтении никак не произносится: считываем из входного потока по символу и помещаем в строку только буквы.

Для запроса на выполнение следует перейти по ссылке.

Ссылка на засчитанное решение на e-olymp.com.

e-olymp 331. Предложение — чемпион

Условие

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

Замечание

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

Тесты

Входные данные Номер предложения
No palindrom here. Here it is: abcba! Seriously, I just hate orks… 2
Some random text ahead: AaA o-O-o I. 1 22 333. Result will be 1. 1
Some random text ahead: AaA o-O-o I. 1 22 333 4444. Now result will be 2! 2
Some random text ahead: AaA o-O-o I. 1 — 22 — 333. Result will be 1. 1
No. Palindrom. at. ALL?! 0

Решение

Заведем переменную [latex]currentSentence[/latex], хранящую номер текущего предложения, будем считывать по слову и увеличивать ее значение на 1, если текущее слово заканчивается на точку, восклицательный или вопросительный знак. Далее, поочередно удаляем с конца лишние символы, заменяя их терминальным, пока не встретится первая буква. Затем переводим слово в нижний регистр и проверяем его на палиндромность, если да — увеличиваем на 1 переменную-счетчик кол-ва палиндромов в текущем предложении  [latex]palCount[/latex]. Если слово было последним в предложении (за это отвечает флаг [latex]endOfSentence[/latex]) — сравниваем предложение с предыдущим чемпионом, после обнуляем значение [latex]palCount[/latex].

Код

Ссылки

Рабочий код на Ideaone.

Засчитанное решение на E-olymp.

e-olymp 330. Слово-чемпион

Задано некоторое предложение на неизвестном языке. Назовем слово в нем чемпионом, если оно является палиндромом и количество букв в нем максимально. Буквами алфавита в неизвестном языке являются буквы латинского алфавита и арабские цифры. Гарантируется, что других символов, кроме пробелов и знаков препинания в предложении нет.

Задача взята с сайта e-olymp.

Входные данные

Предложение на неизвестном языке.

Выходные данные

Номер слова-чемпиона.

Тесты

Предложение Номер слова-чемпиона
Oo, it aaa is not bb. 3
Tummut, suuruu 18! 1
Qrtew asd x, pol 123 xcv. 3
Antaa, qor — aapapaa for Saippuakivikauppias kappak! 6
A b C d E f G h 1
NoPalindrome 0
123321 oro 1234554321? 3

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

Алгоритм

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

  1. Слово-палиндром может содержать в себе буквы различного регистра, что может помешать при проверке на палиндромность. Во избежание ошибки переведем все слово, например, в нижний регистр с помощью соответствующей функции.
  2. В предложении встречаются знаки препинания, поэтому если последний символ в слове не является буквой латинского алфавита или цифрой (проверку для удобства чтения вынесем в отдельную функцию), заменим его на нуль-символ, чтобы в дальнейшем его не учитывать.

После проведенных операций найдем длину текущего слова и, если она превышает максимальную длину ранее найденного слова-чемпиона, проверим, является ли текущее слово палиндромом. Осуществим это с помощью рекурсивной функции, сравнивающей соответствующие символы в данной строке по индексам. Функция работает до тех пор, пока начальный и конечный индекс не сравняются или поменяются местами (изначально первый индекс (start) равен нулю, а конечный (end) меньше длины строки на единицу), или же соответствующие символы окажутся разными. Если данное слово оказалось палиндромом, храним его порядковый номер в предложении.
Как только предложение завершено, выводим индекс найденного слова-чемпиона, или индекс первого из них, если таковых было несколько.

Код программы:

Код программы

Засчитанное решение

e-olymp 29. Уровень палиндромности

Задано натуральное [latex]M[/latex]. Если число не палиндром – записываем его в обратном порядка и слагаем с заданным. Действия повторяем до тех пор, пока не получим число-палиндром. Количество выполненных операций назовем уровнем палиндромности заданного числа.

Найти уровень палиндромности заданного числа [latex]M[/latex].

Входные данные

Единственное число [latex]M[/latex] ([latex]0[/latex] [latex] <[/latex] [latex]M[/latex] [latex] <[/latex] [latex]10000[/latex]).

Выходные данные

Единственное число – уровень палиндромности.

Задача взята с сайта e-olymp.

Тесты

  Входные данные   Выходные данные
1 0
79 6
101 0
198 5
865 2
9998 6

Алгоритм

В данной задаче для заданного числа требуется определить  уровень его палиндромности — количество раз, которое придется просуммировать его с обратным ему числом до получения палиндрома.

  1. Для начала инициализируем счетчик, который хранит в себе текущее значение уровня палиндромности, и логическую переменную, значение которой ложно до тех пор пока палиндром не найден. Данное условие и будет критерием для выполнения тела основного цикла.
  2. Присвоив значения переменным в цикле, выполняем последовательный разбор введенного числа на цифры и сборку «зеркального» числа.
  3. Проверяем равенство числа и ему обратного.
  4. Выполнение условного оператора сигнализирует о том, что палиндром найден, следовательно выводим «уровень», изменяем значение логической переменной на противоположное и выходим из цикла.
  5. В противном случае суммируем текущее число и «зеркальное», инкрементируем счетчик.
  6. Повторяем пункты 2, 3, 5 до истинности пункта и перехода к 4.

Код программы:

 

Код программы

Засчитанное решение