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

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

HotLog


 

Раздача Фибоначчи

(Время: 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.TXTOUTPUT.TXT
121
252

Пояснение к примерам

В первом примере команда решила F2 = 1 задач, всем досталось по 0 шариков, 1 остался лишним.

Во втором примере команда решила F5 = 5 задач, всем досталось по 1 шарику, 2 остались лишними, чтобы не создавать неравенства между членами команды.


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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 A. Дистанционное обучение
 B. Код от сейфа
 C. Всеобъемлющая Галактическая Магистральная Сеть
 D. ДНК-палиндром
 E. Разлад Империй
 F. Раздача Фибоначчи
 G. Карты, числа, два заклинания
 H. Гипноз
 I. Круговой марафон
 J. Пасьянс по-иркутски
 K. Shark Attack

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru