Автор: Демоверсия 2025
Уровень: Базовый
Условие задачи:
Определите, какова сумма протяжённостей дорог из пункта D в пункт G и из пункта A в пункт C.
Теоретическая справка:
Представленный код решения выполняет тривиальный перевод всех вариантов, таким образом, в любой задаче мы сможем найти сопоставление вершин графа. В данном случае нужно заметить, что длина DG получилась равной 8, а длина AC — 30.
Код решения:
Комментарии к коду:
- from itertools import permutations
Импортируем функцию permutations из модуля itertools, которая позволяет генерировать все возможные перестановки элементов. - table = '14 15 17 24 26 35 36 37 41 42 51 53 56 62 63 65 71 73'
Задаем строку table, которая содержит пары чисел, разделенных пробелами. - graph = 'AB BA AC CA EC CE CG GC EF FE FG GF FD DF DG GD DB BD'
Задаем строку graph, которая содержит пары букв, разделенных пробелами, представляющих связи в графе. - for per in permutations('ABCDEFG'):
Проходим по всем возможным перестановкам букв 'A', 'B', 'C', 'D', 'E', 'F', 'G'. - new_table = table
Создаем копию строки table, которая будет изменяться в процессе. - for i in range(1, 7+1):
Проходим по числам от 1 до 7 включительно (индексам элементов строки per). - new_table = new_table.replace(str(i), per[i-1])
Заменяем все вхождения числа i в строке new_table на соответствующую букву перестановки per. - if set(new_table.split()) == set(graph.split()):
Сравниваем множества пар из new_table и graph. Если они совпадают, то: - print('1 2 3 4 5 6 7')
Печатаем строку с числами от 1 до 7. - print(*per)
Печатаем текущую перестановку букв 'A', 'B', 'C', 'D', 'E', 'F', 'G', разделяя их пробелами.
