1. 
package problemSetVolumes.volume009;

import java.util.*;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 948 - Fibonaccimal Base
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=889
*
* @author Siegfried Ippisch
* @version 1.0
*
* Method : -
* Status : Accepted
* Runtime: 0.684
*/
public class FibonaccimalBase {

public static List<Integer> fibonacci(int max){
LinkedList<Integer> list = new LinkedList<Integer>();
list.addFirst(1);
list.addFirst(2);
while(list.getFirst() < max)
list.addFirst(list.get(0) + list.get(1));
list.removeFirst();
return list;
}

public static void main(String[] args){
List<Integer> fib = fibonacci(1000000000);
Scanner in = new Scanner(System.in);

int count = in.nextInt();
while(count-- > 0){
int value = in.nextInt();
System.out.print(value + " = ");

boolean b = false;

for(int i: fib){
if(i <= value){
System.out.print(1);
value -= i;
b = true;
} else if(b) System.out.print(0);
}
System.out.print(" (fib)\n");
}

in.close();
}

}