Cặp gần mục tiêu nhất

Bối cảnh

Trong một vòng tuyển chọn dữ liệu, mỗi phần tử của mảng là mức đóng góp của một ứng viên vào một chỉ số tổng hợp. Ban giám khảo cần ghép đúng hai vị trí khác nhau sao cho tổng của hai giá trị gần một mục tiêu S nhất có thể. Độ lệch của cặp (i,j) được định nghĩa là |a[i] + a[j] - S|.

Ở các buổi sau có thể xuất hiện các kỹ thuật sắp xếp hoặc cấu trúc dữ liệu giúp tối ưu hơn, nhưng tại B09 mục tiêu là xây dựng lời giải đúng hoàn toàn chỉ bằng mảng, vòng lặp và điều kiện. Vì vậy bạn phải duyệt các cặp hợp lệ một cách có tổ chức. Nếu nhiều cặp có cùng độ lệch tốt nhất, chọn cặp có i nhỏ hơn; nếu vẫn bằng nhau, chọn j nhỏ hơn. Quy tắc phá hòa khiến bài không chỉ dừng ở việc tìm một giá trị tối ưu mà còn yêu cầu quản lý trạng thái đáp án cẩn thận.

Không được dùng sort/two-pointers vì đó là kiến thức của module sau. Với n vừa phải, duyệt mọi cặp là lời giải phù hợp và vẫn đủ tính chất tối ưu hóa để luyện cách cập nhật best.

Yêu cầu

1. Duyệt i từ 0 đến n-1.
2. Duyệt j từ i+1 đến n-1.
3. Tính độ lệch và cập nhật đáp án theo thứ tự: diff nhỏ hơn, rồi i nhỏ hơn, rồi j nhỏ hơn.

Input

Dòng 1: n S. Dòng 2: n số nguyên.

Output

Một dòng i j diff với i<j và diff nhỏ nhất.

Ràng buộc

2 ≤ n ≤ 2000, |a[i]|,|S| ≤ 10^9.

Ví dụ 1

Input

5 10
1 8 4 6 12

Output

2 3 0

Giải thích

Mục tiêu là tìm cặp chỉ số có tổng gần S = 10 nhất. Một số cặp đáng chú ý là (0,1) cho 1+8=9, sai lệch 1; (0,4) cho 13, sai lệch 3; và (2,3) cho 4+6=10, sai lệch 0. Sai lệch 0 là nhỏ nhất có thể nên cặp (2,3) chắc chắn tối ưu. Vì thế output là 2 3 0: hai chỉ số và độ lệch tuyệt đối bằng 0.

Ví dụ 2

Input

2 0
-5 7

Output

0 1 2

Giải thích

Dãy chỉ có hai phần tử nên chỉ tồn tại một cặp hợp lệ (0,1). Tổng của cặp là -5+7 = 2; so với mục tiêu S=0, độ lệch tuyệt đối là |2-0| = 2. Không có cặp khác để so sánh, nên kết quả là 0 1 2.

Thông tin học tập

• Module: M03
• Buổi: B09
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: static arrays, pair enumeration, absolute difference, optimization, lexicographic tie-break
• Giới hạn kiến thức: B01-B09
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100