|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||128 MB||50||11||5||20.000%|
Fibonacci 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 Fibonacci 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.) Unfortunately, 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:
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 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 non-negative 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 Fibonacci representation (satisfying the aforementioned conditions) of the sum x+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 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
Olympiad > Polish Olympiad in Informatics > POI 2004/2005 > Stage 2 3번