Truy Tìm Người Nổi Tiếng
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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:
- 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à1thì đặt $c = i$; ngược lại giữ nguyên $c$. - 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ỏi
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
0hoặc1mô tả ma trậnknows(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$
Community Discussion