Задачи
Калькулятор
Калькулятор
Имеется калькулятор, который выполняет следующие операции:
- умножить число
X
на 2; - умножить число
X
на 3; - прибавить к числу
X
единицу.
Определите, какое наименьшее количество операций требуется, чтобы получить из числа 1 число N
.
Входные данные
Во входном файле написано натуральное число N
, не превосходящее 106
.
Выходные данные
В первой строке выходного файла выведите минимальное количество операций. Во второй строке выведите числа, последовательно получающиеся при выполнении операций. Первое из них должно быть равно 1, а последнее N
. Если решений несколько, выведите любое.
Входные данные #1
1
Выходные данные #1
0 1