Bài 12.5. Phân tích chuỗi số "Fibonacci mở rộng" - [Độ khó: Khó]

Mô tả: Trong một dự án nghiên cứu số học, bạn được giao nhiệm vụ phân tích một loại chuỗi số đặc biệt mà chúng tôi gọi là "Fibonacci mở rộng". Chuỗi này bắt đầu bằng hai số nguyên A và B cho trước. Các số tiếp theo trong chuỗi được tạo ra bằng cách cộng hai số liền kề trước đó, giống như chuỗi Fibonacci truyền thống. Nhiệm vụ của bạn là tạo ra chuỗi này cho đến khi nó đạt được N phần tử, hoặc một phần tử nào đó vượt quá giá trị K (tùy điều kiện nào đến trước). Sau đó, bạn cần thực hiện hai phân tích trên chuỗi đã tạo:

1. Tính tổng tất cả các số chẵn trong chuỗi.
2. Đếm số lần xuất hiện của một giá trị X cho trước trong chuỗi.

Bài tập này đòi hỏi bạn phải tạo ra một chuỗi số theo quy tắc phức tạp, quản lý kích thước mảng và điều kiện dừng, sau đó thực hiện các phép phân tích dữ liệu trên mảng. Lưu ý: Các số trong chuỗi Fibonacci mở rộng và tổng của chúng có thể rất lớn. Hãy sử dụng kiểu dữ liệu long long để tránh tràn số.

INPUT FORMAT

Dòng đầu tiên chứa bốn số nguyên: A, B (0 <= A, B <= 10^9), N (1 <= N <= 1000), K (1 <= K <= 10^9). A và B là hai số khởi tạo. N là độ dài tối đa của chuỗi. K là ngưỡng giá trị. Dòng thứ hai chứa một số nguyên X (0 <= X <= 10^9), là giá trị cần đếm số lần xuất hiện.

OUTPUT FORMAT

Dòng đầu tiên in ra tổng các số chẵn trong chuỗi. Dòng thứ hai in ra số lần xuất hiện của giá trị X.

Ví dụ 1:

Input:

1 2 8 50
3

Output:

44
1

Giải thích:

• A=1, B=2, N=8, K=50. X=3.
• Chuỗi Fibonacci mở rộng được tạo ra:
  • Bắt đầu với 1, 2.
  • Số tiếp theo: 1+2=3.
  • Số tiếp theo: 2+3=5.
  • Số tiếp theo: 3+5=8.
  • Số tiếp theo: 5+8=13.
  • Số tiếp theo: 8+13=21.
  • Số tiếp theo: 13+21=34.
• Chuỗi dừng lại khi đạt đủ N=8 phần tử: 1, 2, 3, 5, 8, 13, 21, 34. (Tất cả các số trong chuỗi đều <= K=50).
• Các số chẵn trong chuỗi là: 2, 8, 34. Tổng = 2 + 8 + 34 = 44.
• Giá trị X=3 xuất hiện 1 lần trong chuỗi.

Ví dụ 2 (Trường hợp biên - vượt K):

Input:

1 1 10 5
5

Output:

10
1

Giải thích:

• A=1, B=1, N=10, K=5. X=5.
• Chuỗi Fibonacci mở rộng được tạo ra:
  • Bắt đầu: 1, 1.
  • Số tiếp theo: 1+1=2.
  • Số tiếp theo: 1+2=3.
  • Số tiếp theo: 2+3=5.
  • Số tiếp theo: 3+5=8. Giá trị 8 này lớn hơn K=5. Nó vẫn được thêm vào chuỗi.
  • Chuỗi dừng lại vì số vừa sinh ra (8) lớn hơn K.
• Chuỗi cuối cùng: 1, 1, 2, 3, 5, 8. (Chuỗi có 6 phần tử, nhỏ hơn N=10).
• Các số chẵn trong chuỗi là: 2, 8. Tổng = 2 + 8 = 10.
• Giá trị X=5 xuất hiện 1 lần trong chuỗi.