Олимпиадный тренинг

Задача . Красивая последовательность (пример кратчайшей)


Назовём конечную последовательность натуральных чисел красивой, если она начинается с единицы и каждый её член, кроме первого, больше предыдущего на 1, на 7 или в 2 раза. Последовательность, состоящая из одной единицы, также является красивой.

Напишите программу, находящую наименьшую возможную длину красивой последовательности, заканчивающейся числом \(n\), а также приводящую пример такой последовательности наименьшей длины.

Формат входных данных

На вход программе подаётся единственное натуральное число \(n\). Гарантируется, что \(1\leqslant n\leqslant 10^5\).

Формат выходных данных

Программа должна вывести в первой строке единственное натуральное число — наименьшую возможную длину красивой последовательности, заканчивающейся числом \(n\).

Затем во второй строке программа должна вывести через пробел элементы красивой последовательности, являющейся примером, то есть имеющей выведенную выше длину и заканчивающейся числом \(n\).


Примеры
№Входные данныеВыходные данные
1
1
1
1
2
2
2
1 2
3
9
3
1 2 9
4
128
6
1 8 16 32 64 128
Статистика успешных решений по компиляторам
 Кол-во
Python45
С++4