Hộp trang sức
Đề bài
Mô tả
Minh tìm thấy một chiếc hộp trang sức cổ bí ẩn. Trên mặt hộp có một câu đố, và có vẻ như giải được câu đố sẽ mở được hộp.
Câu đố gồm ổ khóa tròn và chốt. Các ổ khóa được đánh số từ đến và xếp thành lưới như sau:
- Hàng trên: , , .
- Hàng giữa: , , .
- Hàng dưới: , , .
Bốn chốt A, B, C, D nằm ở tâm của bốn ô vuông : chốt A ở giữa các ổ khóa ; chốt B ở giữa các ổ khóa ; chốt C ở giữa các ổ khóa ; chốt D ở giữa các ổ khóa .
Sau một hồi nghịch chiếc hộp, Minh nhận ra một số tính chất của nó:
- Mỗi ổ khóa có số từ đến .
- Chỉ có thể xoay ổ khóa ở góc là , , và , và chỉ xoay theo chiều kim đồng hồ.
- Khi xoay một ổ khóa đang có giá trị , giá trị mới của ổ khóa là .
- Có thể bật hoặc tắt các chốt bao nhiêu lần tùy ý.
- Khi một chốt được bật, ổ khóa xung quanh chốt đó sẽ xoay đồng bộ: nếu một ổ khóa xoay thì ổ còn lại cũng xoay theo cùng cách. Ví dụ:
- Nếu bật chốt A, xoay ổ khóa sẽ làm các ổ khóa xoay theo.
- Nếu bật chốt B, xoay ổ khóa sẽ làm các ổ khóa xoay theo.
- Nếu bật chốt A và B, tắt chốt C và D, xoay ổ khóa sẽ làm các ổ khóa xoay theo. Vì chốt B đang bật, việc ổ khóa và xoay lại làm các ổ khóa và xoay theo. Như vậy khi bật chốt A và B, xoay ổ khóa sẽ làm ổ khóa xoay.
- Nếu bật cả chốt A và D, tắt chốt B và C, các ổ khóa sẽ xoay đồng bộ.
- Nếu bật chốt A và tắt các chốt còn lại, xoay ổ khóa chỉ làm chính nó xoay.
Cho trạng thái hiện tại của các ổ khóa, hãy giúp Minh đưa tất cả các ổ khóa về giá trị . Lưu ý rằng bạn không cần tối thiểu số bước.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên .
- dòng tiếp theo, mỗi dòng chứa đúng số nguyên trong đoạn , biểu diễn trạng thái ban đầu của ổ khóa (theo thứ tự lưới ở trên).
Dữ liệu ra
Nếu không có cách nào, in ra một dòng chứa từ NO. Ngược lại, in ra YES ở dòng đầu tiên, tiếp theo là:
- Một dòng chứa số nguyên , số bước ().
- dòng tiếp theo, mỗi dòng chứa số nguyên , trong đó:
- là trạng thái của các chốt: là bật, là tắt.
- là ổ khóa được xoay.
- là số lần xoay.
Nếu có nhiều đáp án, bạn có thể in ra đáp án bất kỳ.
Ràng buộc
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 8 5 6 1 7 0 6 3 7 5 |
YES 10 1 1 1 1 9 2 0 0 1 1 9 6 1 1 1 1 9 1 0 1 0 1 9 7 1 1 1 1 9 2 1 0 1 0 7 6 1 1 1 1 9 1 1 1 0 0 3 7 0 0 0 0 3 3 0 0 0 0 7 3 |
Một đáp án khác (của đề gốc) gồm bước: bật chốt A và D, xoay ổ khóa lần (1 0 0 1 1 3); tắt hết chốt, xoay ổ khóa lần (0 0 0 0 7 7); bật chốt B, xoay ổ khóa lần (0 1 0 0 3 7); tắt chốt B, bật chốt C, xoay ổ khóa lần (0 0 1 0 7 6). |
| 8 0 0 0 0 0 0 0 0 0 |
YES 0 |
Ví dụ bổ sung (không có trong đề gốc). Các ổ khóa đã ở giá trị . |
Bình luận