574 . Fibonacci Sums
Description
Fibonacci numbers are an integer sequence defined in the following way: Fib0=1, Fib1=1, Fibi=Fibi-1+Fibi-2 (for i>=2). The first few numbers in this sequence are: (1,1,2,3,5,8,...).
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 42, for instance, can be written as: 
, 
or 
. For this very reason, Byteazar has limited himself to only using representations satisfying the following conditions:
- if
, then 
, i.e. the representation of a number does not contain leading zeros. - if
, then 
(for 
), i.e. the representation of a number does not contain two (or more) consecutive ones.
The construction of the computer has proved more demanding than Byteazar supposed. He has difficulties implementing addition. Help him!
Write a programme which:
- reads from the standard input the representations of two positive integers,
- calculates and writes to the standard output the representation of their sum.
Input Format
There are multiple test cases in the input file. For each test case:
The input contains the Fibonacci representations (satisfying the aforementioned conditions) of two positive integers X and Y - one in the first, the other in the second line. Each of these representations is in the form of a sequence of positive integers, separated by single spaces. The first number in the line denotes the length of the representation N, 1<= N <= 1000000. It is followed by N zeros and/or ones.
Output Format
In the first and only line of the output your programme should write the Fibonacci representation (satisfying the aforementioned conditions) of the sum X+Y. The representation should be in the form of a sequence of positive integers, separated by single spaces, as it has been described in the Input section.
There is no need to print any blank lines between test cases.
Sample Input 1
4 0 1 0 1 5 0 1 0 0 1 1 1 1 1
Sample Output 1
6 1 0 1 0 0 1 2 0 1
Hints
Problem Source
Migrated from old NTUJ.
POI 15th Stage III
Subtasks
| No. | Testdata Range | Score |
|---|