Truy Tìm Người Nổi Tiếng

Buổi 63 — Interactive & Constructive Graphs
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Đây là bài toán mô phỏng tương tác (không tương tác trực tiếp — toàn bộ ma trận quan hệ được cho trước).

Trong một buổi tiệc có $N$ người đánh số từ $1$ đến $N$. Người $X$ được gọi là người nổi tiếng nếu:

  • Mọi người khác ($j \ne X$) đều biết $X$.
  • $X$ không biết bất kỳ ai khác ($j \ne X$).

Mỗi lần hỏi knows(a, b) cho biết $a$ có biết $b$ hay không. Chiến lược tối ưu gồm 2 giai đoạn:

  1. Loại trừ: Khởi tạo ứng viên $c = 1$. Với $i = 2, 3, \dots, N$, hỏi knows(c, i): nếu kết quả là 1 thì đặt $c = i$; ngược lại giữ nguyên $c$.
  2. Kiểm chứng: Với $j = 1, 2, \dots, N$ ($j \ne c$), theo đúng thứ tự tăng dần:
    • Hỏi knows(c, j): nếu là 1, kết luận ngay không có người nổi tiếng (-1) và dừng.
    • Ngược lại hỏi knows(j, c): nếu là 0, kết luận ngay không có người nổi tiếng (-1) và dừng.

Hãy mô phỏng quá trình trên và in ra chỉ số người nổi tiếng (hoặc -1) cùng tổng số lần hỏi knows đã thực hiện.

Dữ liệu vào
  • Dòng đầu ghi số nguyên $N$ ($1 \le N \le 1000$).
  • $N$ dòng tiếp theo, mỗi dòng gồm $N$ số nguyên 0 hoặc 1 mô tả ma trận knows (giả sử knows[i][i] = 0).
Dữ liệu ra
  • Hai số nguyên trên một dòng: chỉ số người nổi tiếng (hoặc -1) và tổng số câu hỏi đã dùng.
Ví dụ
Input Output
3
0 1 0
0 0 0
0 1 0
2 6
Giới hạn
  • $1 \le N \le 1000$
Draft saved