0121. Fibonacci Strings

Input file name:	fib.in
Output file name:	fib.out
Time limit:	500 ms
Memory limit:	64 megabytes

A Fibonacci string is a string of 0s and 1s that does not contain consecutive 1s.

Output a Fibonacci string by its position in the lexicographically ordered set of all Fibonacci strings of the same length.

Input file

The input file contains two integers n and k; n is the length of the Fibonacci string (1 ≤ n ≤ 44), and k is the postion of the string to be displayed (valid k ≥ 1).

Output file

Output n-th Fibonacci string in the only line of output.

Examples:

fib.in	fib.out
3 3	010

Source: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version