KEBA2 - Kết bạn (OLP Không chuyên 2009)

Theo quan niệm của người Á Đông cổ, mỗi cá nhân khi sinh ra đều ứng với một ngôi sao, được gọi là sao chiếu mệnh. Các hoạt động của cá nhân đều bị chi phối bởi ngôi sao này, kể cả quá trình kết bạn – hẹn hò. Theo thuyết Âm dương – Ngũ hành, hai người chỉ có thể tạo lập mối quan hệ bền vững khi các sao chiếu mệnh của họ không có các thuộc tính tương khắc. Qua hàng nghìn năm quan sát và chiêm nghiệm, các chiêm tinh gia đã ghi nhận được n sao và hầu hết các tính chất tương sinh – tương khắc giữa chúng. Để có thể nhanh chóng đáp ứng nhu cầu kiểm tra độ tương hợp của các sao, hiệp hội ABS (Association of Broker for Single) tạo lập cơ sở dữ liệu ghi nhận tính chất của tất cả các sao đã khảo sát được. Trong cơ sở dữ liệu này, các sao được đánh số từ 1 tới n; sao thứ i có một giá trị s_i thể hiện khả năng thích nghi của sao gọi là độ thích nghi. Hai sao khác nhau có thể có cùng độ thích nghi. Thông qua độ thích nghi của các sao, người ta xác định khả năng tương hợp của chúng. Khả năng tương hợp của 2 sao được tính bằng tổng 2 độ thích nghi của chúng.

Bài toán: Cho số nguyên dương n, dãy s₁, s₂, …, s_n là độ thích nghi của các sao và số nguyên B. Hãy xác định số lượng T các cặp sao (i, j) mà s_i + s_j = B,với 1 ≤ i< j ≤ n.

Ví dụ: trong 5 sao với độ thích nghi là 3, 5, 6, 5, 3 thì có 4 cặp có khả năng tương hợp bằng 8.

Dữ liệu nhập:

- Dòng thứ nhất là hai số nguyên n và B (2 ≤ n ≤ 10⁵, |B| ≤ 10⁹).

- Dòng thứ hai là n số nguyên s₁, s₂, …, s_n  mỗi số cách nhau một khoảng trắng (|s_i| ≤ 10¹⁵)

Dữ liệu xuất:

- Là số nguyên T.

Ví dụ

• input
  5 8
  3 5 6 5 3
  output
  4

Lần 1:

Đương nhiên là cách đầu tiên nghĩ đến sẽ là duyệt i, j tìm ra bộ phù hợp rồi!

Nhưng như đã nó nói là O(n2), không mảy may có cơ hội AC với độ phức tạp này!

We have to find another way!

Chỉ đơn giản là dùng map để đếm số lượng B-a[i] trước nó là ra!

Code: http://ideone.com/VUUgzj
#namlunoy