Câu chuyện tình yêu Elo Cruz và Mara ở Philippines là một minh chứng cho tình yêu đích thực, không màng đến ngoại hình. Họ khiến cư dân giới phải khâm phục vì một tình yêu bất chấp những khác biệt về ngoại hình. Tuy nhiên admin rất lo lắng cho Elo, không biết anh chàng này sẽ phải chọn cách nào để khiêu vũ với vợ. Cho nên trong buổi tiệc khiêu vũ “Cơn gió đêm hè!” sắp đến đây admin muốn các cặp đôi có chiều cao chênh lệch phải đúng bằng K mới được khiêu vũ cùng nhau.
Yêu cầu: Bạn hãy tính giúp cho admin xem có thể có bao nhiêu cách sắp xếp từng cặp đôi với nhau thỏa mãn.
Dữ liệu: Vào từ file khieuvu.inp gồm
- Dòng đầu tiên là N - số lượng người tham gia bữa tiệc và số K (2 ≤ N ≤ 10; 0 ≤ K ≤ 105)
- Dòng thứ hai là chiều cao của N người tham gia bữa tiệc (0 ≤ Hi ≤ 109)
Kết quả: Ghi ra file khieuvu.out một số duy nhất là kết quả của bài toán.
|
khieuvu.inp |
khieuvu.out |
|
6 2 1 3 3 3 9 5 |
6 |
Gợi ý: không mất tính tổng quát bài toán ta sắp xếp mảng chiều cao h thành dãy không giảm (tăng dần), vì nếu (a, b) là một cặp thì cặp (b, a) không được tính nữa. Ta duyệt i từ 1 đến n-1, với mỗi i ta tìm: vị trí left là vị trí đầu tiên trong đoạn từ [i+1, n] mà h[left] == h[i] + k; vị trí right là vị trí cuối cùng trong đoạn từ [i+1, n] mà h[right] h[i] + k. Như vậy số cặp ghép với h[i] sẽ là right – left +1 (chú ý biện luận trường hợp không thỏa mãn và kết quả bài toán vượt kiểu int). Độ phức tạp thuật toán là O(nlogn)