P5267 [NOI2014] Elimination Game

Recently, Little Z became addicted to a new elimination game. The game is played on an $n \times m$ grid. Initially, each cell contains an integer from $0 \sim 9$. After eliminations, blank cells may appear in the grid, denoted by $-1$. For convenience, denote the number in row $i$, column $j$ as $A_{i,j}$, and its coordinate as $(i,j)$. Given three parameters $l_{\min}, l_{\max}$, and $K$, the player can perform at most $K$ operations. In each operation, the player needs to find a path of length $l$ in the grid. Formally, the path is represented by two sequences of length $l$, $x_1, x_2, \ldots, x_l$ and $y_1, y_2, \ldots, y_l$, satisfying: 1. $1 \le x_i \le n, 1 \le y_i \le m$ for $1 \le i \le l$, i.e., $(x_i,y_i)$ is a valid position in the grid. 2. $\left|x_i-x_{i+1} \right|+ \left|y_i-y_{i+1} \right|=1$ for $1 \le i \lt l$, i.e., $(x_i,y_i)$ and $(x_{i+1},y_{i+1})$ are adjacent cells in the grid. 3. $x_i \neq x_j$ or $y_i \neq y_j$ for $1 \le i \lt j \le l$, i.e., the path cannot pass through any cell more than once. 4. $A_{x_i,y_i} \neq -1$ for $1 \le i \le l$, i.e., the path cannot pass through blank cells. 5. $A_{x_1,y_1} \neq 0$, i.e., the path cannot start with the digit $0$. 6. $l_{\min} \le l \le l_{\max}$, i.e., the path length must be within the given range. Concatenate the digits along the path into an integer $N$, formally: $$ N=\sum\limits_{i=1}^l A_{x_i,y_i}\times 10^{l-i} $$ The game provides two parameters $c_1, c_2$ to compute the score for this operation: 1. If $N$ is a prime number, you get the **prime score** $l^{c_1}$; otherwise, the **prime score** is $1$. 2. If $N$ is a palindrome (i.e., viewing the decimal representation of $N$ as a string, its reverse is exactly the same as itself), you get the **palindrome score** $l^{c_2}$; otherwise, the **palindrome score** is $1$. 3. If both the **prime score** and the **palindrome score** are $1$, then the **score of this operation** is $0$. Otherwise, the **score of this operation** is the sum of the **prime score** and the **palindrome score**. After each operation, if the **score of this operation** equals $0$, then you waste one operation and the grid does not change. If the **score of this operation** is greater than $0$, then the numbers on the path are replaced with blanks, and the numbers above blanks fall vertically. Formally, perform the following steps: 1. Set $A_{x_i,y_i}\leftarrow -1$ for $1\le i\le l$. 2. Enumerate all cells. If there exists a cell $(i, j)$ such that $i \neq n$, $A_{i,j} \neq -1$, and $A_{i+1,j} = -1$, then perform $A_{i+1,j} \leftarrow A_{i,j}, A_{i,j}\leftarrow -1$. Repeat this operation until no such cell exists in the grid. We also provide a parameter $F$. After all operations are completed, the player’s **final score** $S$ is determined by $F$: if $F=0$, then the final score is the sum of the scores of all operations $m$; if $F=1$, then the final score is the sum of the scores of all operations $m$ divided by $2^d$ and floored, i.e., $$ S = \begin{cases} m, & F=0\\\\ \left \lfloor \frac{m}{2^d} \right \rfloor, & F=1 \end{cases} $$ where $d$ is the number of non-blank cells in the final grid. Little Z is so obsessed with this interesting game that she cannot stop. She wants to ask you for help: for the given input parameters, provide an operation plan for the game state. Of course, the higher the final score, the better.

**This is an output-only problem.** For each input file, line $1$ contains $8$ space-separated integers $n, m, K, l_{\min}, l_{\max}, c_1, c_2, F$, with the same meanings as in the statement. Then follow $n$ lines, each containing $m$ integers, describing the grid $A$. Numbers are separated by one space. The input file will not contain extra blank lines, and there will be no extra spaces at the end of lines.

For the given $10$ input files `game1.in ~ game10.in`, you need to submit your output files `game1.out ~ game10.out` respectively. The first line of the output file is an integer $M \ (0 \leq M \leq K)$, the number of operations you perform. Then the output file should contain $M$ lines, each describing one operation. For each line, the first integer $l$ indicates the length of the chosen path for this operation. Then follow $2l$ numbers: $x_1, y_1, x_2, y_2, \dots, x_l, y_l$. The output file should not contain extra spaces or blank lines. Multiple integers on the same line should be separated by one space.

#### Sample Explanation 1 The numbers eliminated in the $4$ eliminations and their corresponding scores are: $37$, score $2+1=3$; $41$, score $2+1=3$; $22$, score $1+2=3$; $131$, score $3+3=6$. The total score is $15$. There may be a better plan. #### Sample Explanation 2 This plan contains only one elimination operation. The eliminated number is $11$, and the score for this operation is $2+2=4$. Since $F=1$, the final score is the sum of operation scores $4$ divided by $2^1 = 2$ and floored, which is $2$. If you choose the elimination path $211$, you will get the best possible score for this game state, which is $4$. #### Scoring For each test, we set $9$ scoring parameters $a_{10},a_9, \dots ,a_2$. If your output is invalid, you get $0$ points. Otherwise, if the game score in your solution is $w_{user}$, your score will be given by the table below: ::cute-table{tuack=2} | Score | Condition | Score | Condition | | :--: | :------------------------------: | :--: | :--------------------------: | | $10$ | $w_{user}\ge a_{10}$ | $5$ | $a_5\le w_{user}\lt a_6$ | | $9$ | $a_9\le w_{user}\lt a_{10}$ | $4$ | $a_4\le w_{user}\lt a_5$ | | $8$ | $a_8\le w_{user}\lt a_9$ | $3$ | $a_3\le w_{user}\lt a_4$ | | $7$ | $a_7\le w_{user}\lt a_8$ | $2$ | $a_2\le w_{user}\lt a_3$ | | $6$ | $a_6\le w_{user}\lt a_7$ | $1$ | $0\lt w_{user}\lt a_2$ | #### Additional Files The checker must be compiled and used by yourself. Please go to [Github](https://github.com/MikeMirzayanov/testlib) to download the latest source code of testlib.h. Translated by ChatGPT 5