Задание 1. Информатика. ЕГЭ. Шастин. 19.09.2024

Просмотры: 163
Изменено: 24 ноября 2024

(Л. Шастин) На рисунке справа схема дорог \(N\)-ского района изображена в виде графа, в таблице содержатся сведения о протяженности каждой из этих дорог (в километрах).

Номер пункта
1 2 3 4 5 6 7 8
1   53 1 2
2 53   13 8
3   30 39 74
4 1 13   5
5 30   3
6 5   21
7 2 39 21  
8 8 74 3  
 

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённости дорого из пункта \(G\) в пункт \(F\) и из пункта \(A\) в пункт \(H\). В ответе запишите целое число.

Решение:

Python


from itertools import permutations

g1 = '1247 2148 3578 4126 538 647 7136 8235'
g2 = 'ABHE BAH CEGD DCF EACG FDGH GCEF HABF'

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
G E H C B D F A

\(GF=2\), \(AH=74\). Сумма протяжённости дорог \(2 + 74 = 76\).

Ответ: \(76\)