Zadanie: Sumy Fibonacciego
Liczby Fibonacciego to ciąg liczb całkowitych zdefiniowany następująco:
Fib0 = 1,
Fib1 = 1,
Fibi = Fibi-2 + Fibi-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
(b1, b2,..., bn) reprezentuje liczbę
b1 . Fib1 + b2 . Fib2 + ... + bn . Fibn.
(Zwróć uwagę, że nie korzystamy z
Fib0.)
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 bn = 1, czyli reprezentacja liczby nie
zawiera wiodących zer,
- jeżeli bi = 1, to
bi+1 = 0 (dla
i = 1,..., n - 1),
czyli reprezentacja liczby nie zawiera dwóch (lub więcej)
jedynek obok siebie.
Konstrukcja komputera okazała się trudniejsza, niż Bajtazar myślał.
Ma on problemy z zaimplementowaniem dodawania.
Pomóż mu!
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia reprezentacje dwóch dodatnich
liczb całkowitych,
- obliczy i wypisze reprezentację ich sumy na standardowe wyjście.
Wejście
Na wejściu znajdują się reprezentacje Fibonacciego
(spełniające podane powyżej warunki)
dwóch dodatnich liczb całkowitych x i y --
jedna w pierwszym, a druga w drugim wierszu.
Każda z tych reprezentacji jest zapisana jako ciąg nieujemnych liczb
całkowitych, pooddzielanych pojedynczymi odstępami.
Pierwsza liczba w wierszu to długość reprezentacji n,
1 <= n <= 1 000 000.
Po niej następuje n zer i/lub jedynek.
Wyjście
W pierwszym i jedynym wierszu wyjścia, Twój program powinien wypisać
reprezentację Fibonacciego (spełniającą podane powyżej warunki)
sumy x + y.
Tak jak to opisano dla wejścia, reprezentacja powinna mieć postać
ciągu nieujemnych liczb
całkowitych, pooddzielanych pojedynczymi odstępami.
Pierwsza liczba w wierszu to długość reprezentacji n,
1 <= n <= 1 000 000.
Po niej następuje n zer i/lub jedynek.