Chọn đề ICPC
Đề bài
Mô tả
Khi tổ chức một kỳ thi ICPC, một trong những công việc khó khăn nhất của ban khoa học là xây dựng một bộ đề tốt. May mắn thay, năm nay ban khoa học nhận được đề xuất bài thi. Mỗi đề xuất được gắn ít nhất một trong các nhãn sau: quy hoạch động (dp), lý thuyết đồ thị (graph), toán và hình học (mathgeo), cấu trúc dữ liệu (ds) và ad hoc (adhoc).
Ban khoa học muốn có một bộ đề cân bằng, vì vậy đặt ra các quy tắc chọn đề sau:
- Số bài có nhãn quy hoạch động phải nằm trong đoạn .
- Số bài có nhãn lý thuyết đồ thị phải nằm trong đoạn .
- Số bài có nhãn toán và hình học phải nằm trong đoạn .
- Số bài có nhãn cấu trúc dữ liệu phải nằm trong đoạn .
- Số bài có nhãn ad hoc phải nằm trong đoạn .
Cho số đề xuất , các nhãn của từng đề xuất và các số , , , , , , , , , , hãy đếm số bộ đề khác rỗng thỏa mãn tất cả các quy tắc trên. Mỗi bộ đề là một tập con của đề xuất. Hai bộ đề và được coi là khác nhau khi và chỉ khi có ít nhất một đề xuất thuộc nhưng không thuộc , hoặc ngược lại.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên , số đề xuất.
- dòng tiếp theo, dòng thứ mô tả đề xuất thứ : bắt đầu bằng số nguyên () là số nhãn của đề xuất, tiếp theo là xâu đôi một phân biệt mô tả các nhãn. Mỗi xâu là một trong các nhãn dp, graph, mathgeo, ds, adhoc.
- Dòng tiếp theo chứa hai số nguyên và .
- Dòng tiếp theo chứa hai số nguyên và .
- Dòng tiếp theo chứa hai số nguyên và .
- Dòng tiếp theo chứa hai số nguyên và .
- Dòng cuối cùng chứa hai số nguyên và .
Dữ liệu ra
In ra một số nguyên là số bộ đề khác nhau thỏa mãn các quy tắc chọn đề.
Ràng buộc
- .
- , , .
- , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 1 dp 1 graph 1 mathgeo 1 ds 1 adhoc 2 dp graph 1 2 1 2 1 2 1 2 1 2 |
5 | Phải dùng cả ba đề xuất , , . Với các đề xuất , , , có cách chọn: , , , và . |
| 2 2 dp adhoc 2 ds graph 1 2 1 2 1 2 1 2 1 2 |
0 | Không có đề xuất nào mang nhãn mathgeo nên không có bộ đề nào thỏa mãn. |
Bình luận