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

Bối cảnh

Một hệ thống phối ghép cần chọn hai giá trị khác vị trí sao cho tổng của chúng gần mục tiêu S nhất. Nếu nhiều cặp có cùng độ lệch |x+y-S|, ưu tiên cặp có giá trị nhỏ hơn ở phần tử thứ nhất; nếu vẫn hòa, ưu tiên phần tử thứ hai nhỏ hơn. Sau sort, ta luôn biểu diễn cặp dưới dạng x≤y.

B16 chưa học two pointers như một kỹ thuật riêng, nhưng đã có sort và binary search. Với mỗi vị trí i, ta cần tìm một giá trị gần S-a[i] trong phần hậu tố i+1..n-1. Binary search vị trí chèn trong hậu tố cho tối đa hai ứng viên đủ để xét. Bài Medium khó hơn membership vì phải quản lý cặp chỉ số khác nhau, hai ứng viên lân cận và tie-break toàn cục.

Yêu cầu

1. Sort dãy tăng dần.
2. Với mỗi i, binary search trong đoạn i+1..n-1 giá trị gần S-a[i].
3. Xét tối đa hai ứng viên quanh vị trí chèn.
4. Chọn cặp có độ lệch nhỏ nhất; tie lexicographic theo (x,y).
5. In x y diff.

Input

Dòng 1 n S; dòng 2 n số.

Output

Một dòng x y diff.

Ràng buộc

2≤n≤5000, mọi phép tính nằm trong long long.

Ví dụ 1

Input

6 10
1 8 4 6 3 12

Output

4 6 0

Giải thích

Sau sort ta có 1 3 4 6 8 12. Khi i ở giá trị 4, target là 6 và binary search trong hậu tố gặp đúng 6, tạo tổng 10 với diff 0. Độ lệch 0 là tốt nhất có thể nên không cặp nào vượt được; cặp output là 4 6 0. Các cặp khác dù cũng được xét không thể có diff âm.

Ví dụ 2

Input

4 0
-5 -1 2 7

Output

-1 2 1

Giải thích

Dãy sort là -5 -1 2 7, mục tiêu S=0. Cặp -1+2=1 có diff 1; cặp -5+7=2 diff 2; các cặp còn lại xa hơn. Vì diff nhỏ nhất là 1, output -1 2 1. Binary search cho từng a[i] tìm đúng các ứng viên gần phần bù cần thiết.

Thông tin học tập

• Module: M05
• Buổi: B16
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: sort, binary search, pair search, closest sum, tie-break
• Giới hạn kiến thức: B01-B16
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100