1214.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1214 on 2006-01-28 at 17:57:39 */ 
#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 };
	int i, t, T;
	char digit[64], fibed[64], ch;
	
	for(i = 2; i < FIB_N; i++) fib[i] = fib[i-1] + fib[i-2];
	scanf("%d\n", &T);
	for(t = 0; t < T; t++) {
		while((ch = getchar()) == '0'); ungetc(ch, stdin);
		int l = strlen(gets(digit)); memset(fibed, 0, sizeof(fibed));
		uint v = 0;
		for(i = 0; i < l; i++) v += (digit[i] - '0') * fib[l-1-i];
		printf("%u in decimal, ", v);
		int prev = -1, fn = 0;
		while(v != 0) {
			int o = upper_bound(fib, fib+FIB_N, v) - fib - 1;
			for(i = o+1; i < prev; i++) fibed[fn++] = '0';
			fibed[fn++] = '1'; prev = o; v -= fib[o];
		}
		for(i = 0; i < prev; i++) fibed[fn++] = '0';
		if(!strcmp(digit, fibed)) printf("already in standard form\n");
		else printf("whose standard form is %s\n", fibed);
	}
	
	return 0;
}