Задание 1. Информатика. ЕГЭ. Поляков-7618
- Просмотры: 209
- Изменено: 24 ноября 2024
(М. Шагитов) На рисунке справа схема дорог \(N\)-ского района изображена в виде графа, в таблице содержатся сведения о протяженности каждой из этих дорог (в километрах).
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта \(C\) в пункт \(D\), из пункта \(D\) в пункт \(G\) и из пункта \(G\) в пункт \(C\). В ответе запишите целое число.
Решение:
Python
from itertools import permutations
g1 = '123467 21356 312458 413 5238 6127 716 835'
g2 = 'ABC BACD CABDGH DBCGE EDGF FGE GCDEFH HCG'
d1 = {x[0]: set(x[1:]) for x in g2.split()}
for p in permutations('ABCDEFGH'):
t = g1
for x, y in zip('12345678', 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 8')
print(*p)
Вывод программы:
1 2 3 4 5 6 7 8 C D G H E B A F 1 2 3 4 5 6 7 8 G D C H B E F A
Так как граф обладает симметрией, то в выводе программы получили два альтернативных обозначения дорог. Выбираем, например, первый. Тогда \(CD = 10\), \(DG = 50\), \(GC = 60\). В сумме \(10 + 50 + 60 = 120\).
Ответ: \(120\)