W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Fibonacci numbers are an integer sequence defined in the following way: , , (for ). The first few numbers in this sequence are: ().
The great computer scientist Byteazar is constructing an unusual computer, in which numbers are represented in Fibonacci system i.e. a bit string denotes the number . (Note that we do not use .) Unfortunately, such a representation is ambiguous i.e. the same number can have different representations. The number , for instance, can be written as: , or . For this very reason, Byteazar has limited himself to only using representations satisfying the following conditions:
The construction of the computer has proved more demanding than Byteazar supposed. He has difficulties implementing addition. Help him!
Write a programme which:
The input contains the Fibonacci representations (satisfying the aforementioned conditions) of two positive integers and - one in the first, the other in the second line. Each of these representations is in the form of a sequence of non-negative integers, separated by single spaces. The first number in the line denotes the length of the representation , . It is followed by zeros and/or ones.
In the first and only line of the output your programme should write the Fibonacci representation (satisfying the aforementioned conditions) of the sum . The representation should be in the form of a sequence of non-negative integers, separated by single spaces, as it has been described in the Input section. The first number in the line denotes the length of the representation , . It is followed by zeros and/or ones.
For the input data:
4 0 1 0 1 5 0 1 0 0 1
the correct result is:
6 1 0 1 0 0 1
Task author: Marcin Kubica.