P5209 [ZJOI2017] Tower of Hanoi

Although Jiutiao often sets problems, she found that setting an entire contest by herself was really too hard, so she dropped the work at hand and started playing some mini-games.

There is a modified version of the Tower of Hanoi. In this game, disks are allowed to have the same size, but it is guaranteed that for each size there are exactly $K$ disks of that size. In the initial state, all disks are stacked on the first peg from bottom to top in non-increasing order of size (larger below, smaller above). For disks of the same size, we label them from $1$ to $K$ from bottom to top. The goal is to move all disks to the third peg. Since there is no requirement on the relative order of disks of the same size, it is easy to see that there are many legal terminal states. Therefore, the game specifies one particular terminal state. The task is to minimize the number of moves. Jiutiao thought this problem seemed quite difficult, so she put it into the contest for you to solve. The specific rules are as follows: - There are three pegs and several circular disks. In the initial state, all disks are on the first peg. - At any moment, you may move the top disk of one peg to the top of another peg, with the goal of moving all disks to the third peg. - During the process, you must ensure that a larger disk is never placed on top of a smaller disk. (There is no order restriction among disks of the same size.)

The first line contains an integer indicating the number of test cases. For each test case, the first line contains two integers $n$ and $K$. The next $n$ lines, in order from larger sizes to smaller sizes, give the relative order of the $K$ disks of that same size in the terminal state (from left to right represents bottom to top). For example, when $K = 2$, `2 1` means the disk that was originally on top goes to the bottom, and the disk that was originally on the bottom goes to the top.

For each test case, output one integer indicating the minimum number of moves.

| Test Point ID | K | Test Point ID | K | | :-----------: | :-----------: | :-----------: | :-----------: | | 1 | =1 | 6 | =3 | | 2 | =2 | 7 | =3 | | 3 | =2 | 8 | =4 | | 4 | =2 | 9 | =4 | | 5 | =3 | 10 | =4 | For $100\%$ of the data, it is guaranteed that $T \le 10^4$, $1 \le n \le 50$, $1 \le x_i \le K$. **In the actual test points, the values of $K$ are the same for all $T$ test cases.** $\textcolor{white}{SookeAKIOI}$ Translated by ChatGPT 5