Задача №111587. Фибоначчи
Числа Фибоначчи - элементы числовой последовательности, в которой каждое последующее число равно сумме двух предыдущих чисел. Более формально, последовательность чисел Фибоначчи {Fn} задается линейным рекуррентным соотношением:
Рассмотрим систему счисления с двумя цифрами 0 и 1, в которой, в отличие от двоичной системы весами являются не степени двойки 1,2,4,8,16,..., а числа Фибоначчи 1,2,3,5,8,13,.... В этой системе счисления каждое положительное целое число единственным образом представляется в виде строки нулей и единиц, которая начинается с 1 и в которой нет двух единиц, стоящих рядом.
Даны две строки, представляющие натуральные числа A и B. Найти строку, представляющую число A+B.
Даны две строки, представляющие A и B, состоящие из нулей и единиц. Длина каждой из строк не превышает 104.
Выведите строку, представляющую число A + B. Обратите внимание, что она должна начинаться с единицы.
10101
100
100010
Исходные строки '10101' и '100' представляют числа 8 + 3 + 1 = 12 и 3. Ответом является строка '100010', представляющая строку 13 + 2 = 15 = 12 + 3.