eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Строки Фибоначчи

Строки Фибоначчи

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Строкой Фибоначчи называется строка из символов 0 и 1, не содержащая двух единиц подряд.

Вашей задачей является по лексикографическому номеру строки Фибоначчи построить саму строку. Лексикографическим номером является номер в лексикографически упорядоченном (т.е. отсортированном естественным образом) наборе. Нумерация ведется от единицы.

Входные данные

Содержит два целых числа: длину строки Фибоначчи n (1n44), и номер строки k, которую необходимо вывести. Гарантируется, что строка с номером k существует.

Выходные данные

Вывести k-ую строку Фибоначчи длины n.

Пример

Входные данные #1
3 3
Выходные данные #1
010
Входные данные #2
5 5
Выходные данные #2
00101
Источник 2010 ЛКШ. Берендеевы Поляны. Июль. A' Д01