print1483. Парад шушанчиков

printПарад шушанчиков

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Однажды крокодил Гена устроил парад шушанчиков. Для этого он взял несколько шушанчиков, окрашенных в разные цвета, и выстроил в ряд. Ряд задан строкой, в которой шушанчики разных цветов обозначены разными буквами.
Гена не любит повторений, поэтому, прохаживаясь перед строем, он находит и выгоняет группы из чётного количества подряд стоящих шушанчиков, в которых цвет у первого шушанчика совпадает с последним, второго с предпоследним и т.д., так что вся группа выглядит одинаково при проходе слева направо и справа налево. Крокодил продолжает это делать до тех пор, пока либо шушанчики не закончатся, либо в оставшемся ряду ему не удастся найти ни одной такой группы.
Например, если ряд задан строкой abbbccbb, Гена может поступить следующим образом: abbbccbb `→` abccbb `→` ab
Крокодил хочет добиться, чтобы в ряду осталось как можно меньше шушанчиков.
Формат входного файла
Во входном файле содержится строка, задающая ряд шушанчиков.
Формат выходного файла
В выходной файл следует вывести строку минимально возможной длины, задающую ряд из оставшихся шушанчиков. Если существует несколько решений одинаковой длины, вывести любое из них. Если же возможно выгнать всех шушанчиков, следует вывести строку EMPTY.
Ограничения
Исходная строка состоит из маленьких латинских букв, её длина не превышает 200000 символов.

Пример ввода 1

abbbccbb

Пример вывода 1

ab

Пример ввода 2

abbaccdd

Пример вывода 2

EMPTY

Пример ввода 3

aaacccmmm

Пример вывода 3

acm
Источник: http:/imcs.dvgu.ru/cats/, Весенний турнир, 2007
loading