Задание 1. Информатика. ЕГЭ. 2024. Пересдача
- Просмотры: 164
- Изменено: 24 ноября 2024
На рисунке справа схема дорог \(N\)-ского района изображена в виде графа, в таблице содержатся сведения о протяженности каждой из этих дорог (в километрах).
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите сумму протяжённостей дорог из пункта \(C\) в пункт \(A\) и из пункта \(B\) в пункт \(D\). В ответе запишите целое число.
Решение:
Python
from itertools import permutations
g1 = '136 2567 314 4367 527 6124 7245'
g2 = 'ABCE BADF CADG DGCB EAF FBE GCD'
d1 = {x[0]: set(x[1:]) for x in g2.split()}
for p in permutations('ABCDEFG'):
t = g1
for x, y in zip('1234567', p):
t = t.replace(x, y)
d2 = {x[0]: set(x[1:]) for x in t.split()}
if d1 == d2:
print('1 2 3 4 5 6 7')
print(*p)
Вывод программы:
1 2 3 4 5 6 7 E C F B G A D 1 2 3 4 5 6 7 F D E A G B C
Граф дорог обладает осевой симметрией, поэтому здесь два варианта расстановки букв. Выбираем первый. Тогда \(CA = 13\) и \(BD = 2\) и сумма протяжённостей дорог будет \(13 + 2 = 15\).
Ответ: \(15\)