Задание 1. Информатика. ЕГЭ. Демо-2025
- Просмотры: 376
- Изменено: 24 ноября 2024
На рисунке схема дорог \(N\)-ского района изображена в виде графа, в таблице содержатся сведения о протяженности каждой из этих дорог (в километрах).
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта \(D\) в пункт \(G\) и из пункта \(A\) в пункт \(C\).
Решение:
Python
from itertools import permutations
g1 = '1457 246 3567 412 5136 6235 713'
g2 = 'ABC BAD CAEG DFGB EFC FEGD GDFC'
d1 = {x[0]: sorted(list(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]: sorted(list(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 C B F A G D E
По таблице определяем, что расстояние \(DG = 8\) и \(AC = 30\). Значит сумма расстояний между этими пунктами равна \(8 + 30 = 38\).
Ответ: \(38\)