Chia Nhóm

Xem dạng PDF

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:
Sưu tầm,make test Ðào Phan Khả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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.