Ba tòa nhà
Đề bài
Mô tả
Bạn là chủ một công ty xây dựng trong thành phố. Công ty có công nhân, và có ba tòa nhà cần xây (gọi là tòa nhà A, B, C).
Bạn muốn phân công công nhân vào ba tòa nhà này: tòa nhà A, B, C nhận tối đa lần lượt , , công nhân. Mỗi công nhân được phân vào nhiều nhất một tòa nhà, và mỗi công nhân có nguyện vọng về những tòa nhà mà họ muốn được phân vào; một công nhân chỉ có thể được phân vào tòa nhà mà họ muốn.
Ví dụ, giả sử và (đánh số bốn công nhân là ):
- Chỉ công nhân muốn vào tòa nhà A.
- Chỉ công nhân muốn vào tòa nhà B.
- Cả hai công nhân và muốn vào tòa nhà C.
- Công nhân không muốn vào tòa nhà nào.
Trong trường hợp này, vì , ta phải chọn công nhân hoặc công nhân cho tòa nhà C. Công nhân chỉ có thể vào tòa nhà A hoặc tòa nhà B. Do đó, ta phân công được nhiều nhất hai công nhân.
Cho , , , và nguyện vọng của công nhân, hãy tính số công nhân lớn nhất có thể phân công vào các tòa nhà.
Dữ liệu vào
- Dòng đầu tiên chứa số bộ dữ liệu ().
- Mỗi bộ dữ liệu gồm:
- Dòng đầu chứa ().
- Dòng thứ hai chứa , , cách nhau bởi dấu cách ().
- Ba dòng tiếp theo mô tả những công nhân muốn vào từng tòa nhà. Dòng thứ nhất bắt đầu bằng (số công nhân muốn vào tòa nhà A), tiếp theo là số phân biệt (chỉ số của các công nhân đó, từ đến ), cách nhau bởi dấu cách. Tương tự, dòng thứ hai chứa và số, dòng thứ ba chứa và số ().
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra số công nhân lớn nhất có thể phân công vào ba tòa nhà, mỗi kết quả trên một dòng.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 5 2 1 1 4 1 2 3 4 1 4 1 5 4 1 1 1 1 1 1 1 2 2 3 |
4 2 |
Bộ 1: hai trong ba công nhân vào tòa nhà A, công nhân vào tòa nhà B, công nhân vào tòa nhà C. Bộ 2: chính là ví dụ trong đề bài. |
| 1 3 1 1 1 3 1 2 3 1 1 1 2 |
3 | Công nhân vào B, công nhân vào C, công nhân vào A. |
Bình luận