Bedan Contest #01 - A - Cặp số Fibo
Xem PDF
Nộp bài
Điểm:
1100 (thành phần)
Thời gian:
0.5s
Bộ nhớ:
256M
Input:
fibopair.inp
Output:
fibopair.out
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++, NASM, Pascal, pypy3, Python
Dãy số Fibo là 1 dãy số có quy luật như sau:
- F_1 = F_2 = 1.
- F_n = F_{n-1}+F_{n-2} với n > 2.
Cho dãy a gồm n phần tử, một cặp chỉ số (i, j) được gọi là cặp số Fibo nếu nó thỏa mãn:
- 1 \le i \le j \le n.
- a_i+a_{i+1}+...+a_j là 1 số Fibo.
Nhiệm vụ của bạn là đếm số lượng cặp số Fibo (i, j) của dãy a.
Input, Output and Scoring
Input
- Số nguyên dương n (1 \le n \le 10^5).
- Dãy a gồm n phần tử a_1, a_2, ..., a_n (1 \le a_i \le 10^5).
Output
- In ra kết quả thỏa mãn.
Scoring
- Subtask 1 (20\%): 1 \le n \le 10^3.
- Subtask 2 (80\%): Không giới hạn gì thêm.
Example
Input
4
2 7 4 3
Output
3
Note
- Có 3 cặp số Fibo là (1, 1), (1, 3), (4, 4).
Bình luận