Manthan, Codefest 16 |
---|
Закончено |
Яш недавно узнал о числах Фибоначчи. Он так обрадовался этому знанию, что решил называть произвольную последовательность фибоначчиеватой, если
Вам дана последовательность целых чисел a1, a2, ..., an. Вам требуется переставить элементы последовательности таким образом, чтобы как можно более длинный её префикс был фибоначчиеватой последовательностью.
В первой строке входных данных записано единственное число n (2 ≤ n ≤ 1000) — длина последовательности ai.
Во второй строке записаны n целых чисел a1, a2, ..., an (|ai| ≤ 109).
Выведите количество элементов в самом длинном возможном фибоначчиеватом префиксе после перестановки элементов.
3
1 2 -1
3
5
28 35 7 14 21
4
В первом примере, если переставить элементы исходной последовательности следующим образом - 1, 2, 1, то вся последовательность ai будет фибоначчиеватой.
Во втором примере оптимальным способом переставить элементы является ,
,
,
, 28.
Название |
---|