Sumy Fibonacciego
Limit pamięci: 32 MB
Liczby Fibonacciego to ciąg liczb całkowitych zdefiniowany następująco:
, ,
(dla ).
Oto kilka pierwszych wyrazów tego ciągu: .
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 reprezentuje liczbę
.
(Zwróć uwagę, że nie korzystamy z ).
Taka reprezentacja liczb nie jest niestety jednoznaczna, tzn. tę samą
liczbę można reprezentować na wiele sposobów.
Na przykład, liczbę można reprezentować jako:
,
lub
.
Dlatego też Bajtazar ograniczył się wyłącznie do reprezentacji
spełniających następujące warunki:
-
jeżeli , to , czyli reprezentacja liczby nie
zawiera wiodących zer,
-
jeżeli , to (dla ),
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 i -
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 ,
.
Po niej następuje 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 .
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 ,
.
Po niej następuje zer i/lub jedynek.
Przykład
Dla danych wejściowych:
4 0 1 0 1
5 0 1 0 0 1
poprawną odpowiedzią jest:
6 1 0 1 0 0 1
Autor zadania: Marcin Kubica.