№1 · решено
Сумма дорог D–A и B–F
На рисунке схема дорог изображена в виде графа, в таблице — длины этих дорог в километрах. Таблицу и схему рисовали независимо, поэтому нумерация пунктов в таблице никак не связана с буквами на графе. Определите, какова сумма длин дорог из пункта D в пункт A и из пункта B в пункт F. В ответе запишите целое число.
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | П8 | |
|---|---|---|---|---|---|---|---|---|
| П1 | 30 | 2 | 1 | |||||
| П2 | 74 | 39 | ||||||
| П3 | 74 | 8 | 53 | |||||
| П4 | 8 | 13 | 3 | |||||
| П5 | 30 | 21 | 5 | |||||
| П6 | 2 | 13 | 21 | |||||
| П7 | 1 | 3 | ||||||
| П8 | 39 | 53 | 5 |
Источник: ФИПИ (пересдача 08.07.2026), № 31347
Ответвпиши то, что вывела программа
Показать разбор
- Выпиши дороги со схемы парами букв в roads, их тут 11. Проверь: в таблице столько же дорог.
- Для каждой строки таблицы запиши номера соседей в conns, а сами длины перенеси в lens, пустые клетки замени нулём.
- Перебери все расстановки букв по номерам через permutations и оставь те, где каждая дорога есть в таблице.
- В подходящей расстановке найди номера нужных букв через p.index и возьми из lens сумму длин дорог D–A и B–F.
- Расстановок может быть несколько, если схема симметричная. Складывай результат в множество: ответ у них должен быть один.
from itertools import permutations
roads = 'AD AE AH BC BE BF CH DF DG EH FG'.split()
conns = ['567', '38', '248', '367', '168', '145', '14', '235']
lens = [
[0, 0, 0, 0, 30, 2, 1, 0],
[0, 0, 74, 0, 0, 0, 0, 39],
[0, 74, 0, 8, 0, 0, 0, 53],
[0, 0, 8, 0, 0, 13, 3, 0],
[30, 0, 0, 0, 0, 21, 0, 5],
[2, 0, 0, 13, 21, 0, 0, 0],
[1, 0, 0, 3, 0, 0, 0, 0],
[0, 39, 53, 0, 5, 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('D')][p.index('A')] + lens[p.index('B')][p.index('F')])
print(*ans)