UVa : 948 (Fibonaccimal Base)

// http://uva.onlinejudge.org/external/9/948.html
// Runtime : 0.008s
// Tag : Recursive, Fibonacci, DFS

//=====================================================================
// Name        : UVa_948.cpp
// Author      : Shahab
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//=====================================================================

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long
using namespace std;

int ar [50];
int in = 0;
bool found;

void fibo ()
{
	int a = 0, b = 1, c = 1;
	in = 0;

	while ( c <= 100000000 ) {
		ar [in++] = c;
		a = b;
		b = c;
		c = a + b;
	}

}

void print (LL m)
{
	string str = "";

	while ( m ) {
		str += (m % 2) + '0';
		m /= 2;
	}

	reverse (str.begin(), str.end());

	cout << str << " (fib)" << endl;
}

void recur (int at, int num, LL mask)
{
	if ( num == 0 ) { print (mask); found = true; return; }
	if ( num < 0 || found ) return;

	for ( int i = at - 2; i >= 0; i-- )
		recur (i, num - ar [i], mask | ( (LL)1 << i));
}

int main ()
{
	fibo ();
	int testCase;
	scanf ("%d", &testCase);

	while ( testCase-- ) {
		int n;
		scanf ("%d", &n);

		cout << n << " = ";

		found = false;

		recur (in + 1, n, 0);
	}

	return 0;
}

// @END_OF_SOURCE_CODE

Advertisements