trang chủ / đề bài / icpc25_nat_j

Phá hoại công lý

Đề bài

Mô tả

The Shell là một nhà tù lớn, nơi các thành viên của Adwent từng bị giam giữ. Người ta nói rằng nó nằm ở đâu đó sâu dưới lòng đất của thế giới này, nhưng vị trí chính xác thì không ai biết.

Ở trung tâm của The Shell có n phòng giam. Mỗi phòng giam được trang bị một camera giám sát cần được theo dõi liên tục. Có n phòng giám sát, phòng giám sát thứ i được kết nối với camera của một tập con xác định các phòng giam. Các phòng giám sát và các phòng giam được đánh số từ 0 đến n−1.

Vì lý do an ninh, mỗi phòng giám sát chỉ có thể theo dõi đúng một trong các camera mà nó được kết nối. The Shell được coi là an toàn khi và chỉ khi tồn tại một cách gán cho mỗi phòng giám sát một camera sao cho mọi camera đều được theo dõi. Đảm bảo rằng ban đầu The Shell an toàn.

Sau khi trốn thoát khỏi The Shell, các thành viên của Adwent lên kế hoạch phá hoại hệ thống an ninh của nó. Tuy nhiên, do nguồn lực có hạn, họ chỉ có thể thực hiện tối đa 50 hành động phá hoại. Trong mỗi hành động, họ chọn một phòng giám sát i và một phòng giam j sao cho phòng giám sát i hiện đang được kết nối với camera của phòng giam j, rồi xóa kết nối đó.

Thủ lĩnh của Adwent muốn biết liệu có thể thực hiện một dãy gồm tối đa 50 hành động phá hoại để The Shell không còn an toàn hay không. Nếu có thể, bạn cần in ra một dãy hành động hợp lệ.

Dữ liệu vào

Mỗi test gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu τ (1≤τ≤50). Tiếp theo là mô tả các bộ dữ liệu.

  • Dòng đầu tiên chứa số nguyên n (1≤n≤50): số phòng giám sát và số phòng giam.
  • Dòng thứ i trong n dòng tiếp theo chứa n số nguyên ai,0,ai,1,…,ai,n−1 (0≤ai,j≤1). ai,j=1 nghĩa là phòng giám sát thứ i được kết nối với camera của phòng giam thứ j; ngược lại ai,j=0.

Đảm bảo rằng The Shell an toàn ở cấu hình ban đầu.

Dữ liệu ra

Với mỗi bộ dữ liệu, nếu không thể làm The Shell mất an toàn bằng tối đa 50 hành động phá hoại, in ra một số nguyên −1. Ngược lại, in ra:

  • Dòng đầu tiên chứa số nguyên m (0≤m≤50): số hành động phá hoại.
  • Dòng thứ i trong m dòng tiếp theo chứa hai số nguyên ri và ci (0≤ri,ci<n): chỉ số phòng giám sát và phòng giam được chọn ở hành động thứ i. Kết nối giữa phòng giám sát và camera của phòng giam được chọn phải tồn tại trước khi thực hiện hành động.

Nếu có nhiều đáp án, bạn có thể in ra bất kỳ đáp án nào. Số hành động không cần nhỏ nhất.

Ràng buộc

  • 1≤τ≤50.
  • 1≤n≤50, ai,j∈{0,1}.
  • Ban đầu tồn tại cách gán mỗi phòng giám sát một camera sao cho mọi camera đều được theo dõi.

Ví dụ

Input Output Giải thích
2
3
1 1 0
0 1 1
1 0 1
2
1 1
1 1
2
0 0
1 2
4
0 0
0 1
1 0
1 1
Bộ 1: ban đầu phòng 0 nối với camera 0, 1; phòng 1 nối với camera 1, 2; phòng 2 nối với camera 0, 2. Sau khi xóa kết nối (0, 0) và (1, 2), phòng 0 và phòng 1 đều chỉ còn nối với camera 1, nên không có cách gán nào để mọi camera được theo dõi. Bộ 2: số hành động không cần nhỏ nhất.
3
1
1
2
1 0
0 1
3
1 1 1
1 1 1
1 1 1
1
0 0
1
0 0
3
0 0
0 1
0 2
Ví dụ bổ sung (không có trong đề gốc). Trong mỗi bộ, xóa mọi kết nối của phòng giám sát 0, khi đó phòng này không thể theo dõi camera nào.

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