Đếm Bạn Bè

Đề bài

Mô tả

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 (2N500).
  • 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

  • 2N500
  • Mỗi số trong danh sách có giá trị từ 0 đến N1.
  • Đả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.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0