ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1396. Максимум. Версия 2

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Рассмотрим последовательность чисел ai, i = 0, 1, 2, …, удовлетворяющих следующим условиям:
  • a0 = 0
  • a1 = 1
  • a2i = ai
  • a2i + 1 = ai + ai + 1
для каждого i = 1, 2, 3, … .
Напишите программу, которая для заданного значения n находит максимальное среди чисел a0, a1, …, an.

Исходные данные

Входные данные состоят из нескольких тестов (не более 10 000). Каждый тест представляет собой строку, в которой записано целое число n (1 ≤ n < 1018). В последней строке входных данных записано число 0.

Результат

Для каждого n во вводе выведите соответствующее максимальное значение.

Пример

исходные данныерезультат
5
10
0
3
4

Замечания

Задача совпадает с задачей 1079 “Максимум”, но имеет большие ограничения на входные данные.
Автор задачи: Подготовка – Владимир Яковлев