Задание №1. Графы и таблицы: кто есть кто на карте

Что от тебя хотят

Есть схема дорог с буквами А, Б, В... и таблица с пунктами П1, П2, П3... Рисовали их независимо, поэтому номера в таблице никак не связаны с буквами на схеме. Это как два паспорта на одного человека, где в одном написано имя, а в другом только номер. Твоя задача: понять, кто есть кто, и достать из таблицы число.

Идея: у каждого пункта есть «паспорт»

Степень вершины — это число дорог, которые из неё выходят. На схеме её видно по отрезкам у буквы, а в таблице это количество заполненных клеток в строке. Одно и то же место на двух рисунках всегда даёт одну и ту же степень, и за это можно зацепиться.

Алгоритм из четырёх шагов

1. Посчитай степени всех букв на схеме и всех строк в таблице. Запиши рядом.
2. Найди одиночек: степень, которая встречается один раз. Такие пункты определяются сразу.
3. Разбери одинаковых по соседям. Если у двух пунктов одинаковая степень, посмотри, с кем они соединены. Опирайся на уже найденных.
4. Прочитай ответ на пересечении нужной строки и столбца. Перед этим ещё раз перечитай вопрос.

Разбор на живом примере

Схема дорог и таблица описывают один и тот же район. На схеме дороги такие: А–Б, А–В, А–Е, А–Ж, В–Г, В–Ж, Г–Д, Г–Е, Д–Е. В таблице указаны длины дорог в километрах. Определите длину дороги между пунктами Г и Д.

1. Степени на схеме: А — 4, Б — 1, В — 3, Г — 3, Д — 2, Е — 3, Ж — 2. В таблице: П1 — 3, П2 — 2, П3 — 4, П4 — 2, П5 — 3, П6 — 1, П7 — 3.
2. Одиночки: степень 4 только у А и у П3, значит А = П3. Степень 1 только у Б и у П6, значит Б = П6.
3. Две двойки: Ж и Д на схеме, П2 и П4 в таблице. Ж соединён с А, а из двух пунктов только П4 соединён с П3. Значит Ж = П4, а Д = П2.
4. У Ж ещё один сосед, это В. В строке П4 вторая клетка стоит в столбце П1, значит В = П1.
5. Соседи Д — это Г и Е, в таблице у П2 это П5 и П7. Е соединён с А (П3), и из этих двух с П3 соединён П7. Значит Е = П7, а Г = П5.
6. Нужна дорога Г–Д, то есть П5–П2. На пересечении стоит 4.

Ответ: 4. Я проверил этот пример перебором всех 5040 раскладок букв по номерам: подходит одна, и ответ в ней такой же.