Задача №3582. Фибоначчиева система счисления
Напомним, что числами Фибоначчи называется последовательность чисел, получаемая по следующему правилу: f0 = f1 = 1, fk = fk - 1 + fk - 2, где k > 1.
Фибоначчиева система счисления (ФСС) — это позиционная система счисления с алфавитом, состоящим из двух цифр: 0 и 1, а ее базисом является последовательность чисел Фибоначчи 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... (f0 = 1 в базис не включается). В фибоначчиевой системе, как и во всех позиционных системах счисления, «вес» каждого разряда определяется соответствующим элементом базиса этой системы. Так, 10011fib = 1 × 8 + 0 × 5 + 0 × 3 + 1 × 2 + 1 × 1 = 11. Если не наложить дополнительных ограничений, то представление чисел в такой системе счисления оказывается неоднозначным.
Например, 1110 = 1111fib = 10011fib = 10100fib
Требуется написать программу, которая для натурального числа N будет выводить все его представления в ФСС. Если полученные представления рассматривать как двоичные числа, то выводить их надо в порядке возрастания — от меньшего числа к большему.
Во входном файле записано единственное число N (1 ≤ N ≤ 2 × 109).
В выходной файл требуется вывести все представления числа N в ФСС по одному на каждой строке, упорядоченные по возрастанию значений соответствующих этим представлениям двоичных чисел.
5
110 1000
11
1111 10011 10100