Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Система счисления Фибоначчи

(Время: 1 сек. Память: 16 Мб Сложность: 51%)

Числа Фибоначчи F1, F2, … определяются начальными значениями и соотношением:

F1=1; F2=2; Fn=Fn-1+Fn-2.

Рассмотрим систему счисления с двумя цифрами 0 и 1, в которой, в отличие от двоичной системы, весами являются не степени двойки 1, 2, 4, 8, 16, …, а числа Фибоначчи 1, 2, 3, 5, 8, 13, …. В этой системе счисления каждое положительное целое число единственном способом представляется в виде строки из нулей и единиц, которая начинается с 1 и в которой нет двух единиц, стоящих рядом.

Требуется написать программу, которая по двум заданным строкам, представляющим числа A и B в системе счисления Фибоначчи, находила строку, представляющую число A+B также в этой системе счисления.

Например, исходные строки 10101 и 100 представляют числа 1*8+0*5+1*3+0*2+1*1=8+3+1=12 и 1*3+0*2+0*1=3. Ответом является строка 100010, представляющая число 1*13+0*8+0*5+0*3+1*2+0*1=13+2=15=12+3.

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

Входной файл INPUT.TXT в первой строке содержит число A и B во второй. Длина записи чисел A, B и их суммы A+B в системе счисления Фибоначчи не превышает 255 знаков.

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

В выходной файл OUTPUT.TXT выведите значение суммы A+B в системе счисления Фибоначчи.

Пример

INPUT.TXTOUTPUT.TXT
110101
100
100010

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483