Задачи
Строки Фибоначчи
Строки Фибоначчи
Строкой Фибоначчи называется строка из символов 0 и 1, не содержащая двух единиц подряд.
Вашей задачей является по лексикографическому номеру строки Фибоначчи построить саму строку. Лексикографическим номером является номер в лексикографически упорядоченном (т.е. отсортированном естественным образом) наборе. Нумерация ведется от единицы.
Входные данные
Содержит два целых числа: длину строки Фибоначчи n (1 ≤ n ≤ 44), и номер строки k, которую необходимо вывести. Гарантируется, что строка с номером k существует.
Выходные данные
Вывести k-ую строку Фибоначчи длины n.
Пример
Входные данные #1
3 3
Выходные данные #1
010
Входные данные #2
5 5
Выходные данные #2
00101