Câu đố tủ khóa I
Đề bài
Mô tả
Một căn phòng có chiếc tủ khóa, được đánh số từ đến . Mỗi tủ đang ở trạng thái mở hoặc đóng. Một nhóm gồm 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ừ đế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ứ được chọn, người đó đảo trạng thái của mọi tủ có chỉ số là bội của . Cụ thể hơn, với mọi số nguyên dương sao cho , trạng thái của tủ thứ đượ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ả 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 (): 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 (): số tủ khóa.
- Dòng thứ hai chứa số nguyên (): trạng thái ban đầu của các tủ, trong đó nghĩa là tủ thứ đang mở và 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 .
- Ngược lại, in ra trên dòng đầu tiên một số nguyên (): số thao tác trong dãy của bạn.
- Nếu , in ra trên dòng thứ hai số nguyên (), trong đó là người thừa kế được chọn ở thao tác thứ .
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
- .
- .
- .
- , .
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ế , , làm trạng thái các tủ thay đổi như sau: , 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ế đảo tất cả các tủ nên một thao tác là đủ. |
Bình luận