P5507 Mechanism

After Steve landed successfully, he found a gate on Planet M, but the gate was locked.

There is a mechanism on the gate. It has a total of $12$ knobs, and each knob has $4$ states. The states of a knob are represented by the numbers $1$ to $4$. Each knob can only be rotated in one direction (states: $1\rightarrow2\rightarrow3\rightarrow4\rightarrow1$). When it is rotated, it will cause another knob to rotate once as well (in the same direction, and it will not cause a chain reaction). The same knob, when in different states, may cause different knobs to rotate (given in the input). When all knobs are rotated to state $1$, the mechanism opens. Because the knobs have not been maintained for a long time, rotating once is difficult, and time is tight. Therefore, Steve wants to open the mechanism using the minimum number of rotations. This task is left to you.

There are $12$ lines, each containing $5$ integers, describing the state of the mechanism. On line $i$, the first integer $s_i$ indicates that the initial state of the $i$-th knob is $s_i$. The next $4$ integers $a_{i,j}, j=1,2,3,4$ indicate that when this knob is in state $j$ and is rotated, it will cause the $a_{i,j}$-th knob to rotate to the next state.

The first line contains an integer $n$, indicating the minimum number of steps. The second line contains $n$ integers, indicating the indices of the knobs rotated in order. The testdata guarantees that a solution exists.

Samples $1$ and $2$ have the same input, and both outputs are accepted. Explanation for sample $4$: ``` 414334 241424 Rotate knob 11 to state 3, causing knob 3 to rotate to state 1. 411334 241434 Rotate knob 4 to state 4, causing knob 11 to rotate to state 4. 411434 241444 Rotate knob 6 to state 1, causing knob 11 to rotate to state 1. 411431 241414 Rotate knob 10 to state 1, causing knob 8 to rotate to state 1. 411431 211114 Rotate knob 7 to state 3, causing knob 9 to rotate to state 2. 411431 312114 Rotate knob 7 to state 4, causing knob 5 to rotate to state 4. 411441 412114 Rotate knob 5 to state 1, causing knob 12 to rotate to state 1. 411411 412111 Rotate knob 9 to state 3, causing knob 7 to rotate to state 1. 411411 113111 Rotate knob 9 to state 4, causing knob 4 to rotate to state 1. 411111 114111 Rotate knob 9 to state 1, causing knob 1 to rotate to state 1. 111111 111111 ``` The testdata guarantees that there is a way to open the mechanism. Each test point is worth $10$ points. As long as your output format is correct, you output the correct number of steps, and you provide any correct solution, you will get the score for that test point. Otherwise, you will get $0$ points for that test point. Constraints: Test point | Required steps :-: | :-: 1 | 4 2 | 6 3 | 8 4 | 9 5 | 10 6 | 11 7 | 12 8 | 13 9 | 15 10 | 17 Translated by ChatGPT 5