Description

对于每个数字x，我们总可以把它表示成一些斐波拉切数字之和，比如8 = 5 + 3， 而22 = 21 + 1，因此我们可以写成 x = a1 * Fib1 + a2 * Fib2 + a3 * Fib3 + … + an * Fibn, 其中，Fib1 = 1, Fib2 = 2…. Fib[i] = Fib[i – 1] + Fib[I - 2], 且a[n] > 0.那么我们称ai为x的一种斐波拉切表示，由于表示方法有很多种，我们要求最大化a[1…n]，即，如果b[1…n]和a[1…m]都可以表示x，若m > n 则a更大，若 m = n， 则从高位到低位比，第一个不同处i，若ai > bi 则a比b大。

你的任务很简单，给你两个用斐波拉切数最大化表示的两个数字，输出他们相加后用斐波那契最大化表示的数字。

Input

两行，分别表示两个数字

每一行开头一个n，表示长度

然后紧接着n个数字，为从低位到高位。

Output

同输入格式。一行。

Sample Input

4 0 1 0 1

5 0 1 0 0 1

Sample Output

6 1 0 1 0 0 1

Data Constraint

对于30%的数据 长度 <= 1000

对于100%的数据 长度 <= 1000000

Solution

在两数相加的时候，其实不需要表示成斐波拉契的形式，因为我们可以通过读入的信息得到答案。

我们把两序列逐位相加，得到一个全新的序列，即为答案。

但这仍不是最优表示，还存在一些 连续的 1 或 一些 2 。

于是我们将这些“进位”掉，并注意判断特殊情况即可，复杂度是线性的。

注意：本题读入输出文件较大，可以使用C++读入输出优化（不会的戳这里），可大大优化时间。

Code

#include<cstdio> using namespace std; int a[1000005]; inline int read() { int X=0,w=1; char ch=0; while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();} while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar(); return X*w; } inline void dfs(int x,int y) { while(x<=y && x<=a[0]) { if(a[x]) { if(a[x]>=1 && a[x+1]>=1) { if(x+2>a[0]) a[0]=x+2; a[x+2]++; a[x]--,a[x+1]--; } if(a[x]>=2) { if(x==a[0]) a[++a[0]]++; else a[x+1]++; int z=x-2; if(!z) z++; else if(z<0) z=-1; if(z>=0) a[z]++; a[x]-=2; if(a[z]>=2 || z>=0 && a[z+1]>=1) dfs(z,x); else if(z>1 && a[z-1]>=1) dfs(z-1,x); } if(a[x]>=1 && a[x+1]>=1) { if(x+2>a[0]) a[0]=x+2; a[x+2]++; a[x]--,a[x+1]--; } } x++; } } int main() { a[0]=read(); for(int i=1;i<=a[0];i++) a[i]=read(); int k=read(); for(int i=1;i<=k;i++) a[i]+=read(); if(k>a[0]) a[0]=k; dfs(1,1e9); printf("%d",a[0]); for(int i=1;i<=a[0];i++) { putchar(' '); if(a[i]) putchar('1'); else putchar('0'); } return 0; }