Trại giao lưu
Đề bài
Mô tả
Ở Gakuentoshi, mỗi người đều có một kỹ năng riêng của mình. Uiharu và Shirai tổ chức một buổi giao lưu để các bạn dạy kỹ năng cho nhau và làm quen với bạn mới. Uiharu và các bạn của cô là đội Đỏ, Shirai và các bạn của cô là đội Trắng.
Mỗi người trong đội Đỏ sẽ chọn một thành viên của đội Trắng làm học trò, và mỗi người trong đội Trắng sẽ chọn một thành viên của đội Đỏ làm học trò. Mọi người đều chọn một học trò, và mỗi người chỉ được làm học trò của đúng một người.
Đầu tiên, đội Đỏ dạy cho học trò của mình kỹ năng riêng của họ, đồng thời đội Trắng cũng dạy cho học trò của mình kỹ năng riêng của họ. Lúc này mỗi người đã học được một kỹ năng mới. Sau đó, mỗi người lại dạy cho học trò của mình kỹ năng mới vừa học được. Quá trình này tiếp tục cho đến khi không ai học được kỹ năng mới nữa.
Mỗi đội có người, và đã có người chọn xong học trò. Uiharu muốn biết còn bao nhiêu cách chọn để cuối cùng mỗi người đều học được kỹ năng của tất cả những người tham gia. Hai cách được coi là khác nhau nếu có một người chọn học trò khác nhau.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên là số bộ dữ liệu.
- Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa hai số nguyên và : mỗi đội có người và đã có người chọn học trò.
- dòng tiếp theo, dòng thứ chứa một chữ cái và hai số nguyên , . là R hoặc W: R nghĩa là thành viên thứ của đội Đỏ chọn thành viên thứ của đội Trắng làm học trò; W nghĩa là thành viên thứ của đội Trắng chọn thành viên thứ của đội Đỏ làm học trò. Mỗi người xuất hiện tối đa một lần với vai trò người chọn.
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra trên một dòng số cách chọn để mỗi người đều học được kỹ năng của tất cả những người tham gia.
Ràng buộc
- .
- .
- .
- là R hoặc W.
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 1 1 R 1 1 3 2 R 3 1 W 2 2 |
1 1 |
Bộ thứ nhất: thành viên Trắng duy nhất buộc phải chọn thành viên Đỏ duy nhất. |
| 1 2 0 |
2 | Đỏ có cách chọn học trò, sau đó mọi lựa chọn còn lại bị buộc để bốn người tạo thành một vòng truyền kỹ năng duy nhất. |
Bình luận