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

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

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

ABCDEFGH
П1П2П3П4П5П6П7П8
П1152412
П21513
П31843
П4941
П5241839
П643937
П71337
П8124139

Источник: ФИПИ (демоверсия), № 23738

Ответвпиши то, что вывела программа
Показать разбор
  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 = ['258', '17', '56', '68', '138', '347', '26', '145']
lens = [
    [0, 15, 0, 0, 24, 0, 0, 12],
    [15, 0, 0, 0, 0, 0, 13, 0],
    [0, 0, 0, 0, 18, 43, 0, 0],
    [0, 0, 0, 0, 0, 9, 0, 41],
    [24, 0, 18, 0, 0, 0, 0, 39],
    [0, 0, 43, 9, 0, 0, 37, 0],
    [0, 13, 0, 0, 0, 37, 0, 0],
    [12, 0, 0, 41, 39, 0, 0, 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)