Dimka621

10.02.2021 06:30 •  Информатика

Задача 4: Тайна Карбофоса Все секреты известного международного преступника и контрабандиста Карбофоса хранятся в его чемодане. Чемодан оборудован специальным замком, состоящим из девяти ручек, каждая из которых может быть либо в горизонтальном, либо в вертикальном положении.

Для того, чтобы открыть чемодан, нужно привести все ручки в горизонтальное положение, но сделать это не так просто, как кажется: каждая из ручек при повороте также поворачивает несколько других.

Двум известным сыщикам, действующим под кодовыми именами «Шеф» и «Коллега», удалось найти схему, определяющую связь ручек:

1:6 9,
2:3 8,
3:6 7 9,
4:2 3,
5:1 4 6,
6:2 7,
7:4 5 8,
8:3 9,
9:1 4.
Таким образом, поворот ручки с номером 1 автоматически повернет ручки 6 и 9, при этом дальнейшие (рекурсивные) повороты ручек, зависящих от 6 и 9, не выполняются. Аналогично поворот ручки с номером 2 приведет к повороту только ручек 3 и 8 и так далее. Начальное положение ручек представлено на рисунке: ручки с номерами 2, 3, 5, 7, 9 находятся в вертикальном положении.

В ответе запишите последовательность номеров ручек, которые нужно повернуть, чтобы наибольшее количество ручек на чемодане оказались в горизонтальном положении. При этом ваша последовательность должна содержать как можно меньше чисел. Числа в последовательности разделяйте пробелами.