Đếm Bạn Bè

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ người trong một mạng xã hội. Mỗi người có một số bạn bè nhất định (quan hệ bạn bè là hai chiều). Ai đó đã liệt kê số bạn bè của mỗi người, nhưng lại ghi nhầm thành $N + 1$ số thay vì $N$ số — tức có đúng một số thừa trong danh sách.

Hãy xác định những vị trí nào trong danh sách có thể là số thừa. Cụ thể, nếu bỏ số ở vị trí $i$ , $N$ số còn lại phải tạo thành một dãy bậc hợp lệ (tức tồn tại một đồ thị đơn $N$ đỉnh có dãy bậc đó).

Dữ liệu vào

Dòng đầu tiên: số nguyên $N$ ( $2 \leq N \leq 500$ ).
$N + 1$ dòng tiếp theo: mỗi dòng chứa một số nguyên không âm, là số bạn bè (hoặc số thừa).

Dữ liệu ra

Dòng đầu tiên: số nguyên $K$ — số vị trí có thể là số thừa.
$K$ dòng tiếp theo: các vị trí đó (đánh số từ 1), theo thứ tự tăng dần.

Ràng buộc

$2 \leq N \leq 500$
Mỗi số trong danh sách có giá trị từ $0$ đến $N - 1$ .
Đảm bảo tồn tại ít nhất một vị trí hợp lệ.

Ví dụ

Input	Output	Giải thích
4 1 2 2 1 3	3 1 4 5	Bỏ số ở vị trí 1 (giá trị 1): còn ${2, 2, 1, 3}$ — hợp lệ (đồ thị 4 đỉnh). Bỏ vị trí 4 (giá trị 1): còn ${1, 2, 2, 3}$ — hợp lệ. Bỏ vị trí 5 (giá trị 3): còn ${1, 2, 2, 1}$ — hợp lệ. Bỏ vị trí 2 hoặc 3 (giá trị 2): tổng lẻ → không hợp lệ.

Bình luận

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