Автор: | Антон Карабанов | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Числа Фибоначчи — элементы бесконечной числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … , в которой первые два числа равны 1 и 1, а каждое последующее число равно сумме двух предыдущих чисел.
Треугольник Фибоначчи — это треугольник, составленный из чисел на основе чисел Фибоначчи. Две стороны этого треугольника образуют последовательность Фибоначчи. Каждое число является суммой двух чисел выше по левой или правой диагонали. Ниже на рисунке приведены несколько первых строк треугольника:
Тимофей исследует свойства этого треугольника. Ему необходимо знать, встретится ли нужное ему натуральное число в этом треугольнике, и если да, то в какой по порядку строке это произойдет?
В единственной строке записано натуральное число n.
Выведете одно натуральное число — номер строки треугольника, в которой впервые встретится данное число. Если число в треугольнике не встретится никогда, выведите − 1.
1 ≤ n ≤ 1018
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Подзадача 1: 1 ≤ n ≤ 103, баллы: 30.
Подзадача 2: нет дополнительных ограничений, баллы: 70.
Число 2 первый раз встречается в третьей строке треугольника, число 10 — в седьмой, число 12 не встречается вообще.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|