Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

История одного анекдота

(Время: 1 сек. Память: 256 Мб Сложность: 74%)

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

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

  1. «push_x» – добавить букву «x» в конец слова;
  2. «pop» – удалить последнюю букву (этот тип применим только для непустых слов).

Анекдотолог Иван собрал историю одного анекдота – все версии анекдота, полученные корректной последовательностью изменений начиная с пустого слова, но есть нюанс. К сожалению, версии даны в произвольном порядке, а для публикации в научном журнале нужно восстановить последовательность изменений.

Помогите Ивану – найдите последовательность изменений такую, что применив её к изначально пустому слову, набор всех промежуточных версий совпадёт с имеющейся историей не учитывая порядка.

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

Первая строка входного файла INPUT.TXT содержит целое число n – количество версий (1 ≤ n ≤ 3 000).

В следующих n строках содержится по одному слову, состоящему из строчных букв латинского алфавита и записанному в кавычках.

Суммарная длина слов не превосходит 106.

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

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

В выходной файл OUTPUT.TXT выведите список из n−1 изменений в том порядке, в котором их нужно выполнять. Каждое изменение должно быть описано в отдельной строке.

Список слов, полученных этим списком действий, должен совпадать с данным списком слов, не учитывая порядка.

Примеры

INPUT.TXTOUTPUT.TXT
15
"a"
"b"
""
""
""
push_a
pop
push_b
pop
26
""
""
"a"
"b"
"ab"
"a"
push_b
pop
push_a
push_b
pop

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2021 / 2022
 2022 / 2023
 A. Вы все уже победители
 B. Заработай себе металлолома
 C. Обледенение
 D. Дата сайнс
 E. Вирусные воспоминания
 F. Докраска забора
 G. Скатерть
 H. История одного анекдота
 I. Кружок
 J. JuryGPT

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru