Раздача Фибоначчи
(Время: 1 сек. Память: 16 Мб Сложность: 24%)
Пожилая команда «Путешественники по разуму» пишет уже свой пятьдесят четвёртый четвертьфинал пенсионерского командного чемпионата мира по программированию.
Программисты Иркутского государственного дома престарелых люди уже не молодые, как и их соперники, поэтому контест для них длится не стандартные студенческие пять часов, а пять месяцев. Спокойное, размеренное решение задач – залог здоровья.
Соответственно, и количество задач на таком контесте бесконечное. «Путешественники» верны своим принципам, поэтому всегда решают на четвертьфинале количество задач, равное некоторому числу Фибоначчи.
Числа Фибоначчи – это числовая последовательность, задаваемая следующими правилами:
- F0 = 0
- F1 = 1
- Fi = Fi−1 + Fi−2, i ≥ 2
На четвертьфинале 2020 «Путешественники» решили Fn задач. По правилам чемпионата, они во время тура получили ровно столько же воздушных шариков, по одному за каждую задачу.
Капитан команды, Кинир, решил раздать всем трём участникам команды (включая себя) максимальное возможное равное количество шариков из имеющихся. Однако в конце обнаружилось, что осталось несколько лишних шариков.
А вот сколько именно – предстоит ответить вам.
Входные данные
Входной файл INPUT.TXT содержит целое число n (0 ≤ n ≤ 109), означающее, что команда получила Fn шариков за контест.
Выходные данные
В выходной файл OUTPUT.TXT выведите единственное число – ответ на задачу (количество лишних шариков, оставшихся после раздачи всех имеющих поровну в максимально возможном количестве).
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 | 1 |
| 2 | 5 | 2 |
Пояснение к примерам
В первом примере команда решила F2 = 1 задач, всем досталось по 0 шариков, 1 остался лишним.
Во втором примере команда решила F5 = 5 задач, всем досталось по 1 шарику, 2 остались лишними, чтобы не создавать неравенства между членами команды.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
