Description

The group of Absurd Calculation Maniacs has discovered a great new way how to count. Instead of using the ordinary decadic numbers, they use Fibonacci base numbers. Numbers in this base are expressed as sequences of zeros and ones similarly to the binary numbers, but the weights of bits (fits?) in the representation are not powers of two, but the elements of the Fibonacci progression (1, 2, 3, 5, 8,... - the progression is defined by F0 = 1, F1 = 2 and the recursive relation Fn = Fn-1 + Fn-2 for n >= 2).

For example 1101001Fib = F0 + F3 + F5 + F6 = 1 + 5 + 13 + 21 = 40.

You may observe that every integer can be expressed in this base, but not necessarily in a unique way - for example 40 can be also expressed as 10001001Fib. However, for any integer there is a unique representation that does not contain two adjacent digits 1 - we call this representation canonical. For example 10001001Fib is a canonical Fibonacci representation of 40.

To prove that this representation of numbers is superior to the others, ACM have decided to create a computer that will compute in Fibonacci base. Your task is to create a program that takes two numbers in Fibonacci base (not necessarily in the canonical representation) and adds them together.

Input

The input consists of several instances, each of them consisting of a single line. Each line of the input contains two numbers X and Y in Fibonacci base separated by a single space. Each of the numbers has at most 40 digits. The end of input is not marked in any special way.

Output

The output for each instance should be formated as follows:

The first line contains the number X in the canonical representation, possibly padded from left by spaces. The second line starts with a plus sign followed by the number Y in the canonical representation, possibly padded from left by spaces. The third line starts by two spaces followed by a string of minus signs of the same length as the result of the addition. The fourth line starts by two spaces immediately followed by the canonical representation of X + Y. Both X and Y are padded from left by spaces so that the least significant digits of X, Y and X + Y are in the same column of the output. The output for each instance is followed by an empty line.

输入数据 1 11101 1101

1 1

输出数据 1

100101

10001

1001000

1

1

10

Source

CTU Open 2004

描述

“荒谬计算狂热者” 小组发现了一种全新的计数方法。他们不使用常见的十进制数，而是采用斐波那契基数来表示数字。在这种基数下，数字像二进制数一样用由 0 和 1 组成的序列来表示，但在这种表示中，数位（比特？）的权重不是 2 的幂次方，而是斐波那契数列（1, 2, 3, 5, 8, … 该数列定义为 F 0​ =1， F 1​ =2，且对于 n≥2 有递归关系 F n​=F n−1​+F n−2​）的元素。

例如，1101001 Fib =F 0 +F 3 +F 5+F 6=1+5+13+21=40。

你可能会注意到，每个整数都可以用这种基数表示，但不一定是唯一的表示方式 —— 例如，40 也可以表示为 10001001 Fib。 然而，对于任何整数，都存在一种不包含两个相邻 1 的唯一表示形式，我们称这种表示为规范表示。例如， 10001001 Fib 就是 40 的规范斐波那契表示形式。 为了证明这种数字表示方法优于其他方法，“荒谬计算狂热者” 小组（ACM）决定制造一台能够在斐波那契基数下进行计算的计算机。你的任务是编写一个程序，接受两个斐波那契基数表示的数字（不一定是规范表示形式）并将它们相加。

输入

输入由若干个实例组成，每个实例占一行。输入的每一行包含两个用单个空格分隔的斐波那契基数表示的数字 X 和 Y 。每个数字最多有 40 位。输入的结束没有特殊的标记。

输出

每个实例的输出格式如下： 第一行包含规范表示形式的数字 X，可能在左边用空格填充。第二行以加号开头，后面跟着规范表示形式的数字Y，同样可能在左边用空格填充。第三行以两个空格开头，后面跟着一串长度与X+Y的结果长度相同的减号。第四行以两个空格开头，紧接着是X+Y的规范表示形式。X和Y都在左边用空格填充，使得 X、Y和X+Y的最低有效位在输出中处于同一列。每个实例的输出后面都跟一个空行。 输入数据 1

11101 1101

1 1

输出数据 1

100101

10001

1001000

1

1

10

来源

2004 年 CTU 公开赛

题意分析：

给出两个01串，每个位的权重是斐波那契值，要求相加后的结果，并将它们都转化为不存在连续1的字符串。

题解思路：

斐波那契+模拟 预处理斐波那契数列，然后将原串转化为十进制n u m numnum。接下来考虑如何转化。 已知原串位数不超过40位，可以知道上限为f [ 41 ]，从上限往下遍历，若n u m ≥f [ i ]，减去即可，这样就不会出现连续1，推一推就知道了。

标程

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll F[50];
string s1,s2,s3;
void init(){
	F[0]=1,F[1]=2;
	for(int i=2;i<=45;i++)
		F[i]=F[i-1]+F[i-2];
}
ll getnum(string s){
	ll ans=0;
	int len=s.size();
	for(int i=0;i<len;++i)
		if(s[i]=='1')
			ans+=F[i];
	return ans;
}
void solve(ll n,string& s){
	int i;
	for(i=45;i>=0;i--)
		if(F[i]<=n)
			break;
	for(int t=i;t>=0;t--){
		if(n>=F[t]){
			n-=F[t];
			s+='1';
		}
		else 
		s+='0';
	}
	if(i<0) s+='0';
}
int main(){
	init();
	while(cin>>s1>>s2){
		reverse(s1.begin(),s1.end());
		reverse(s2.begin(),s2.end());
		ll a=getnum(s1);
		ll b=getnum(s2);
		ll sum=a+b;
		s1.clear();
		s2.clear();
		s3.clear();
		solve(a,s1);
		solve(b,s2);
		solve(sum,s3);
		int l1=s1.size(),l2=s2.size(),l3=s3.size();
		printf("  ");
		for(int i=0;i<l3-l1;i++)
			printf(" ");
		cout<<s1<<endl;
		printf("+ ");
		for(int i=0;i<l3-l2;i++)
			printf(" ");
		cout<<s2<<endl;
		printf("  ");
		for(int i=0;i<l3;++i)
			printf("-");
		cout<<endl;
		printf("  ");
		cout<<s3<<endl;
		cout<<endl;
	} 
	return 0;
}