images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
26/04/2024 15:22:47

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1908. Семантическая сеть

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

24944.png
Семантическая сеть — информационная модель предметной области, имеющая вид графа, вершины которого соответствуют объектам предметной области, а рёбра (дуги) задают отношения между ними. Объектами могут быть люди, понятия, события, свойства. В этой задаче вам необходимо построить семантическую сеть на основании информации из СМИ, а затем определить силу семантических связей между некоторыми объектами. Если два объекта упоминаются вместе в `M` статьях, то будем считать силу прямой семантической связи между этими объектами равной `M`. Объекты могут быть связаны между собой не только прямо, но косвенно, через другие объекты. В этом случае силу семантической связи будем рассчитывать как `max_P\ {M(P)}/{L(P)}`, где `P` – кратчайший путь между объектами, `L(P)` – длина этого пути, `M(P)` – минимальная сила прямых семантических связей на пути `P`. Если пути между объектами не существует, то сила семантической связи равна 0. Например, между понятиями elkin и mafia есть два кратчайших пути elkin-sosnovskiy-mafia (с минимальной силой связи `M(P)=2`) и elkin-bank-mafia (`M(P)=1`). Длина кратчайшего пути `L(P)=2`. Максимум значения выражения достигается на первом пути: `2//2=1`.
Формат ввода
Первая строка ввода содержит два целых числа: количество статей `N` (`1\ ≤\ N\ ≤\ 1000`) и количество запросов `Q` (`1\ ≤\ Q\ ≤\ 1000`). В следующих `N` строках содержится от двух до четырех слов, разделенных пробелами. Каждая строка соответствует одной статье в СМИ и указывает, какие объекты в ней связываются между собой. Количество объектов не более 2000. Далее следует `Q` строк, содержащих ровно два слова, разделенных пробелом – запросы на расчет силы семантической связи между объектами. Все слова состоят из строчных латинских букв, и их длина не превышает 15 букв. Имена объектов в статье или запросе не повторяются.
Формат вывода
Для каждого запроса вывести строку, содержащее одно число – силу семантической связи между объектами с точностью `10^{-6}`.

Пример ввода

6 4
elkin bank sosnovskiy
bank sosnovskiy mafia
bank elkin sosnovskiy
bank elkin
mafia sosnovskiy
sosnovskiy mafia
bank sosnovskiy
bank mafia
elkin mafia
elkin palkin

Вывод для примера

3.000000
1.000000
1.000000
0.000000
loading