// 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