Polish version    English version  
  O olimpiadzie -> Zadania


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN

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.





Wersja do druku