Codeforces Round #804 (Div. 2)
22:48:47 |
Educational Codeforces Round 131 (Rated for Div. 2)
4 өдрийн дараа |
Codeforces Round #805 (Div. 3)
6 өдрийн дараа |
Codeforces Round #806 (Div. 4)
8 өдрийн дараа |
D. Фибоначчи-иш
хугацааны хязгаарлалт 3 секунд
санах ойн хязгаарлалт 512 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Яаш саяхан Фибоначч-ийн дараалал үзсэн бөгөөд үүний талаар ихээхэн сонирхож байгаа юм. Тэрээр аливаа дарааллыг дараах нөхцөлийг хангаж байвал Фибоначчи-иш гэж нэрлэж байв. Үүнд:
- Дараалал нь дор хаяж 2 элементээс тогтоно.
- $f_{0}$ болон $f_{1}$-ыг дураараа сонгоно.
- Бүх $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$.