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

Чемпионат Урала 2009

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

A. Пробуждение

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Николай возвращался домой с работы на метро. Обычно он предпочитал передвигаться пешком, любуясь висящей над самым горизонтом Землёй, но сегодня он спешил. Поезд бесшумно скользил по магнитному рельсу, перевозя людей по кольцевому маршруту вдоль стены купола. Глядя в одно окно, можно было увидеть величественные небоскрёбы и многоуровневые эстакады огромного мегаполиса; в другом же окне, сколько хватало взгляда, простиралась лунная пустыня. В самом вагоне было людно. Большинство пассажиров были похожи на Николая — неброский костюм, тонкий кейс в руке и дорогой коммуникатор вместо часов. Таков был типичный внешний вид рабочей пчёлки информационного общества Луны. Некоторые из них тихо о чём-то переговаривались, другие устало смотрели в окно. Из общей массы выделялось несколько человек с каменными лицами и стеклянными глазами. Можно было заметить, что у каждого из них к коммуникатору был подключен тонкий белый проводок, который тянулся к голове и заканчивался где-то за ухом.
На очередной остановке рядом с Николаем освободилось место. Он сел, устроился поудобнее и достал из кармана такой же проводок. Он подключил один конец к коммуникатору, а второй поднёс к своей голове, нащупал за ухом нейропорт и подключился к нему. Тотчас перед ним предстал привычный интерфейс его рабочего стола. Всё, что он видел своими глазами, оказалось выделенным в отдельное окно с названием «Реальный мир». Николай нажал на кнопку отключения звука в этом окне и шум вагона стих. Ничто не могло теперь отвлечь его от чтения почты. К сожалению, в почтовом ящике был один спам. Но одно из этих писем привлекло его внимание. В нём рекламировался эксклюзивный клуб для преуспевающих молодых людей. Мужчина на картинке сиял от радости и беспрестанно повторял: «Я счастлив быть здесь!» Николай выделил адрес этого клуба и скопировал его в записную книжку.
Николай отключился от коммуникатора, когда поезд уже подъезжал к его станции. Он вышел из метро и быстрым шагом направился к своему дому. Его квартира находилась на семнадцатом этаже. Она была невелика, но в окна светило солнце, что ценилось превыше всего. Внутри царил идеальный порядок, более того, трудно было поверить, что здесь живёт живой человек. Если бы какой-нибудь шпион решил проникнуть внутрь, он не нашёл бы ни одного предмета, который характеризовал бы Николая как личность. Сказать по правде, Николай и сам не знал, что он за человек.
Он не задержался в своей квартире надолго. Он переоделся в одежду типичного безработного обитателя нижних уровней — длинные рукава скрывали его коммуникатор, а капюшон скрывал его нейропорт. Выйдя на улицу, Николай направился прямо к одному из трёх гигантских лифтов, которые связывали поверхность, накрытую куполом, и множество подземных уровней, где была сконцентрирована вся промышленность и системы жизнеобеспечения, где жила основная часть населения Города. Каждый такой лифт напоминал земной паром — машины заезжали в него и становились в аккуратные ряды, люди покупали билеты и рассаживались по своим местами, ожидая отправки. Наконец, звучал гудок, загорались красные сигналы и лифт медленно начинал ползти вниз. Для кого-то это было щекочущее нервы путешествие в поисках запретных радостей, а кто-то возвращался не солоно хлебавши туда, откуда он так хотел вырваться.
Для Николая это не было первым путешествием вниз. Он достаточно хорошо ориентировался под землёй, поэтому быстро сообразил, где находится тот эксклюзивный клуб, о котором он прочитал в рекламе. Это были старые шахты, где на заре колонизации добывали лёд. Они простирались на многие километры вокруг и считались одним из самых опасных мест для жителей поверхности. Но Николай умел сливаться с толпой и перемещаться, не вызывая подозрений. Людской поток вынес его прямо к воротам небольшого обшарпанного особняка. Николай постоял немного в нерешительности, убедился в правильности адреса и зашёл внутрь.
Внутреннее убранство клуба резко контрастировало с его внешним обликом. Посетитель попадал в просторный, хорошо освещённый зал с высоким потолком. Интерьер производил впечатление элегантной простоты, которую могут позволить себе только очень богатые люди. В противоположном от входа конце зала находилась стойка администратора, за которой сидела красивая, ухоженная девушка. Когда Николай подошёл к ней, она широко улыбнулась и мягко произнесла:
— Добрый день, могу я увидеть вашу карточку члена клуба?
Николай на миг растерялся, но быстро собрался и твёрдо произнёс:
— Я счастлив быть здесь.
Девушка ещё шире улыбнулась ему, поднялась со своего места и сказала:
— Мы тоже очень рады вас видеть. Следуйте за мной, пожалуйста.
Они прошли по извилистому коридору мимо многочисленных дверей, пока девушка не остановилась перед тяжёлой красной портьерой и не пригласила его внутрь. Николай отодвинул портьеру и шагнул вперёд.
Достаточно большое помещение было разгорожено красными полупрозрачными вуалями на множество маленьких кабинок, в каждой из которых стояла кушетка и маленькая тумбочка. И хотя комната утопала в полумраке, Николай смог разглядеть, что на некоторых из кушеток лежат люди. Под потолком вился лёгкий дымок, в воздухе чувствовался сладковатый запах, от которого начинала слегка кружиться голова. В одной из пустующих кабинок на тумбочке горела настольная лампа. Николай зашёл туда и сел на кушетку.
Не прошло и пяти минут, как в соседнюю кабинку вошёл человек. Николай не мог разглядеть его лица, но, благодаря лампе, человек прекрасно видел Николая. Он сел на кушетку и спросил трескучим голосом:
— Вы принесли деньги?
Николай достал из кармана пластиковую карточку и положил её под вуаль. Человек взял её и провёл над считывающим устройством. На экране отобразилось число, которое, судя по всему, его удовлетворило. Он сунул карточку в один карман, а из другого достал маленький синий куб, положил его на пол и ногой передвинул на сторону Николая.
— Напоминаю два правила, — произнёс незнакомец. — Во-первых, обладание подобным устройством карается на Луне смертной казнью. Во-вторых, вас ждёт что-то похуже смертной казни, если вы проболтаетесь, где его взяли.
Не дожидаясь реакции Николая, человек встал и вышел.
Николай протянул руку и взял синий куб. В центрах двух противоположных граней находилось по нейропорту. Вся остальная поверхность была гладко отполирована. Николай поразился внешней простоте этого легендарного устройства. Оно называлось «Модуль управления ассоциативными связями», в просторечии — «промывалка мозгов». Используя его, можно было заставить кредитора забыть о вашем долге, а заносчивой фотомодели внушить неудержимую любовь к бомжу. Но Николай не собирался использовать его на других людях. Всё, чего он хотел — это узнать, кто он на самом деле. Он хотел помнить больше, чем три последних года своей жизни.
Problem illustration
Николай вернулся домой в середине ночи и сразу же подключил себя к кубу. Используя свой домашний компьютер, он начал изучать собственный мозг. Он быстро выделил воспоминания последних трёх лет и начал изучать остальную память. Она не была стёрта, но и не была похожа на человеческие воспоминания. Это были бессмысленные ассоциативные цепочки, причудливо ветвящиеся, но, к удивлению Николая, каждая из них неизбежно замыкалась на одном из пяти ярких, чётких образов. Этими образами были кит, пингвин, пианино, сапог и поезд.
Николай выдернул шнур из-за уха и задумался. Кто-то, возможно, он сам, хорошо поработал над его головой. Ассоциативные цепочки были перемешаны на всю глубину. Но эти пять объектов должны были что-то обозначать. Возможно, это был какой-то код, к которому нужно было подобрать ключ. Возможно, эти пять предметов как раз и указывали на ключ. Должно было быть что-то, что их объединяет. Николай решил написать программу, которая бы пыталась найти общие ассоциации у группы объектов.

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

В первой строке указано число n — количество объектов (2 ≤ n ≤ 1000). Каждая из следующих n строк содержит название объекта, двоеточие, пробел и набор ассоциаций этого объекта, разделённых пробелом. Название объекта и ассоциации состоят только из строчных латинских букв. В следующей строке указано число m — количество наборов объектов, для которых нужно найти общие ассоциации (1 ≤ m ≤ 1000). Каждая из следующих m строк содержит эти наборы в виде перечисления через пробел названий объектов. В каждом наборе не меньше двух объектов. Все строки не превышают 250 символов в длину.

Результат

Для каждого набора объектов выведите на отдельной строке все общие ассоциации этих объектов, отсортированные по алфавиту и разделённые пробелом. Если у объектов в наборе нет общих ассоциаций, выведите строку «No solution.»

Пример

исходные данныерезультат
6
whale: big black water animal
penguin: black white ice beak
piano: keyboard black white wire
jackboot: leather heel black
train: rail wheel black
rose: red green thorn
3
whale penguin piano jackboot train
penguin piano
jackboot rose
black
black white
No solution.
Автор задачи: Павел Атнашев
Источник задачи: XIII чемпионат Урала по спортивному программированию, 4 апреля 2009 г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1700. Пробуждение