DASO - Dãy số Fibonacci (OLPCĐ 2013)
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

       Một dãy số gồm n số nguyên f1, f2, ... , fn được gọi là dãy có tính chất của dãy số Fibonacci
nếu n ≥ 3 và với mọi số fi (i ≥ 3) thõa mãn điều kiện fi = fi-1 + fi-2.
      Ví dụ, dãy 1, 1, 2, 3, 5, 8  là dãy số có tính chất của dãy số Fibonacci; còn dãy 3, 3, 6, 9, 14, 23 không phải là dãy số có tính chất của dãy số Fibonacci.
Yêu cầu: Cho dãy số nguyên a1, a2, ... , an. Hãy  tìm một dãy con liên tiếp gồm nhiều phần tử nhất của dãy số a1, a2, ... , an mà có tính chất của dãy số Fibonacci. (Dãy con liên tiếp là dãy có dạng: ai, ai+1, ai+2,... ,ai+k).
Dữ liệu nhập:
-  Dòng đầu chứa số nguyên n (3 ≤ n ≤ 30.000)
-  Dòng thứ hai chứa n số nguyên a1, a2, ... , an (|ai| ≤ 109).
Dữ liệu xuất:

- Nếu tồn tại dãy con Fibonaci, in ra số lượng phần tử của dãy con tìm được.

- Nếu không tồn tại dãy con liên tiếp nào có tính chất của dãy số Fibonacci, in ra -1.

Ví dụ

  • input
    7
    1 3 3 6 9 14 23
    output
    4
  • input
    7
    1 1 2 3 5 8 13
    output
    7
Back to Top