Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1483. Парад шушанчиков
Стеки, очередиОлимпиадные задачи на русском языке
| 24/06/2010 | Лето 2010 дорешивание (12D) |
| 19/07/2010 | Лето 2010 - 12 (D) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Однажды крокодил Гена устроил парад шушанчиков. Для этого он взял несколько шушанчиков, окрашенных в разные цвета, и
выстроил в ряд. Ряд задан строкой, в которой шушанчики разных цветов обозначены разными буквами.
Гена не любит повторений, поэтому, прохаживаясь перед строем, он находит и выгоняет группы из чётного
количества подряд стоящих шушанчиков, в которых цвет у первого шушанчика совпадает с последним, второго с предпоследним и т.д., так что вся группа выглядит одинаково при проходе слева направо и справа налево. Крокодил продолжает это делать до тех пор, пока либо шушанчики не закончатся, либо в оставшемся ряду ему не удастся найти ни одной такой группы.
Например, если ряд задан строкой abbbccbb, Гена может поступить
следующим образом: abbbccbb `→` abccbb `→` ab
Крокодил хочет добиться, чтобы в ряду осталось как можно меньше шушанчиков.
Формат входного файла
Во входном файле содержится строка, задающая ряд шушанчиков.
Формат выходного файла
В выходной файл следует вывести строку минимально возможной длины, задающую ряд из оставшихся шушанчиков. Если существует несколько решений одинаковой длины, вывести любое из них. Если же возможно выгнать всех шушанчиков, следует вывести строку EMPTY.
Ограничения
Исходная строка состоит из маленьких латинских букв, её длина не превышает 200000 символов.
Пример ввода 1
abbbccbb
Пример вывода 1
ab
Пример ввода 2
abbaccdd
Пример вывода 2
EMPTY
Пример ввода 3
aaacccmmm
Пример вывода 3
acm
