Задание 1. Информатика. ЕГЭ. Статград. 17.12.2024-1
- Просмотры: 2345
- Изменено: 18 января 2025
На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.
|
 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что дорога АГ короче дороги ГД. Определите длину дороги ЖИ.
Решение:
Python
from itertools import permutations
graph = {'А': set('БГ'),
'Б': set('АВ'),
'В': set('БГЕ'),
'Г': set('АВДЖ'),
'Д': set('ГЕ'),
'Е': set('ВДЖК'),
'Ж': set('ГЕИ'),
'И': set('ЖК'),
'К': set('ИЕ'),}
templ = {1: [2, 8],
2: [1, 4, 6, 7],
3: [5, 9],
4: [2, 9],
5: [3, 7],
6: [2, 8, 9],
7: [2, 5, 9],
8: [1, 6],
9: [3, 4, 6, 7]}
for p in permutations('АБВГДЕЖИК'):
chk = {p[k - 1]: set([p[i - 1] for i in v]) for k, v in templ.items()}
if chk == graph:
print('1 2 3 4 5 6 7 8 9')
print(*p)
Вывод программы:
1 2 3 4 5 6 7 8 9 А Г К Д И В Ж Б Е 1 2 3 4 5 6 7 8 9 К Е А Д Б Ж В И Г
Для первого случая длина АГ равно 21, а ГД — 15. Он не подходит нам. Во втором случае длина АГ равна 17, а ГД — 18, т.е. удовлетворяет условию задачи. Значит длина ЖИ равна 16.
Ответ: \(16\)