Подразделы

Другие разделы

Дата и время

09/04/2025 08:39:48

Авторизация

Задачи очного тура личного первенства

1. Налогообложение 2. Закодированное изображение 3. Дробь 4. Эльфы 5. Фибоначчиева система счисления 6. Игра 7. Задача электрика 8. Auto Loan 9. Prime Polynom

5. Фибоначчиева система счисления

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Числа Фибоначчи хорошо известны. Они определяются рекуррентным соотношением:

$F_0=0$ ,

$F_1=1$ ,

$F_n=F_{n-1}+F_{n-2}$ для

$n>1$ .

Фибоначчиева система счисления (ФСС) основана на теореме Цеккендорфа, утверждающей, что любое целое положительное число имеет единственное представление вида

$N=F_{k_1}+F_{k_2}+…+F_{k_r}$ , где

$F_{k_i}$ – число Фибоначчи, а

$k_1\ ">>"\ k_2\ ">>"\ …\ ">>"\ k_r\ ">>"\ 0$ .

Здесь

$i\ ">>"\ j$ означает, что

$i\ ≥\ j+2$ . Целое неотрицательное число можно записать в виде последовательности нулей и единиц:

$N=(b_m\ b_{m-1}…b_2)_F\ hArr\ N\ =\ sum_{i=2}^m\ b_i*F_i$ , где

$b_i\ =\ 1$ , если

$F_i$ входит в преставление, иначе 0.

Например,

$1000000$ =

$832040\ +\ 121393\ +\ 46368\ +\ 144\ +\ 55$ =

$F_30\ +\ F_26\ +\ F_24\ +\ F_12\ +\ F_10$ или

$(1000000)_10\ =\ (10001010000000000010100000000)_F$ . Эта система счисления напоминает двоичное представление, за исключением того, что в ней никогда не встречаются две 1 подряд.

Напишите программу, которая вводит числа в десятичной системе счисления и выводит их в ФСС.

Во входном файле в первой строке содержится число

$T$ (

$0\ <\ T\ <\ 100$ ) – количество тестов. Каждый тест распологается на своей строке, он состоит из одного числа

$N$ (

$0\ <\ N\ <\ 10^100$ ), записанного в десятичной системе счисления.

В выходной файл для каждого введенного числа вывести его представление в Фибоначчиевой системе счисления. Число обязательно должно начинаться с 1.

Пример ввода

Пример вывода

1
1000010100
100000000100000