Legend of Catan
栋栋 has recently become obsessed with a game called Catan. The game takes place on a map where resources are generated at each time step. The player's main goal is to acquire resources and build settlements. 栋栋 is currently studying strategies for the game and hopes to start with some simple scenarios. To this end, he has simplified the game and provided some game scenarios, hoping you can help him find excellent solutions for these scenarios.
The simplified game takes place on a map composed of an $n \times m$ grid, as shown in the figure below.
For convenience, we use $[r, c]$ to denote the cell in the $r$-th row ($1 \le r \le n$) and $c$-th column ($1 \le c \le m$) of the grid above. The top-left coordinate of $[r, c]$ is denoted as $(r-1, c-1)$, and the bottom-right coordinate is denoted as $(r, c)$ (please note the difference between parentheses and square brackets). Each cell $[r, c]$ has a resource type $S[r, c]$ and a point value $D[r, c]$. The resource type $S[r, c]$ can only be one of $1, 2, 3, 4$, while the point value $D[r, c]$ can be any non-negative integer.
Players can acquire resources generated by the cells by building settlements. There are two types of settlements: settlements and cities, both of which can only be built on the vertices of the grid. The amounts of the four types of resources required to build a settlement are $h_1, h_2, h_3, h_4$, respectively. A settlement can be upgraded to a city, and the amounts of the four types of resources required for the upgrade are $l_1, l_2, l_3, l_4$, respectively. If a city is built directly, the amounts of the four types of resources required are $h_1+l_1, h_2+l_2, h_3+l_3, h_4+l_4$. When building a settlement, the straight-line distance between any two settlements must be strictly greater than 1, and except for the first one, the building location must be connected to an existing road.
Roads also need to be built by the player; each road is an edge of a grid cell. The amounts of the four types of resources required to build a road are $a_1, a_2, a_3, a_4$, and it must share a common point with an existing road or settlement. Roads can be built repeatedly; the resources spent when building a road repeatedly are still $a_1, a_2, a_3, a_4$ (repeatedly building roads is generally meaningless, but the rules allow it).
At each time step $t$, the game generates a value $V_t$. Every cell with a point value $D[r, c] = V_t$ will produce a resource of type $S[r, c]$. The settlements at the four corners of such a cell (if any) will receive the corresponding resources: each settlement receives 1 unit of resource $S[r, c]$, and each city receives 2 units of resource $S[r, c]$. These resources are collected by the player. For example, if there is one settlement and one city at the four corners of a cell with resource type 4, then at time $t$, if the point value of this cell equals $V_t$, the player will receive 3 units of resource 4 from this cell. At the same time, a settlement may receive resources from multiple cells.
At the start of the game, the player has $h_1, h_2, h_3, h_4$ units of the four resources. Using these resources, the player can build a settlement at any location.
At any time, the player can exchange $K$ identical resources for 1 unit of another type of resource, where $K$ is a value defined by the game rules. For example, they can use $K$ units of resource 3 to exchange for 1 unit of resource 4.
Now, 栋栋 has told you the map and the value $V_t$ generated by the game at each time step. You need to find a solution in the shortest possible time such that $2 \times (\text{number of cities}) + (\text{number of settlements}) \ge 10$.
Input
This is a submission-based problem. There are 10 input files in your directory, catan1.in ~ catan10.in.
The first line of the input contains two integers $n, m$, representing the number of rows and columns of the grid, respectively.
The next $n$ lines represent the resource types of all cells, where the $r$-th line contains $m$ integers, and the $c$-th integer in the $r$-th line represents $S[r, c]$.
The next $n$ lines represent the point values of all cells, where the $r$-th line contains $m$ integers, and the $c$-th integer in the $r$-th line represents $D[r, c]$.
The next line contains 4 integers $h_1, h_2, h_3, h_4$, representing the 4 resource amounts required to build a settlement.
The next line contains 4 integers $l_1, l_2, l_3, l_4$, representing the 4 resource amounts required to upgrade a settlement to a city.
The next line contains 4 integers $a_1, a_2, a_3, a_4$, representing the 4 resource amounts required to build a road.
The next line contains 1 integer $K$, representing that the player can use $K$ identical resources to exchange for 1 unit of another resource.
The next line contains 1 integer $G$, representing the given duration.
The last line contains $G$ integers $V_1, V_2, \dots, V_G$, representing the value generated by the game at each time step.
Output
For each input file, provide the corresponding output file catan*.out in the directory.
The first line of the output contains an integer $ans$, representing the time duration required to build enough settlements (i.e., $2 \times (\text{number of cities}) + (\text{number of settlements}) \ge 10$).
The next two lines represent the player's initial strategy. The first line contains a capital letter B and two integers $x_0, y_0$, representing building a settlement at position $(x_0, y_0)$ at the beginning. The second line contains a capital letter E.
The next $ans$ parts represent the player's strategy during the game.
Each $i$-th part contains several lines, representing the player's actions after the resources are generated at time $i$.
- If a line contains a capital letter B and two integers $x, y$, it means building a settlement at position $(x, y)$.
- If a line contains a capital letter C and two integers $x, y$, it means building a city at position $(x, y)$.
- If a line contains a capital letter U and two integers $x, y$, it means upgrading the settlement at position $(x, y)$ to a city.
- If a line contains a capital letter R and four integers $x_1, y_1, x_2, y_2$, it means building a road between positions $(x_1, y_1)$ and $(x_2, y_2)$. The distance between $(x_1, y_1)$ and $(x_2, y_2)$ must be 1.
- If a line contains a capital letter X and two integers $p, q$, it means exchanging $K$ units of resource $p$ for 1 unit of resource $q$.
- If a line contains a capital letter E, it means the end of this part.
Note: The size of your output file cannot exceed 1MB.
Subtasks
For each test case, if you do not output, the output is invalid, or you cannot build enough settlements within the given time $G$, you will receive 0 points.
Otherwise, for each data set, we have 9 scoring parameters $m_2, \dots, m_{10}$.
- If $ans \le m_{10}$, 10 points;
- If $m_{i+1} < ans \le m_i$, $i$ points;
- If $ans > m_2$, 1 point.
Interaction
In your directory, there is a program checker that can be used to test your output results. You can use the following command in the terminal to check your output:
./checker N
where $N$ is the test case number. For example, to test the 3rd test case, you can use:
./checker 3
This program will check whether your output is valid. For valid output, checker will output "Right.", otherwise it will output error information.
Examples
Input 1
1 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 100 10 1 1 1 1 1 1 1 1 1 1
Output 1
6 B 0 0 E U 0 0 E R 0 0 0 1 R 0 1 0 2 E B 0 2 U 0 2 E R 0 2 0 3 R 0 3 0 4 B 0 4 U 0 4 E R 0 4 0 5 R 0 5 0 6 B 0 6 U 0 6 R 0 6 0 7 R 0 7 0 8 E B 0 8 U 0 8 E
Note
The above is one possible solution, requiring a total time of 6. Please note that this answer is not necessarily optimal, and there may be better solutions.