GFIB - Dãy số Fibonacc
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ớ: 512 megabyte
Đăng bởi: admin

Dãy số nguyên a1, a2, . . ., am được gọi là dãy số Fibonacci nếu thoả mãn một trong các điều kiện sau:

- m = 2,
- ai+1 = ai + ai-1 với m > i ≥ 2.

Ví dụ: Các dãy số sau là dãy số Fibonacci:

5,-2
5,-2,3,1,4,5,9,14,23

Với dãy số nguyên cho trước b1, b2, . . ., bn (n ≥ 2) người ta luôn luôn có thể gạch bỏ một số phần tử của dãy để dãy còn lại (giữ nguyên thứ tự trong dãy ban đầu) là một dãy số Fibonacci.

Ví dụ, từ dãy số cho trước 5,-2,50,3,1,4,5,60,9,14,23 ta có thể nhận được dãy Fibonacci bằng cách gạch bỏ khỏi dãy các phần tử thứ tám (số 60) và phần tử thứ ba (số 50).

Yêu cầu: Cho số nguyên dương n và dãy số nguyên b1, b2, . . ., bn. Hãy tìm cách gạch bỏ ít nhất các phần tử của dãy để nhận được dãy Fibonacci.

Dữ liệu:

- Dòng đầu tiên chứa số nguyên n

- Dòng thứ hai chứa n số nguyên b1, b2, . . ., bn (|bi| ≤ 109 , 1 ≤ i ≤ n ). Các số trên một dòng cách nhau bởi dấu cách.

Kết quả:

Ghi ra  số lượng ít nhất các phần tử cần gạch bỏ. 

Ví dụ

Input

11
5 -2 50 3 1 4 5 60 9 14 23

Output

2

Subtask 1: n ≤ 100.

Subtask 2: n ≤ 1000.

Subtask 3: n ≤ 10000.


Nguồn: 3D 20152016

Back to Top