Gửi bài giải
Điểm:
1,21 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
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.
Input
Một số bộ test có dạng
- Dòng đầu tiên chưa số nguyên ~N~, ~1 \le N \le 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~
Output
- 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~
Sample 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
Sample Output
1
Bình luận