Задание 1. Информатика. ЕГЭ. Статград. 01.04.2025-1
- Просмотры: 523
- Изменено: 1 апреля 2025
На рисунке схема дорог N-ского района изображена в виде графа, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
|
 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Каждому населённому пункту на схеме соответствует номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам C и E на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
Решение:
Python
from itertools import permutations
graph = {'A': set('BCF'),
'B': set('AC'),
'C': set('ABE'),
'D': set('EFG'),
'E': set('CDG'),
'F': set('AD'),
'G': set('ED')}
templ = {1: [4, 5],
2: [3, 4, 7],
3: [2, 7],
4: [1, 2, 5],
5: [1, 4, 6],
6: [5, 7],
7: [2, 3, 6]}
for p in permutations('ABCDEFG'):
chk = {p[k-1]: set([p[i-1] for i in v]) for k, v in templ.items()}
if chk == graph:
print('1 2 3 4 5 6 7')
print(*p)
Вывод программы
1 2 3 4 5 6 7 B E G C A F D 1 2 3 4 5 6 7 G C B E D F A
Ответ: \(24\)