trang chủ / đề bài / icpc21_nat_j

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 9 ổ khóa tròn và 4 chốt. Các ổ khóa được đánh số từ 1 đến 9 và xếp thành lưới 3×3 như sau:

  • Hàng trên: 1, 2, 3.
  • Hàng giữa: 4, 5, 6.
  • Hàng dưới: 7, 8, 9.

Bốn chốt A, B, C, D nằm ở tâm của bốn ô vuông 2×2: chốt A ở giữa các ổ khóa 1,2,4,5; chốt B ở giữa các ổ khóa 2,3,5,6; chốt C ở giữa các ổ khóa 4,5,7,8; chốt D ở giữa các ổ khóa 5,6,8,9.

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ó C số từ 0 đến C−1.
  • Chỉ có thể xoay 4 ổ khóa ở góc là 1, 3, 7 và 9, và chỉ xoay theo chiều kim đồng hồ.
  • Khi xoay một ổ khóa đang có giá trị x, giá trị mới của ổ khóa là (x+1)modC.
  • 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, 4 ổ khóa xung quanh chốt đó sẽ xoay đồng bộ: nếu một ổ khóa xoay thì 3 ổ còn lại cũng xoay theo cùng cách. Ví dụ:
    • Nếu bật chốt A, xoay ổ khóa 1 sẽ làm các ổ khóa 2,4,5 xoay theo.
    • Nếu bật chốt B, xoay ổ khóa 3 sẽ làm các ổ khóa 2,5,6 xoay theo.
    • Nếu bật chốt A và B, tắt chốt C và D, xoay ổ khóa 1 sẽ làm các ổ khóa 2,4,5 xoay theo. Vì chốt B đang bật, việc ổ khóa 2 và 5 xoay lại làm các ổ khóa 3 và 6 xoay theo. Như vậy khi bật chốt A và B, xoay ổ khóa 1 sẽ làm 6 ổ khóa xoay.
    • Nếu bật cả chốt A và D, tắt chốt B và C, các ổ khóa 1,2,4,5,6,8,9 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 9 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ị 0. 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 C.
  • 3 dòng tiếp theo, mỗi dòng chứa đúng 3 số nguyên trong đoạn [0,C−1], biểu diễn trạng thái ban đầu của 9 ổ 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 k, số bước (0≤k≤1000).
  • k dòng tiếp theo, mỗi dòng chứa 6 số nguyên pA,pB,pC,pD,c,rot, trong đó:
    • pA,pB,pC,pD∈{0,1} là trạng thái của các chốt: 1 là bật, 0 là tắt.
    • c∈{1,3,7,9} là ổ khóa được xoay.
    • 1≤rot≤100 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

  • 8≤C≤50.

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 4 bước: bật chốt A và D, xoay ổ khóa 1 3 lần (1 0 0 1 1 3); tắt hết chốt, xoay ổ khóa 7 7 lần (0 0 0 0 7 7); bật chốt B, xoay ổ khóa 3 7 lần (0 1 0 0 3 7); tắt chốt B, bật chốt C, xoay ổ khóa 7 6 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ị 0.

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