11388: 【原1388】Fib表示

题目

题目描述

author: Taring 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1388

Description

Taring开始思考斐波那契数列了。及，\( F_0 = 1, F_1 = 1, F_i = F_{i - 1} + F_{i - 2}(i >= 2) \)。

他发现，根据这个数列，我们可以将一个数用\( b_1 \cdot F_1 + b_2 \cdot F_2 + ... + b_n \cdot F_n \)表示。其中，\( { b_i } \)数组是一个01串数组。

而对于这个数组，作出如下的规定去规范化这个数组(称作Fib表示)。

1.不含前导零，即\( b_n = 1 \)。

2.不存在连续的两个值均为1的数字，即若\( b_i = 1\), 则\( b_{i + 1} = 0 \)。

现在给出两个数的Fib表示，求这两个数的和的Fib表示。

Input Format

输入共两行，每一行表示一个数的Fib表示。

对于每一行，第一个数为len，为该表示数列的长度；后面有n个数，分别为\(b_1 .. b_n \)。

Output Format

输出共一行，为这个和的Fib表示。

对于这一行，第一个数为len，为该表示数列的长度；后面有n个数，分别为\(b_1 .. b_n \)。

Sample Input

4 0 1 0 1
5 0 1 0 0 1

Sample Output

6 1 0 1 0 0 1

Hint

对于40%的数据, n ≤ 100。

对于100%的数据, n ≤ 1,000,000。

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！