1. Java, Simon Baumgartner


/*
* ACM Programming Contest
*
* Problem: 948 Fibonaccimal-Base
* Status: Accepted
* Run Time: 0.200
* Date: 2009-05-19
* Author: Simon Baumgartner
*/


import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

static long[] FIB_NRS = new long[]{1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,
2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,
1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986};

public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader in = new BufferedReader(new FileReader("input.txt"));
int count = Integer.parseInt(in.readLine());
for(int i=0; i < count; i++){
long x = Long.parseLong(in.readLine());
System.out.println(x + " = " + fib(x) + " (fib)");
}
}

private static String fib(long x) {
long sum = 0;
String ret = "";
// iterate in reverse order to always pick bigger fib nr first instead of the two smaller ones
// i.e take 21 instead of 8 and 13
for(int i = FIB_NRS.length - 1; i >= 0; i--){
long current = FIB_NRS[i];

// first find fib nr <= x to start with
if(current <= x){
// if we can add then add
if(sum + current <= x){
sum += current;
ret += "1";
}
else
ret += "0";
}
}
return ret;
}

}