0121. Fibonacci Strings

Имя входного файла: fib.in
Имя выходного файла: fib.out
Ограничение по времени: 500 ms
Ограничение по памяти: 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.infib.out
3 3010


Источник: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Автор: Andrew Lopatin, Nick Durov

Обсудить       Отправить решение



Версия для печати