Задание 1. Информатика. ЕГЭ. Апробация. 05.03.2025

Просмотры: 2152
Изменено: 5 марта 2025

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

Номер пункта
1234567
1 2158
2 321
3 3913
42139 30
55313 
6220 53
78153 
 

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

Решение:

Python


from itertools import permutations

graph = {'A': set('BDF'),
         'B': set('ACG'),
         'C': set('BDE'),
         'D': set('ACF'),
         'E': set('CFG'),
         'F': set('ADE'),
         'G': set('BE')}

templ = {1: [4, 5, 7],
         2: [5, 6, 7],
         3: [4, 5],
         4: [1, 3, 6],
         5: [1, 2, 3],
         6: [2, 4, 7],
         7: [1, 2, 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
C A G E B F D
1 2 3 4 5 6 7
C F G B E A D

Отсюда \(FA = 2,\) \(CD = 8.\)

Ответ: \(10\)