Mr Fibonacci does some Encoding
All submissions for this problem are available.
Every positive integer can be represented uniquely as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers.
With the help of the above proposition, every integer can be encoded into a sequence of 0s and 1s.
For a number N, if d(0), d(1), d(2)...d(k-1) and d(k) represent the digits of the code word representing N then we have:
....where F (i) is the ith Fibonacci number, and so F (i+2) is the ith distinct Fibonacci number starting with 1, 2, 3, 5, 8, 13... The last bit d(k) is always an appended bit of 1 and does not carry place value.
It is one example of representations of integers based on Fibonacci numbers. Each code word ends with "11" and contains no other instances of "11" before the end.
Given a set of numbers, write a program to encode each of them into code words as described above.
Line 1: A single integer T, the number of test cases
Line 2 to T+1: Each of these lines describes a single integer X (i), followed by a newline.
Line 1 to T: Each of these lines must describe the code for the corresponding integer that had been entered, followed by a newline.
All integers in the input are going to be natural numbers.
· T<=100000 & X (i) <= 18446744073709551615
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.