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

Квалификационный тур восточного четвертьфинала 2015

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

A. Классификатор Тимуса

Ограничение времени: 2.0 секунды
Ограничение памяти: 256 МБ
Вова составил классификатор задач с сайта Timus Online Judge по темам. Все темы структурированы в виде дерева — то есть каждая тема может подразделяться ещё на несколько тем. Например, тему «геометрия» Вова разбил на две темы: «геометрия на идею» и «геометрия на технику». Для каждой темы указаны примеры задач на неё. Одна задача может относиться сразу к нескольким темам. Скажем, задача 1065 относится сразу к темам «графы» и «геометрия на технику».
Требуется по заданному классификатору для каждой задачи выдать список всех тем, к которым она относится.

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

В этой задаче не будет строгого описания формата ввода и вывода. Вы можете понять формат, изучив пример в условии. Мы укажем лишь следующие ограничения на входные данные.
  1. Всего входные данные содержат не более 20 тем и не более 20 различных номеров задач. К некоторым темам могут относиться сразу все задачи, а к некоторым — не относиться ни одной задачи.
  2. Все номера задач — числа в пределах от 1000 до 9999. Список задач, относящихся к теме, может быть записан в несколько строк, но в каждой из этих строк есть хотя бы один номер задачи. В списке не фигурирует дважды номер одной и той же задачи.
  3. Названия тем — непустые строки длиной не более 20, состоящие из строчных латинских букв и пробелов. Первый и последний символ названия — не пробел, двух пробелов подряд в названии также быть не может.
  4. Код темы — последовательность вида <число>.<число>. ... <число>. Все числа в коде лежат в пределах от 1 до 20 и не содержат ведущих нулей. Коды всех тем различны.
  5. Первая тема имеет код «1.»
  6. Если тема A расположена до темы B, то либо код B содержит код A как префикс, либо первое слева число, в котором различаются коды A и B, меньше у кода A.
  7. Если код темы имеет вид «X.» либо оканчивается на «.X.», где в обоих случаях X больше единицы, то обязательно где-то ранее описана тема с кодом, который отличается от кода данной только заменой суффикса «X.» на суффикс «Y.», где Y = X − 1.
  8. Если код темы оканчивается на «.1.», то непосредственно перед ней описана тема, код которой получается из кода данной отбрасыванием «1.» в конце.

Результат

Перечислите для каждой задачи список её тем, как показано в примере. Описание темы должно содержать её собственное название и название всех тем, являющихся предками этой темы в дереве. Если задача относится к нескольким темам, то описание этих тем нужно вывести через запятую и пробел. Если у нескольких задач абсолютно одинаковый набор тем, то нужно склеить их описания, перечислив номера задач через запятую и пробел.
Номера задач слева от двоеточия должны быть перечислены в порядке возрастания, описания тем справа от двоеточия также должны быть выведены в лексикографически возрастающем порядке. Все строки в ответе нужно также упорядочить лексикографически по возрастанию.

Пример

исходные данныерезультат
1. graphs
1022
1065
2. geometry
1020
2.1. idea
1130
2.2. technique
1111 1065
1265
2.2.1. convex hull
1271
3. dynamic programming
1244
1020 : geometry
1022 : graphs
1065 : geometry.technique, graphs
1111, 1265 : geometry.technique
1130 : geometry.idea
1244 : dynamic programming
1271 : geometry.technique.convex hull
Автор задачи: Михаил Рубинчик
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2074. Классификатор Тимуса