1919 - Pháp sư

Tạo bởi: GV. Bùi Phú Khuyên

Mô tả yêu cầu

n pháp sư với các chỉ số ma lực. Mỗi pháp sư được đánh số từ 1 đến n, và pháp sư thứ i có sức mạnh r_i (1 \leq i \leq n). Hiện tại, họ phải đối đầu với một kẻ thù vô cùng mạnh mẽ, với sức mạnh là S.

Các pháp sư này có khả năng kết hợp sức mạnh để chiến đấu hiệu quả hơn, và họ đặc biệt thích hợp tác theo cặp. Khi hai pháp sư kết hợp, sức mạnh tổng hợp của họ sẽ bằng tổng sức mạnh của từng người. Mục tiêu của bạn là đếm xem có bao nhiêu cặp pháp sư (i, j) (i \neq j) có sức mạnh tổng hợp đủ mạnh để đánh bại kẻ thù.

Để chiến thắng, sức mạnh của cặp pháp sư phải lớn hơn sức mạnh S của kẻ thù. Nếu hai pháp sư có cùng sức mạnh thì sẽ dẫn đến kết quả hoà và không được tính là thắng. Một cặp (i, j)(j, i) được xem là cùng một cặp, chỉ tính một lần.

Dữ liệu vào

Dữ liệu bao gồm nhiều trường hợp kiểm tra. Mỗi trường hợp được cho dưới dạng:

17301686366173.png

Trong đó:

  • n: số lượng pháp sư.
  • S: sức mạnh của kẻ thù.
  • r_i: sức mạnh của pháp sư thứ i.

Kết thúc đầu vào là một dòng chứa 0 0, báo hiệu kết thúc.

Dữ liệu ra

Với mỗi trường hợp kiểm tra, in ra số lượng cặp (i, j) thỏa mãn điều kiện đánh bại kẻ thù trên một dòng.

Giới hạn

  • Tất cả các giá trị đều là số nguyên.
  • 1 \leq n \leq 20,000.
  • 1 \leq r_i \leq 100.
  • 1 \leq S \leq 100.
  • Số lượng trường hợp kiểm tra không quá 100.

Ví dụ

Dữ liệu vào Sao chép
3 7
1
3
10
0 0
Dữ liệu ra Sao chép
2

Gợi ý/Hướng dẫn

Trong ví dụ này, có 2 cặp pháp sư có tổng sức mạnh lớn hơn S = 7, giúp họ đánh bại được kẻ thù.

Đăng nhập để làm bài
Thông tin
Giới hạn thời gian 1 giây
Giới hạn bộ nhớ 128 MB