Bài 4 – đề thi tuyển sinh 10 lớp chuyên tin học tỉnh Quảng Trị - năm 2021

Cho dãy \(A\) gồm \(n\) số nguyên dương \(a_{1},a_{2},\ldots,a_{n}\) và một số nguyên dương \(k\). Một đoạn con của \(A\) là một dãy liên tục các phần tử của \(A\). Một đoạn con của \(A\) được gọi là hài hòa nếu trung bình cộng của các phần tử trong đoạn con đó đúng bằng \(k\).

Yêu cầu: Hãy tìm đoạn con hài hòa dài nhất bằng cách chỉ ra độ dài và chỉ số phần tử đầu tiên của đoạn con đó. Nếu tồn tại nhiều đoạn con như vậy thì đưa ra đonạ con có chỉ số phần tử đầu tiên nhỏ nhất. Nếu không tồn tại đoạn con nào thỏa mãn thì ghi ra số 0.

Dữ liệu vào:

+ Dòng đầu tiên ghi hai số nguyên dương \(n\) và \(k\) \((1 \leq n \leq 10^{5},1 \leq k \leq 10^{9})\);

+ Dòng thứ hai ghi \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}\ (1 \leq a_{i} \leq 10^{9};i = 1,2,\ldots,n)\).

Kết quả:

+ Ghi hai số nguyên dương cho biết độ dài và chỉ số phần tử đầu tiên của đoạn con tìm được, hoặc ghi ra số 0 nếu không tồn tại đoạn con nào thỏa mãn điều kiện của bài toán.

Ví dụ:

Ràng buộc:

+ Có 30% số test tương ứng 30% số điểm với \(n \leq 100\)

+ Có 60% số test tương ứng 60% số điểm với \(n \leq 5000\)