printРабочее место участника

printЗадачи

2095. Строки Фибоначчи

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Алла очень любит палиндромы. Все потому, что её имя является палиндромом. Напомним, что строку называют палиндромом тогда, когда она одинаково читается как слева направо, так и справа налево.
Однажды в школе учитель рассказал Алле про так называемые строки Фибоначчи.
Строки Фибоначчи определяются следующим образом:
  • `f_0\ =\ a`
  • `f_1\ =\ b`
  • `f_{n}\ =\ f_{n-1}\ f_{n-2}` для каждого `n\ >\ 2` – конкатенация двух предыдущих строк Фибоначчи
Таким образом, первые пять строк Фибоначчи: a, b, ba, bab, babba.
Аллу сразу заинтересовал вопрос – какой максимально длинный палиндром встречается в `k`-й строке Фибоначчи. Помогите Алле решить эту задачу.
Первая строка входного файла содержит одно целое число `k` (`0\ ≤\ k\ ≤\ 80`) – номер строки Фибоначчи.
В выходной файл выведите длину самого большого палиндрома, содержащегося в `k`-й строке Фибоначчи.

Пример ввода 1

2

Пример вывода 1

1

Пример ввода 2

4

Пример вывода 2

4
Источник: neerc.ifmo.ru/school
loading