trang chủ / đề bài / icpcwf12_e

Thâm nhập

Đề bài

Mô tả

Chào buổi sáng, điệp viên W-12. Nhiệm vụ của anh, nếu anh chấp nhận, như sau.

Chúng ta đang thâm nhập vào Hiệp hội Hỗn loạn và Quậy phá (ACM) vô cùng xảo quyệt để triệt hạ bộ máy chỉ huy của chúng. Đáng tiếc là chúng dường như đã lường trước khả năng này, và đã thiết kế bộ máy chỉ huy phức tạp đến khó chịu, khiến việc thâm nhập của ta trở nên khá khó khăn.

Bộ máy chỉ huy của ACM được chia thành nhiều chi bộ. Với mỗi cặp chi bộ A và B, hoặc A kiểm soát B, hoặc B kiểm soát A. Nhưng quan hệ "kiểm soát" này có thể tạo thành vòng, nên có thể xảy ra chuyện A kiểm soát B, B kiểm soát C và C kiểm soát A.

Ta có thể cài điệp viên vào bất kỳ chi bộ nào. Thâm nhập một chi bộ cho ta quyền kiểm soát chi bộ đó và các chi bộ mà nó kiểm soát, nhưng không có quyền với chi bộ nào khác. Như trong ví dụ trên, thâm nhập A cho ta quyền kiểm soát A và B, nhưng không có C.

Để cuộc thâm nhập ACM thành công, ta phải giành được quyền kiểm soát tất cả các chi bộ của nó; nếu không, những chi bộ nằm ngoài tầm kiểm soát sẽ phát hiện ra ta và bắt đầu gây ra màn hỗn loạn và quậy phá đặc trưng của chúng.

Như anh biết, dạo này cấp trên siết chặt ngân sách, nên ta cần thực hiện nhiệm vụ một cách tiết kiệm nhất có thể. Nhiệm vụ của anh là tìm số chi bộ ít nhất cần thâm nhập để thành công.

Bản tóm tắt nhiệm vụ này sẽ tự hủy sau năm giờ. Chúc may mắn!

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test, đọc tới hết file. Dòng đầu tiên của mỗi bộ test chứa số chi bộ n của ACM (1≤n≤75). Mỗi dòng trong n dòng tiếp theo chứa một xâu nhị phân độ dài n, trong đó ký tự thứ i của dòng thứ j bằng 1 nếu chi bộ j kiểm soát chi bộ i, và bằng 0 nếu ngược lại (1≤i,j≤n).

Ký tự thứ i của dòng thứ i bằng 0, và với i≠j, đúng một trong hai điều sau xảy ra: ký tự thứ i của dòng thứ j bằng 1, hoặc ký tự thứ j của dòng thứ i bằng 1.

Dữ liệu ra

Với mỗi bộ test, in ra số thứ tự của bộ test theo định dạng trong ví dụ, tiếp theo là số nhỏ nhất m các chi bộ phải thâm nhập để giành quyền kiểm soát toàn bộ ACM. Sau đó in m số c1,…,cm theo thứ tự bất kỳ, là danh sách các chi bộ cần thâm nhập (các chi bộ được đánh số từ 1 tới n). Nếu có nhiều tập gồm m chi bộ cùng cho quyền kiểm soát toàn bộ, in tập nào cũng được.

Ràng buộc

  • 1≤n≤75.
  • Ký tự thứ i của dòng thứ i bằng 0; với i≠j đúng một trong hai ký tự (thứ i của dòng j, thứ j của dòng i) bằng 1.

Ví dụ

Input Output Giải thích
2
00
10
3
010
001
100
5
01000
00011
11001
10100
10010
Case 1: 1 2
Case 2: 2 1 2
Case 3: 2 2 3
Bộ 1: chi bộ 2 kiểm soát chi bộ 1, nên chỉ cần thâm nhập chi bộ 2. Bộ 2: 1 kiểm soát 2, 2 kiểm soát 3, 3 kiểm soát 1 (một vòng); mỗi chi bộ chỉ cho quyền với chính nó và một chi bộ khác, nên cần 2 chi bộ, chẳng hạn {1,2}. Bộ 3: không chi bộ nào kiểm soát được cả 4 chi bộ còn lại; chi bộ 2 kiểm soát 4,5 và chi bộ 3 kiểm soát 1,2,5, nên {2,3} cho quyền với cả 5 chi bộ.
4
0000
1001
1100
1010
Case 1: 2 2 3 Chi bộ 2 kiểm soát 1,4; chi bộ 3 kiểm soát 1,2; chi bộ 4 kiểm soát 1,3. Không chi bộ nào một mình đủ, còn {2,3} thì đủ. Tập {3,4} cũng là một đáp án đúng.

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.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0