trang chủ / đề bài / icpc26_mn_f

Câu đố tủ khóa I

Đề bài

Mô tả

Một căn phòng có n chiếc tủ khóa, được đánh số từ 1 đến n. Mỗi tủ đang ở trạng thái mở hoặc đóng. Một nhóm gồm n người thừa kế phải giải một câu đố với các tủ này trước khi được nhận tài sản thừa kế.

Những người thừa kế cũng được đánh số từ 1 đến n. Ở mỗi bước, bạn được chọn một người thừa kế để thực hiện một thao tác. Khi người thừa kế thứ i được chọn, người đó đảo trạng thái của mọi tủ có chỉ số là bội của i. Cụ thể hơn, với mọi số nguyên dương j sao cho i×j≤n, trạng thái của tủ thứ (i×j) được đổi từ mở thành đóng hoặc ngược lại. Một người thừa kế có thể được chọn nhiều lần.

Câu đố được giải khi cả n tủ đều đóng.

Hãy tìm một dãy thao tác đóng được tất cả các tủ, hoặc cho biết không tồn tại dãy như vậy.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên t (1≤t≤100): số bộ dữ liệu.

Mỗi bộ dữ liệu gồm:

  • Dòng đầu tiên chứa một số nguyên n (1≤n≤100): số tủ khóa.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (0≤ai≤1): trạng thái ban đầu của các tủ, trong đó ai=1 nghĩa là tủ thứ i đang mở và ai=0 nghĩa là tủ đó đang đóng.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra câu trả lời như sau:

  • Nếu không tồn tại dãy thao tác hợp lệ, in ra một số nguyên −1.
  • Ngược lại, in ra trên dòng đầu tiên một số nguyên k (0≤k≤n2): số thao tác trong dãy của bạn.
  • Nếu k>0, in ra trên dòng thứ hai k số nguyên b1,b2,…,bk (1≤bi≤n), trong đó bi là người thừa kế được chọn ở thao tác thứ i.

Nếu có nhiều dãy thao tác hợp lệ, bạn có thể in ra dãy bất kỳ.

Ràng buộc

  • 1≤t≤100.
  • 1≤n≤100.
  • 0≤ai≤1.
  • 0≤k≤n2, 1≤bi≤n.

Ví dụ

Input Output Giải thích
8
3
0 0 0
3
0 0 1
3
0 1 0
3
0 1 1
3
1 0 0
3
1 0 1
3
1 1 0
3
1 1 1
0
1
3
1
2
2
2 3
3
1 2 3
2
1 2
2
1 3
1
1
Ở bộ dữ liệu thứ nhất mọi tủ đã đóng nên không cần thao tác nào. Ở bộ dữ liệu thứ năm, chọn lần lượt người thừa kế 1, 2, 3 làm trạng thái các tủ thay đổi như sau: (1,0,0)→(0,1,1)→(0,0,1)→(0,0,0), nên dãy trong đầu ra đóng được mọi tủ.
3
7
1 0 0 0 0 1 1
11
1 1 1 1 1 1 0 1 0 1 0
15
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
4
1 2 3 5
4
1 7 9 11
1
1
Ở bộ dữ liệu thứ ba mọi tủ đều mở, người thừa kế 1 đảo tất cả các tủ nên một thao tác 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.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