1 人解决，7 人已尝试。
1 份提交通过，共有 54 份提交。
9.9 EMB 奖励。
单点时限: 5.0 sec
内存限制: 256 MB
Fibbonacci numbers are an integer sequence defined in the following way: Fib0 = 1, Fib1 = 1, Fibi = Fibi-2 + Fibi-1 (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 Fibbonacci system i.e. a bit string (b1, b2,…, bn) denotes the number b1 . Fib1 + b2 . Fib2 + … + bn . Fibn. (Note that we do not use Fib0.) Unfortunatelly, such a representation is ambiguous i.e. the same number can have different representations. The number 42, for instance, can be written as: (0, 0, 0, 0, 1, 0, 0, 1), (0, 0, 0, 0, 1, 1, 1, 0) or (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 > 1, then bn = 1, i.e. the representation of a number does not contain leading zeros.
if bi = 1, then bi+1 = 0 (for i = 1,…, 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!
Task
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.
The input contains the Fibbonacci represantations (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 <= 1 000 000. It is followed by n zeros and/or ones.
In the first and only line of the output your programme should write the Fibbonacci 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. The first number in the line denotes the length of the representation n, 1 <= n <= 1 000 000. It is followed by n zeros and/or ones.
4 0 1 0 1 5 0 1 0 0 1
6 1 0 1 0 0 1
1 人解决，7 人已尝试。
1 份提交通过，共有 54 份提交。
9.9 EMB 奖励。