1788.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1788 on 2006-01-29 at 16:04:40 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int FIB_N = 46;
typedef unsigned int uint;

int main()
{
	uint fib[64] = { 1, 2 }, add[3];
	char digit[3][64];
	int i, j;
	
	for(i = 2; i < FIB_N; i++) fib[i] = fib[i-1] + fib[i-2];
	while(scanf("%s %s", digit[0], digit[1]) != EOF) {
		for(i = 0; i < 2; i++) {
			int l = strlen(digit[i]); add[i] = 0;
			for(j = 0; j < l; j++) add[i] += (digit[i][j] - '0') * fib[l-1-j];
		}
		add[2] = add[0] + add[1];
		memset(digit, 0, sizeof(digit));
		for(i = 0; i < 3; i++) {
			int prev = -1, fn = 0;
			while(add[i] != 0) {
				int o = upper_bound(fib, fib+FIB_N, add[i]) - fib - 1;
				for(j = o+1; j < prev; j++) digit[i][fn++] = '0';
				digit[i][fn++] = '1'; prev = o; add[i] -= fib[o];
			}
			for(j = 0; j < prev; j++) digit[i][fn++] = '0';
			if(digit[i][0] == 0) digit[i][0] = '0';
		}
		int len = strlen(digit[2]) + 2;
		for(i = 0; i < 3; i++) {
			if(i == 2) {
				printf("  ");
				for(j = 2; j < len; j++) putchar('-');
				putchar('\n');
			}
			int l = len - strlen(digit[i]);
			if(i == 1) putchar('+'), l--;
			for(j = 0; j < l; j++) putchar(' ');
			printf("%s\n", digit[i]);
		}
		putchar('\n');
	}
	
	return 0;
}