#P3424. [POI 2005] SUM-Fibonacci Sums

[POI 2005] SUM-Fibonacci Sums

题目描述

Fibonacci numbers are an integer sequence defined in the following way: Fib0=1Fib_0=1, Fib1=1Fib_1=1, Fibi=Fibi1+Fibi2Fib_i=Fib_{i-1}+Fib_{i-2} (for i2i\ge 2). The first few numbers in this sequence are: (1,1,2,3,5,8,1,1,2,3,5,8,\cdots).

The great computer scientist Byteazar is constructing an unusual computer, in which numbers are represented in Fibonacci system i.e. a bit string (b1,b2,,bn)(b_1,b_2,\cdots,b_n) denotes the number $b_1\cdot Fib_1+b_2\cdot Fib_2+\cdots+b_n\cdot Fib_n$. (Note that we do not use Fib0Fib_0.) Unfortunately, such a representation is ambiguous i.e. the same number can have different representations. The number 4242, for instance, can be written as: (0,0,0,0,1,0,0,1)(0,0,0,0,1,0,0,1), (0,0,0,0,1,1,1,0)(0,0,0,0,1,1,1,0) or (1,1,0,1,0,1,1)(1,1,0,1,0,1,1). For this very reason, Byteazar has limited himself to only using representations satisfying the following conditions:

if n>1n>1, then bn=1b_n=1, i.e. the representation of a number does not contain leading zeros.

if bi=1b_i=1, then bi+1=0b_{i+1}=0 (for i=1,,n1i=1,\cdots,n-1), 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!

TaskWrite 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.

输入格式

The input contains the Fibonacci representations (satisfying the aforementioned conditions) of two positive integers xx and yy - 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 nn, 1n1 000 0001\le n\le 1\ 000\ 000. It is followed by nn 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 x+yx+y. 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 nn, 1n1 000 0001\le n\le 1\ 000\ 000. It is followed by nn zeros and/or ones.

4 0 1 0 1
5 0 1 0 0 1
6 1 0 1 0 0 1