Условие: Тип 1 № 58468
• Статья подготовлена командой itpy
• Полный разбор задачи в Notion
На рисунке схема дорог изображена в виде графа, в таблице звёздочками обозначено наличие дороги между населёнными пунктами. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Выпишите последовательно без пробелов и знаков препинания указанные на графе буквенные обозначения пунктов от П1 до П8: сначала букву, соответствующую П1, затем букву, соответствующую П2, и т. д.
Решение через Python и комментарии к нему:
💡 Комментарии к коду решения:
- from itertools import permutations - Импортируем функцию permutations из модуля itertools для генерации перестановок получаемого алфавита.
- table = '14 17 18 23 25 26 32 34 38 41 43 47 48 52 56 58 62 65 71 74 81 83 84 85' - По таблице из условия составляем строку всех возможных дорог (туда и обратно).
- graph = 'АБ БА АИ ИА ИБ БИ ИЖ ЖИ БЖ ЖБ БВ ВБ ВЖ ЖВ ВГ ГВ ЖЕ ЕЖ ЕГ ГЕ ДГ ГД ЕД ДЕ' - Аналогично делаем для графа с буквенными вершинами.
- for per in permutations('АБВГДЖИЕ'): - Через permutations получаем все возможные перестановки символов 'АБВГДЖИЕ'.
- new_table = table - Инициализируем переменную new_table с текущим значением table.
- for i in range(1, 8+1): - Будем пробегать все числовые вершины из таблицы.
- new_table = new_table.replace(str(i), per[i-1]) - И заменяем числа в строке new_table на символы из текущей перестановки per.
- if set(new_table.split()) == set(graph.split()): - Проверяем, получившиеся наборы дорог совпадают через множества элементов строк new_table и graph.
- print('1 2 3 4 5 6 7 8') - Вывод числовой набор вершин.
- print(*per) - И выводим текущую перестановку, которая соответствует графу.