PKGROUP - Chia Nhóm
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Có N người được đánh số từ 1 đến N . Mỗi người có thể quen biết số người trong N-1 người còn lại . Hãy chia những người này thành 2 nhóm thỏa mãn các điều kiên sau :
- Mỗi người phải thuộc một nhóm
- Mỗi nhóm phải có ít nhất một người
- Mỗi người trong nhóm phải biết hết những người còn lại trong nhóm đó
Sư chênh lệch về số người giữa 2 nhóm càng ít càng tốt
Yêu cầu
Cho biết thông tin quan hệ của mỗi người hãy in ra độ chênh lệch nhỏ nhất hoặc cho biết không tồn tại cách chia thỏa mãn
Dữ liệu vào
Một số bộ test có dạng
- Dòng đầu tiên chưa số nguyên N, 1 <= N <= 1000
- Dòng thứ i trong số N dòng tiếp theo ghi danh sách những người mà người thứ i quen biết dưới dạng dãy số nguyên kết thúc bằng số 0 , các số cách nhau ít nhất 1 dấu cách
- Kết thúc bộ test là số -1
Kết quả
- In ra độ chênh lệch nhỏ nhất cho từng test , mỗi test in ra trên 1 dòng
- Trong trường hợp không có cách chia nhóm thỏa mãn in ra -1
Input 5 2 3 5 0 1 4 5 3 0 1 2 5 0 1 2 3 0 4 3 2 1 0 -1 Output 1
- Người up: only_love97
- Nguồn bài: Sưu tầm,make test Ðào Phan Khải