На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | |
| П1 | 4 | 5 | |||||
| П2 | 4 | 8 | 9 | 6 | |||
| П3 | 10 | 7 | |||||
| П4 | 11 | ||||||
| П5 | 8 | 11 | 12 | ||||
| П6 | 9 | 10 | 12 | 13 | |||
| П7 | 5 | 6 | 7 | 13 |
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта В в пункт Д. В ответе запишите целое число — так, как оно указано в таблице.
Пункт А — единственный пункт с одной дорогой, значит, ему соответствует П4.
С пунктом А имеет общую дорогу пункт Б, следовательно, пункт Б это пункт П5.
Пункт Б имеет общие дороги с пунктами В и Д, тогда пунктам В и Д соответствуют пункты П2 и П6. Тогда длинна дороги из пункта В в пункт Д равна длине П2-П6 и равна 9.
Ответ: 9.
Приведём решение Александра Козлова на языке Python.
from itertools import *
s = '27 1567 67 5 246 2357 12367'.split()
v = 'АБ БВ БД ВД ВГ ВЕ ДЕ ДК ГЕ ЕК'.split()
print(*range(1,8))
for p in permutations('АБВГДЕК'):
for x,y in v:
i,j = p.index(x), p.index(y)
if str(j+1) not in s[i]:
break
else:
print(*p)
Приведём другое решение Александра Козлова на языке Python.
from itertools import *
s = '27 1567 67 5 246 2357 12367'.split()
v = 'АБ БВ БД ВД ВГ ВЕ ДЕ ДК ГЕ ЕК'.split()
print(*range(1,8))
for p in permutations('АБВГДЕК'):
if all(str(p.index(b)+1) in s[p.index(a)] for a,b in v):
print(*p)