Иван-царевич (И.) сражается с N-головым
Змеем Горынычем (З.Г.). З.Г. неагрессивный (видимо, сытый). За 1 удар И. может
снести мечом 1 или 2 головы, но взамен отрубленной тут же вырастают 2 новых.
Однако если после очередного раунда количество голов З.Г. становится кратным 3,
среди них начинаются конфликты, головы взаимооткусываются
и их становится втрое меньше. При этом если их число снова останется кратным 3,
процесс взаимооткусывания повторится. Например, если
N=7, И. может первым ударом снести 2 головы, отрастут 4 новые, голов станет 9,
они превратятся в 3 а затем в 1, и вторым ударом И.
победит.
Требуется разработать программу, которая вводит натуральное
N и выводит самую короткую последовательность «ходов», приводящую И. к победе.
Например, при N=7 она должна вывести 21, а при N=11 – 122. Если таких
последовательностей несколько, выводится та, что «меньше»: например, для N=77 выводится 111, а не 221.
Ввод: единственное
число N
Вывод: последовательность
“ходов” (“наименьшая” из кратчайших)
Для отправки решений необходимо