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 f₁, f₂, ... , f_n đượ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ố f_i (i ≥ 3) thõa mãn điều kiện f_i = f_i-1 + f_i-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 a₁, a₂, ... , a_n. 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ố a₁, a₂, ... , a_n 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: a_i, a_i+1, a_i+2,... ,a_i+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 a₁, a₂, ... , a_n (|ai| ≤ 10⁹).
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
• Solution : 
• #include<iostream>

  #include<bits/stdc++.h>

  using namespace std;

  int n;

  // long BinarySearch(int x){

  // int left = 0,right = n-1;

  // while(left <= right){

  // int mid = (left + right)/2;

  // if(a[mid] == x) return mid;

  // else if(a[mid] < x) left = mid + 1;

  // else right = mid - 1;

  // }

  // return -1;

  // }

  int main (){

  cin >> n;

  int a[n];

  for(int i = 0;i<n;i++){

  cin >> a[i];

  }

  int dem = 0 , max = 0;

  for(int i = 0;i<n;i++){

  if(a[i+2] == (a[i]+a[i+1])) dem++;

  else {

  if(dem + 2 > max && dem != 0)

  max = dem + 2;

  dem = 0;

  }

  }

  if(dem + 2 > max && dem != 0){

  max = dem + 2;

  }

  if(max == 0) cout << "-1";

  else cout << max;

  }