Zadanie: Sumy Fibonacciego

Liczby Fibonacciego to ciąg liczb całkowitych zdefiniowany następująco: Fib₀ = 1, Fib₁ = 1, Fib_i = Fib_i-2 + Fib_i-1 (dla i >= 2). Oto kilka pierwszych wyrazów tego ciągu: (1, 1, 2, 3, 5, 8,...).

Wielki informatyk Bajtazar konstruuje niezwykły komputer. Liczby w tym komputerze są reprezentowane w układzie Fibonacciego. Liczby w takim układzie są reprezentowane jako ciągi zer i/lub jedynek (bitów), ciąg (b₁, b₂,..., b_n) reprezentuje liczbę b₁ ^. Fib₁ + b₂ ^. Fib₂ + ^... + b_n ^. Fib_n. (Zwróć uwagę, że nie korzystamy z Fib₀.) Taka reprezentacja liczb nie jest niestety jednoznaczna, tzn. tę samą liczbę można reprezentować na wiele sposobów. Na przykład, liczbę 42 można reprezentować jako: (0, 0, 0, 0, 1, 0, 0, 1), (0, 0, 0, 0, 1, 1, 1, 0) lub (1, 1, 0, 1, 0, 1, 1). Dlatego też Bajtazar ograniczył się wyłącznie do reprezentacji spełniających następujące warunki:

• jeżeli n > 1, to b_n = 1, czyli reprezentacja liczby nie zawiera wiodących zer,
• jeżeli b_i = 1, to b_i+1 = 0 (dla i = 1,..., n - 1), czyli reprezentacja liczby nie zawiera dwóch (lub więcej) jedynek obok siebie.

Zadanie

• wczyta ze standardowego wejścia reprezentacje dwóch dodatnich liczb całkowitych,
• obliczy i wypisze reprezentację ich sumy na standardowe wyjście.

Wejście

Wyjście

Wersja do druku