1961 - TINH GIẢN BIÊN CHẾ

Tạo bởi: GV. Nguyễn Huy Cường

Mô tả yêu cầu

Trong một cơ quan hành chính có N nhân sự, mỗi người đang đảm nhiệm một công việc riêng biệt. Mỗi công việc bao gồm một tập hợp các nhiệm vụ con, được biểu diễn bằng các số nguyên dương.

Thực hiện chủ trương sắp xếp tinh gọn lại bộ máy, Ban lãnh đạo phải thực hiên kế hoạch họp nhất theo yêu cầu bằng cách gộp một số đầu việc lại với nhau sao cho một người có thể kiêm nhiệm nhiều công việc cùng lúc.

Tuy nhiên, để đảm bảo tính hiệu quả và tránh chồng chéo, một người sẽ bị tinh giản khi và chỉ khi toàn bộ nhiệm vụ của người đó được thực hiện bao phủ hoàn toàn bởi một người khác, thì người đó mới có thể bị thay thế.

Nói cách khác: nếu người A thực hiện toàn bộ nhiệm vụ của người B (và có thể có thêm) thì người A có thể thay thế người B trong công việc.

Yêu cầu: Hãy xác định số lượng người ít nhất còn lại sau khi thực hiện tinh gọn bộ máy một cách tối ưu, sao cho không ai có thể bị thay thế nhiều hơn một lần.

Dữ liệu vào

  • Dòng đầu tiên là số nguyên N — số lượng nhân sự (1 ≤ N ≤ 1000).
  • N Dòng tiếp theo, mỗi dòng bắt đầu bằng một số nguyên kᵢ (số nhiệm vụ của người thứ i), theo sau là kᵢ số nguyên dương biểu diễn các nhiệm vụ của người đó.

Dữ liệu ra

Một dòng duy nhất là số nguyên — số người còn lại sau khi đã tinh gọn bộ máy tối ưu

Giới hạn

  • 1 ≤ N ≤ 1000
  • 1 ≤ kᵢ ≤ 10000

Ví dụ

Dữ liệu vào Sao chép
3
3 1 2 3
2 1 4
2 3 5
Dữ liệu ra Sao chép
3
Dữ liệu vào Sao chép
4
3 1 2 3
2 1 2
2 1 3 
2 3 4
Dữ liệu ra Sao chép
2

Gợi ý/Hướng dẫn

(1): Cần giữ lại cả 3 người vì không có người nào có tất cả nhiệm vụ của người khác.

(2): Người 1 có nhiệm vụ {1, 2, 3}, bao phủ người 2 và người 3. Người 4 không bị ai bao phủ nên vẫn giữ lại. → Giữ lại người 1 và người 4 → 2 người.

Đăng nhập để làm bài
Thông tin
Giới hạn thời gian 1 giây
Giới hạn bộ nhớ 128 MB