Задача № 160
На рисунке схема дорог N-ского района изображена в виде графа, в таблице звёздочкой обозначено наличие дороги между населёнными пунктами. Отсутствие звёздочки означает, что дороги нет.
| Номер пункта | ||||||||
|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | ||
| Номер пункта | 1 | \( * \) | \( * \) | \( * \) | ||||
| 2 | \( * \) | \( * \) | ||||||
| 3 | \( * \) | \( * \) | ||||||
| 4 | \( * \) | \( * \) | ||||||
| 5 | \( * \) | \( * \) | \( * \) | |||||
| 6 | \( * \) | \( * \) | \( * \) | |||||
| 7 | \( * \) | \( * \) | \( * \) | |||||
Каждому населённому пункту на схеме соответствует номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам G и D на схеме. В ответе запишите номера этих пунктов в порядке возрастания без пробелов и знаков препинания.
ЕГКР 27 апреля 2024 года (Московский пробник)
Прокрути, чтобы прочитать решение задачи
Ты уверен, что хочешь это сделать?
Удачного чтения!
Решение
Код из видео
# подключаем стандартные библиотеки
from itertools import permutations
# записываем все связи из таблицы и графа
table = '12 14 16 21 26 35 37 41 45 53 54 57 61 62 67 73 75 76'
graph = 'gb ga bg ba be eb ef fe fc fd df dc cd cf ca ab ac ag'
# уникальные цифры и буквы, которые встречаются в таблице и на графе
numbers = sorted(set(table))
letters = set(graph)
# выводим цифры
print(*numbers)
# перебираем все перестановки букв
for perm in permutations(letters):
# копируем таблицу, чтобы заменять цифры на буквы
copy = table
# соединяем соответствующие цифры и буквы
for num, let in zip(numbers, perm):
# выполняем замену цифры на букву
copy = copy.replace(num, let)
# сравниваем множетсво графа и нами созданной таблицы
if set(copy.split()) == set(graph.split()):
# выводим, если совпадают
print(*perm)