D. Фибоначчи-иш

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Яаш саяхан Фибоначч-ийн дараалал үзсэн бөгөөд үүний талаар ихээхэн сонирхож байгаа юм. Тэрээр аливаа дарааллыг дараах нөхцөлийг хангаж байвал Фибоначчи-иш гэж нэрлэж байв. Үүнд:

  1. Дараалал нь дор хаяж 2 элементээс тогтоно.
  2. $f_{0}$ болон $f_{1}$-ыг дураараа сонгоно.
  3. Бүх $n ≥ 0$-ын хувьд $f_{n + 2} = f_{n + 1} + f_{n}$ байна.

Танд бүхэл тоон дараалал $a_{1}, a_{2}, ..., a_{n}$ өгөгдөв. Таны даалгавар бол уг дарааллын элементүүдээс сонгож боломжит хамгийн урт Фибоначчи-иш дараалал үүсгэх явдал юм.

Оролт

Эхний мөрөнд $a_{i}$ дарааллын урт болох ганц бүхэл тоо $n$ ($2 ≤ n ≤ 1000$) өгөгдөнө.

2-дахь мөрөнд $n$ ширхэг бүхэл тоо $a_{1}, a_{2}, ..., a_{n}$ ($|a_{i}| ≤ 10^{9}$)-ууд өгөгдөнө.

Гаралт

Дахин байрлуулсны дараах дараалалд байх боломжит хамгийн урт Фибоначчи-иш дарааллын уртыг хэвлэнэ.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
3
1 2 -1
Гаралт
3
Оролт
5
28 35 7 14 21
Гаралт
4

Тэмдэглэл

Эхний жишээнд хэрэв бид дарааллаа $-1$, $2$, $1$ гэж дахин байрлуулбал $a_{i}$ дараалал нь тэр чигээрээ Фибоначчи-иш дараалал болох юм.

2-дахь жишээнд, оновчтой боломжит хувилбар нь дараах байдлаар байх юм. , , , , $28$.

Сэтгэгдлүүдийг ачааллаж байна...