Bài 18.4. Thư Viện Sách Cổ - Độ khó: Khá

Trong một thư viện sách cổ khổng lồ, mỗi cuốn sách đều có một số trang nhất định. Nhà thủ thư muốn tìm kiếm các cặp sách mà tổng số trang của chúng chính xác bằng một "số trang kỷ niệm" nhất định để chuẩn bị cho một triển lãm đặc biệt. Với hàng triệu cuốn sách, việc tìm kiếm thủ công là không thể. Bạn cần giúp nhà thủ thư tự động hóa việc này.

Mô tả bài tập: Bạn được cung cấp một danh sách các số nguyên, mỗi số đại diện cho số trang của một cuốn sách. Và một số nguyên K là "số trang kỷ niệm" mục tiêu. Nhiệm vụ của bạn là tìm xem có tồn tại ít nhất một cặp sách phân biệt (có nghĩa là hai cuốn sách khác nhau, không phải một cuốn sách tự cộng với chính nó) mà tổng số trang của chúng bằng K hay không. Nếu có, trả về true, ngược lại false. Hãy tối ưu hóa giải pháp của bạn, đặc biệt khi số lượng sách có thể rất lớn.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên N và K (1 <= N <= 10^5, 1 <= K <= 2 * 10^9). N là số lượng sách, K là tổng trang mục tiêu. Dòng thứ hai chứa N số nguyên P_1, P_2, ..., P_N (1 <= P_i <= 10^9), là số trang của từng cuốn sách.

OUTPUT FORMAT

In ra true nếu tìm thấy cặp sách, ngược lại in ra false.

Ví dụ:

Input:

5 10
1 2 3 4 5

Output:

true

Giải thích:

• Có các cặp sách có tổng bằng 10: (5, 5) nhưng đây là một cuốn sách tự cộng với chính nó (không phân biệt).
• Cặp (4, 6) không tồn tại 6.
• Cặp (3, 7) không tồn tại 7.
• Cặp (2, 8) không tồn tại 8.
• Cặp (1, 9) không tồn tại 9. Điều kiện cặp sách phân biệt là quan trọng ở đây. Nếu có 2 cuốn sách với số trang 5, thì cặp (5,5) là hợp lệ. Với 1 2 3 4 5 và K=10, không có cặp nào. Wait, my example for 10 is bad for "distinct books" if the input values are distinct. Let's make the example clearer: Input:

  5 10
  1 2 5 5 8

  Output:

  true

  Giải thích:
• Danh sách sách: [1, 2, 5, 5, 8]
• K = 10.
• Cặp (2, 8) có tổng 10. 2 nằm ở chỉ số 1 và 8 nằm ở chỉ số 4. Đây là hai cuốn sách khác nhau, nên kết quả là true.
• Cặp (5, 5) (chỉ số 2 và chỉ số 3) cũng có tổng 10. Đây cũng là hai cuốn sách khác nhau.

Input:

3 7
1 2 3

Output:

false

Giải thích:

• Các cặp có thể: (1,2) = 3, (1,3) = 4, (2,3) = 5.
• Không có cặp nào có tổng bằng 7.