На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам Б и В на схеме. В ответ запишите без разделителей сначала номер пункта Б, потом номер пункта В.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 1 | * | * | * | |||||
| 2 | * | * | ||||||
| 3 | * | * | * | |||||
| 4 | * | * | * | |||||
| 5 | * | * | * | |||||
| 6 | * | * | * | |||||
| 7 | * | * | ||||||
| 8 | * | * | * |
Заметим, что пункты К и Ж имеют степень 2. Значит, им соответствуют номера
Ответ: 14.
Приведём решение Данила Шарлова на языке Python.
from itertools import permutations
table = '568 36 247 368 178 124 35 145'.split()
graph = {
'А': ['Б', 'Г', 'Ж'],
'Б': ['А', 'Г', 'Е'],
'В': ['Г', 'Е', 'Д'],
'Г': ['А', 'Б', 'В'],
'Д': ['В', 'К', 'Ж'],
'Е': ['Б', 'В', 'К'],
'Ж': ['А', 'Д'],
'К': ['Е', 'Д']
}
print('1 2 3 4 5 6 7 8')
for perm in permutations(graph.keys()):
indices = {node: str(i + 1) for i, node in enumerate(perm)}
if all(len(graph[node]) == len(table[i]) for i, node in enumerate(perm)) and all(indices[neighbor] in table[i] for i, node in enumerate(perm) for neighbor in graph[node]):
print(' '.join(perm))
break