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

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

HotLog


 

Дерево - 2

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

Катя решила разместить на стене комнаты свое родословное дерево из фотографий. В корне дерева она повесила свою фотографию. Фотографии мамы и папы – это левое и правое поддеревья. И так далее… Катя повесила на стену фотографии всех родственников, которых она знала, полюбовалась на свою работу, и ушла гулять.

Пока Кати не было, её брат Антон решил вставить фотографии в рамочки. Для этого он решил снять фотографии. Сначала он слева-направо снял все фотографии, которые являются листьями дерева (лист - это вершина, у которой нет поддеревьев.) Снятые портреты Антон сложил в стопку и перенес к себе в комнату. Затем вернулся в комнату Кати и повторил процедуру. В конце концов на стене остался только портрет Кати. Антон перенес и этот портрет к себе.

И вот тут Антон понял, что восстановить дерево по оставшимся у него стопкам портретов он не может! Помогите Антону восстановить дерево! Вам должны помочь буквенные обозначения, которыми Катя пометила все узлы дерева. Каждый узел удовлетворяет следующим условиям:

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

На рисунке показан пример дерева, а также последовательность действий Антона.

Удаление узлов с данными:

BDHPY
CM
GQ
K

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

Входной файл INPUT.TXT содержит нескольких строк, где каждая строка содержит буквенные обозначения удаленных узлов. Последняя строка теста содержит знак «*». Гарантируется, что в дереве есть хотя бы один узел. Число узлов дерева не превосходит число символов английского алфавита. Каждая буква в тесте встречается только один раз.

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

В выходной файл OUTPUT.TXT выведите структуру дерева в следующем формате: сначала корень дерева, потом данные левого поддерева, потом данные правого поддерева.

Пример

INPUT.TXTOUTPUT.TXT
1BDHPY
CM
GQ
K
*
KGCBDHQMPY

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

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

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



Беспроводные охранно пожарные сигнализации.