ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат УрФУ среди юниоров 2016

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Десериализация

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
В наш век современных технологий уже не принято использовать текстовые протоколы взаимодействия, все компьютерные программы общаются между собой исключительно с помощью бинарных протоколов, когда любые данные представляются в виде последовательности байтов.
Вот и в компании «Периметр» решили перевести все программы на использование бинарного протокола. Программист Вася неделю корпел и, всё доделав, с гордостью ушёл в отпуск восстанавливать нервы. Но баба Зина вечером в пятницу, протирая пол под рабочим местом Васи, случайно уронила на пол компьютер, после чего тот перестал работать. Руководство компании в панике — ни программиста, ни программы. Вас попросили в срочном порядке спасти положение, реализовав потерянную часть, а именно десериализацию бинарного протокола (преобразование закодированных данных в осмысленный формат).
Напомним, что при обмене информацией структурированные данные в процессе сериализации превращаются в набор байтов (чисел от 0 до 255), которые удобнее всего записать как последовательность шестнадцатеричных чисел, состоящих из двух цифр каждое. Затем эта последовательность передаётся по сети другой программе, которая её десериализует, получая на выходе исходный набор данных.
Передаваемые данные — последовательность структур. Каждая структура имеет имя и состоит из упорядоченного множества полей, каждое из которых может являться целым неотрицательным числом, строкой или другой структурой. При сериализации поля обрабатываются последовательно в порядке описания и одно за другим попадают в итоговый поток байтов.
Целые числа сериализуются в 4 байта, которые можно представить в виде шестнадцатеричной записи этого числа из 8 символов. Знаковый бит отсутствует, порядок битов — от старших к младшим. Например,
Problem illustration
Строки сериализуются как целое число — длина строки, а затем коды символов в таблице ASCII (по 1 байту). Известно, что в строчках встречаются только маленькие латинские буквы. Например,
Problem illustration
Структуры описываются названием и перечислением типов полей. Поле может быть либо типа «целое число», либо типа «строка», либо типа другой, ранее описанной структуры. При сериализации структуры сначала сериализуется первое поле в порядке описания, потом второе и так далее, пока список полей не кончится.

Исходные данные

В первой строке записаны целые числа n и l — количество известных структур и количество строк с описанием структур (1 ≤ n ≤ 240; 2nl ≤ 103). В следующих l строках задано описание структур. Гарантируется, что имена структур различны и никакое имя не совпадает с «int», «string» и «struct».
Первая строка в описании структуры: ключевое слово «struct» и название — непустая строка из маленьких латинских букв не длиннее 10 символов. В последующих строках записан упорядоченный список типов полей. Тип может быть либо словом «int», либо словом «string», либо названием структуры, которая уже была описана выше. Все типы отделены от начала строки пробелом. Гарантируется, что каждая структура содержит хотя бы одно поле.
В последней строке задан массив байт, в который был сериализован конкретный экземпляр структуры (или нескольких структур) — последовательность шестнадцатеричных цифр чётной длины (цифрам от 10 до 15 соответствуют заглавные латинские буквы A-F). Гарантируется, что последовательность является корректной и её длина не превосходит 104.
В массив байт могло быть сериализовано несколько структур. Перед сериализацией каждой структуры сериализуется порядковый номер данной структуры. Структуры индексируются с единицы в порядке описания их в исходных данных.

Результат

Выведите десериализованные экземпляры структур через перевод строки в том порядке, в котором они идут в сериализованных данных, в следующем формате:
  • в первой строке расположено название десериализованной структуры;
  • все последующие строки, принадлежащие представлению данного экземпляра, содержат ненулевое количество пробелов в начале;
  • если удалить у этих строк один пробел из начала, то получится список значений полей, разделённых переносом строки;
  • количество значений полей совпадает с количеством типов в описании структуры;
  • если тип из описания с соответствующим индексом — «целое число», то значение будет представлять из себя строку «int» (без кавычек) и число (без ведущих нулей), разделённые пробелом.
  • если тип из описания с соответствующим индексом — «строка», то значение будет представлять из себя строку «string» (без кавычек) и строку, состояющую только из маленьких латинских букв, разделённые пробелом.
  • если тип из описания с соответствующим индексом является структурой, то значение будет представлять из себя набор строк, содержащих десериализованное значение данной структуры в описываемом формате;
  • если сериализовать экземпляр в последовательность байтов по алгоритму, описанному выше, то она будет побайтово идентична соответствующей последовательности из входных данных.
Гарантируется, что размер выходных данных не превосходит 30 килобайт.

Пример

исходные данныерезультат
2 5
struct a
·string
struct b
·a
·int
000000020000000361626300000004000000010000000568656C6C6F
b
·a
··string abc
·int 4
a
·string hello

Замечания

Для наглядности в примере ведущие пробелы заменены на точки. Во всех тестах, включая пример, используется формат, описанный в условии.
Автор задачи: Михаил Вяцков
Источник задачи: Чемпионат УрФУ среди юниоров 2016
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2106. Десериализация