Cặp Tờ Khai Cảng Cái Mép

Mô tả

Tại cửa kiểm soát Cảng Cái Mép, mỗi ngày có hàng chục tờ khai hải quan đi qua. Để tối ưu việc sắp xếp hàng lên tàu, bộ phận điều phối cần ghép đôi hai tờ khai sao cho tổng số lượng container của đúng hai tờ đó bằng đúng sức chứa còn trống S của một khoang tàu đang chờ đóng hàng.

Hệ thống đã xuất ra danh sách số lượng container của từng tờ khai theo thứ tự tăng dần. Bạn hãy viết chương trình xác định xem có tồn tại một cặp tờ khai (hai tờ khác vị trí) có tổng đúng bằng S hay không. Nếu có, trả về true; ngược lại trả về false.

Đầu vào

• Dòng đầu tiên chứa số nguyên n (số lượng tờ khai) và số nguyên S (mục tiêu tổng), cách nhau bởi một khoảng trắng.
• Dòng thứ hai chứa n số nguyên a[0], a[1], ..., a[n-1] là số lượng container của từng tờ khai, đã được sắp xếp tăng dần, cách nhau bởi khoảng trắng.

Đầu ra

• In ra true nếu tồn tại cặp tờ khai có tổng đúng bằng S, ngược lại in ra false.

Ràng buộc

• 2 ≤ n ≤ 10^5
• 1 ≤ a[i] ≤ 10^6 với mọi i
• 2 ≤ S ≤ 2 × 10^6
• Mảng đầu vào luôn được sắp xếp tăng dần (không giảm).

Ví dụ

Ví dụ 1:

5 10 1 3 5 7 9

true

Giải thích: Đặt con trỏ trái tại tờ khai đầu tiên (1) và con trỏ phải tại tờ khai cuối cùng (9). Tổng 1 + 9 = 10 bằng đúng mục tiêu S, ta trả về true ngay lập tức.

Ví dụ 2:

4 100 10 20 30 40

false

Giải thích: Bắt đầu với hai con trỏ ở hai đầu, 10 + 40 = 50, nhỏ hơn 100 nên tăng con trỏ trái. Tiếp tục 20 + 40 = 60, vẫn nhỏ hơn, lại tăng. Đến 30 + 40 = 70 thì hai con trỏ chạm nhau, không còn cặp nào để kiểm tra. Trả về false.