Cho số nguyên dương n và dãy số a1, a2, ..., aN. Gọi đoạn con [u,v] của dãy là các phần tử liên tiếp au, au+1, au+2,....av (u v). Dễ thấy đoạn con [u,v] có độ dài là v-u+1 và giá trị trung bình là
(au+au+1+au+2+…+av) / (v - u+1).
Yêu cầu: Cho số nguyên k, hãy xác định đoạn con có độ dài không nhỏ hơn k có giá trị trung bình lớn nhất.
Dữ liệu: Vào từ file văn bản AVERAGE.INP
- Dòng đầu chứa 2 số nguyên dương n, k
- Dòng thứ 2 chứa n số nguyên A1, A2, ..., AN ( |ai| 109 , 1<= i <=n), các số được phân tách nhau bởi dấu cách.
Kết quả: Đưa ra file văn bản AVERAGE.OUT một số thực duy nhất là giá trị trung bình của đoạn con tìm được. Kết quả đưa ra lấy 3 chữ số thập phân sau dấu phẩy.
AVERAGE.INP |
AVERAGE.OUT |
4 2 17 0 14 1 |
10.333 |
AVERAGE.INP |
AVERAGE.OUT |
5 1 2 8 -1 4 5 |
8.000 |
Giải thích:
-Trong ví dụ 1, đoạn con có giá trị trung bình lớn nhất thỏa mãn là đoạn [1,3] với các giá trị 17, 0, 14.
-Trong ví dụ 2, đoạn con có giá trị trung bình lớn nhất thỏa mãn là đoạn [2,2] với giá trị là 8.
Ràng buộc: