Khoảng cách độ khó
Đề bài
Mô tả
Mimi, một trò chơi âm nhạc theo nhịp phát hành vào năm 201x, đang thu hút ngày càng nhiều người chơi, từ thanh thiếu niên đến người lớn. Là một trò chơi mang tính xã hội, Mimi yêu cầu người chơi ghép thành từng cặp và cùng chọn một bài hát để chơi chung (lưu ý rằng trong phiên bản hư cấu này, mỗi bài hát chỉ có đúng một mức độ khó).
Tại một khu trò chơi, có một câu lạc bộ gồm người chơi Mimi sắp tham gia một buổi luyện tập. Người chơi thứ có mức độ khó bài hát ưa thích là , đây cũng là trình độ của họ. Không có hai người chơi nào có cùng trình độ.
Trưởng nhóm muốn chọn một tập con các người chơi và chia họ thành các cặp sao cho chênh lệch trình độ giữa hai người trong mỗi cặp không vượt quá . Chính thức, gọi là chỉ số của hai người chơi trong cặp thứ , thì phải có .
Trưởng nhóm muốn tạo được nhiều cặp nhất có thể cho buổi luyện tập. Nhiệm vụ của bạn là đếm số cách tạo được số cặp tối đa. Hai cách được coi là khác nhau khi và chỉ khi tồn tại ít nhất một cặp người chơi xuất hiện trong cách này nhưng không xuất hiện trong cách kia.
Dữ liệu vào
Mỗi test gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu (). Tiếp theo là mô tả các bộ dữ liệu.
- Dòng đầu tiên chứa số nguyên (): số người chơi trong câu lạc bộ.
- Dòng thứ hai chứa số nguyên (): trình độ của các người chơi. Đảm bảo mọi trình độ đều khác nhau.
Đảm bảo tổng trên tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một số nguyên: số cách tạo được số cặp tối đa, lấy theo modulo .
Ràng buộc
- .
- , tổng không vượt quá .
- , các đôi một khác nhau.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 6 2 4 5 7 9 10 6 1 3 4 9 8 5 2 1 100 |
1 2 1 |
Bộ 1: chọn các người chơi có trình độ và tạo hai cặp , . Đây là cách duy nhất để tạo hai cặp, và không thể tạo nhiều hơn hai cặp. Bộ 2: có 2 cách tạo hai cặp là và . Bộ 3: không thể tạo cặp nào, số cách tạo cặp là . |
| 3 5 3 1 5 2 4 4 13 10 12 11 7 1 2 3 5 6 7 8 |
3 1 2 |
Ví dụ bổ sung (không có trong đề gốc). Bộ 1: tạo được cặp, người bị bỏ ra là , hoặc . Bộ 2: chỉ có cách . Bộ 3: nhóm có cách, nhóm có cách. |
Bình luận