Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!