SEMINAR - Xếp lịch hội nghị
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: AresGod

Một hội nghị chuyên đề có M tiểu ban (đánh số từ 1 đến M), được tổ chức tại một khu hội nghị có N phòng (đánh số từ 1 đến N). Theo yêu cầu chuyên môn, mỗi tiểu ban cần được bố trí một số lượt phòng, mỗi phòng trong một ngày tại một số phòng nào đó phù hợp với nó đồng thời không được có quá một tiểu ban làm việc cùng lúc tại cùng một phòng (như vậy, mỗi tiểu ban có thể làm việc cùng lúc tại nhiều hơn một phòng nếu bố trí được phòng phù hợp).

Yêu cầu: Cho biết số lượt phòng cần làm việc của mỗi tiểu ban và danh sách phòng mà mỗi tiểu ban là phù hợp với chúng, hãy tìm một cách bố trí sao cho hội nghị diễn ra trong một số ít nhất ngày có thể được.

Dữ liệu nhập: 

- Dòng đầu ghi hai số nguyên dương M, N (1  M, N ≤ 100).

- Dòng thứ i trong M dòng tiếp theo: bắt đầu bởi một số pi là số lượt phòng mà tiểu ban i cần để làm việc, sau đó là số q thể hiện số các phòng phù hợp với tiểu ban i, qi  số tiếp theo là danh sách các phòng phù hợp với tiểu ban i.

Ràng buộc: 1  pi ≤ 3, 1 ≤ qi ≤ N

Dữ liệu xuất: Một số duy nhất là số ngày ít nhất cần để hội nghị hoàn thành công việc.

 

Ví dụ

  • input
    5 4
    1 2 2 3
    1 1 4
    2 2 1 3
    1 1 3
    3 2 2 4
    output
    2

Giải thích: Có thể xếp lịch như sau để hội nghị diễn ra trong 2 ngày:

- Tiểu ban 1 dùng phòng 3 vào ngày 1

- Tiểu ban 2 dùng phòng 4 vào ngày 1

- Tiểu ban 3 dùng phòng 1 vào ngày 1 và ngày 2

- Tiểu ban 4 dùng phòng 3 vào ngày 2

- Tiểu ban 5 dùng phòng 2 vào ngày 1,2 và phòng 4 vào ngày 2

 

Back to Top