Bài 8: Tập xe

Đăng bởi Admin

Tháng 10 8, 2022

https://chuyenhalong.ucode.vn/problems/tap-xe-117988

Cô giáo trường tiểu học Sông Đà đang dạy $n$ học sinh tập xe đạp, các học sinh được đánh số từ $1$ tới $n$ , học sinh thứ $i$ có trọng lượng là $a_i$ . Có một xe đạp duy nhất với tải trọng là $m$ , hai học sinh chỉ có thể cùng lên xe nếu tổng trọng lượng của hai học sinh không vượt quá $m$ .

Cô giáo tự hỏi có bao nhiêu cách chọn hai học sinh khác nhau cho cùng lên xe, sau nhiều giờ tính toán không có kết quả, cô quyết định hỏi các chuyên gia lập trình CSP (Counting Student Pairs) về đáp số.
Yêu cầu: Đếm số cặp chỉ số $i, j$ trong đó $i<j$ và $a_i+a_j \leq m$

Đầu vào
– Dòng 1 chứa hai số nguyên dương $\mathrm{n} \leq 10^6, \mathrm{~m} \leq 10^6$
– Dòng 2 chứa $n$ số nguyên dương $a_1, a_2, \ldots, a_n\left(\forall \mathrm{i}: a_i \leq 10^6\right)$