№1 · решено
Сумма дорог B–C и A–C
На рисунке схема дорог изображена в виде графа, в таблице — длины этих дорог в километрах. Таблицу и схему рисовали независимо, поэтому нумерация пунктов в таблице никак не связана с буквами на графе. Определите, какова сумма длин дорог из пункта B в пункт C и из пункта A в пункт C. В ответе запишите целое число.
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | |
|---|---|---|---|---|---|---|---|
| П1 | 8 | 5 | 3 | ||||
| П2 | 39 | 53 | 21 | ||||
| П3 | 8 | 39 | 30 | ||||
| П4 | 53 | 30 | 2 | ||||
| П5 | 13 | 1 | |||||
| П6 | 5 | 21 | 13 | ||||
| П7 | 3 | 2 | 1 |
Источник: ФИПИ (резервный день 22.06.2026), № 31209
Ответвпиши то, что вывела программа
Показать разбор
- Выпиши дороги со схемы парами букв в roads, их тут 10. Проверь: в таблице столько же дорог.
- Для каждой строки таблицы запиши номера соседей в conns, а сами длины перенеси в lens, пустые клетки замени нулём.
- Перебери все расстановки букв по номерам через permutations и оставь те, где каждая дорога есть в таблице.
- В подходящей расстановке найди номера нужных букв через p.index и возьми из lens сумму длин дорог B–C и A–C.
- Расстановок может быть несколько, если схема симметричная. Складывай результат в множество: ответ у них должен быть один.
from itertools import permutations
roads = 'AC AD AF BC BE BF CG DE DG EG'.split()
conns = ['367', '346', '124', '237', '67', '125', '145']
lens = [
[0, 0, 8, 0, 0, 5, 3],
[0, 0, 39, 53, 0, 21, 0],
[8, 39, 0, 30, 0, 0, 0],
[0, 53, 30, 0, 0, 0, 2],
[0, 0, 0, 0, 0, 13, 1],
[5, 21, 0, 0, 13, 0, 0],
[3, 0, 0, 2, 1, 0, 0],
]
ans = set()
for p in permutations('ABCDEFG'):
if all(str(p.index(x) + 1) in conns[p.index(y)] for x, y in roads):
ans.add(lens[p.index('B')][p.index('C')] + lens[p.index('A')][p.index('C')])
print(*ans)