Bài 6.2. Phân Tích Dữ Liệu Khách Hàng - [Độ khó: Khá]

Mô tả bài tập: Một cửa hàng bán lẻ đang phân tích dữ liệu mua sắm của khách hàng. Họ có một danh sách các "điểm trung thành" mà mỗi khách hàng đạt được sau mỗi giao dịch. Cửa hàng muốn tìm hiểu xem có bao nhiêu cặp khách hàng (không phân biệt thứ tự) có tổng điểm trung thành bằng đúng một giá trị mục tiêu K để triển khai chương trình khuyến mãi cho các cặp này. Mỗi khách hàng trong danh sách là duy nhất.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên N và K (1 <= N <= 1000, 0 <= K <= 2000). Dòng thứ hai chứa N số nguyên P_1, P_2, ..., P_N (0 <= P_i <= 1000), là điểm trung thành của N khách hàng.

OUTPUT FORMAT

In ra một số nguyên duy nhất là tổng số cặp khách hàng có tổng điểm trung thành bằng K. Một cặp (P_i, P_j) với i != j được tính là một cặp. Để tránh đếm lặp các cặp (P_i, P_j) và (P_j, P_i) (vì thứ tự không quan trọng), bạn chỉ nên xem xét các cặp mà chỉ số i nhỏ hơn chỉ số j.

Ví dụ 1:

Input:

5 6
1 5 2 4 3

Output:

2

Giải thích:

• Các cặp khách hàng có tổng điểm trung thành bằng 6 là:
  • Khách hàng có điểm 1 (chỉ số 0) và khách hàng có điểm 5 (chỉ số 1).
  • Khách hàng có điểm 2 (chỉ số 2) và khách hàng có điểm 4 (chỉ số 3).
• Tổng cộng có 2 cặp thỏa mãn.

Ví dụ 2:

Input:

6 10
5 5 1 9 5 5

Output:

7

Giải thích: Xét các cặp (P_i, P_j) với i < j và P_i + P_j = 10:

• P_0=5:
  • Với P_1=5 (P_0 + P_1 = 10)
  • Với P_4=5 (P_0 + P_4 = 10)
  • Với P_5=5 (P_0 + P_5 = 10)
• P_1=5:
  • Với P_4=5 (P_1 + P_4 = 10) (đã xét P_0 + P_1 ở trên, không xét P_1 + P_0 nữa)
  • Với P_5=5 (P_1 + P_5 = 10)
• P_2=1:
  • Với P_3=9 (P_2 + P_3 = 10)
• P_4=5:
  • Với P_5=5 (P_4 + P_5 = 10) Tổng cộng có 7 cặp thỏa mãn.