0У
Все задачи №1
№1

Сумма дорог G–E и F–H

На рисунке схема дорог изображена в виде графа, в таблице — длины этих дорог в километрах. Таблицу и схему рисовали независимо, поэтому нумерация пунктов в таблице никак не связана с буквами на графе. Определите, какова сумма длин дорог из пункта G в пункт E и из пункта F в пункт H. В ответе запишите целое число.

ABCDEFGH
П1П2П3П4П5П6П7П8
П114829
П21527
П3141517
П42713
П52312
П681723
П7131219
П82919

Источник: ФИПИ (ЕГКР 13.12.2025), № 25340

Ответвпиши то, что вывела программа
Показать разбор
  1. Выпиши дороги со схемы парами букв в roads, их тут 10. Проверь: в таблице столько же дорог.
  2. Для каждой строки таблицы запиши номера соседей в conns, а сами длины перенеси в lens, пустые клетки замени нулём.
  3. Перебери все расстановки букв по номерам через permutations и оставь те, где каждая дорога есть в таблице.
  4. В подходящей расстановке найди номера нужных букв через p.index и возьми из lens сумму длин дорог G–E и F–H.
  5. Расстановок может быть несколько, если схема симметричная. Складывай результат в множество: ответ у них должен быть один.
from itertools import permutations

roads = 'AC AD AG BC BH CG DH EF EG FH'.split()
conns = ['368', '34', '126', '27', '67', '135', '458', '17']
lens = [
    [0, 0, 14, 0, 0, 8, 0, 29],
    [0, 0, 15, 27, 0, 0, 0, 0],
    [14, 15, 0, 0, 0, 17, 0, 0],
    [0, 27, 0, 0, 0, 0, 13, 0],
    [0, 0, 0, 0, 0, 23, 12, 0],
    [8, 0, 17, 0, 23, 0, 0, 0],
    [0, 0, 0, 13, 12, 0, 0, 19],
    [29, 0, 0, 0, 0, 0, 19, 0],
]

ans = set()
for p in permutations('ABCDEFGH'):
    if all(str(p.index(x) + 1) in conns[p.index(y)] for x, y in roads):
        ans.add(lens[p.index('G')][p.index('E')] + lens[p.index('F')][p.index('H')])
print(*ans)