[NOI2012] 三重镇

ID: 6324

远端评测题

1000ms

125MiB

尝试: 0

已通过: 0

难度: 9

上传者:

Hydro

标签>

2012

NOI

提交答案

Special Judge

Background

Student Xiao Xi recently became interested in the iOS game Triple Town. After playing, Xiao Xi also started thinking about how to get a higher score in this game.

Problem Description

As shown in the figure below, the game is played on an $n \times m$ grid map. The game provides a building sequence. The player chooses an empty cell each time and places the corresponding building unit in order. Buildings have nine different levels. From low to high they are Grass, Bush, Tree, Hut, etc. (for convenience, we call them $L_1, L_2, L_3, \ldots , L_9$ ).

After the player builds a unit on an empty cell, it may trigger a reaction. A reaction happens if: starting from this cell, the size of the connected component formed by cells with the same building level as this unit is at least $3$ . Then this connected component will be merged into one building of the next level. The new building is placed at the position of the last built unit, and all other cells in the component become empty. Here, a connected component means a set of positions that are directly or indirectly adjacent.

Also note that $L_9$ is the highest level, so connected components of multiple $L_9$ will not merge. For example, in the figure below, after building the middle $L_1$ , the $L_1$ connected to it are merged into one $L_2$ .

Note that during merging, chain reactions may occur, as shown below.

The game score depends on the units the player builds and the units generated by reactions. Whenever a building unit is placed or generated by a reaction, the corresponding score is added. The score table for different building levels is as follows:

Building	$L_1$	$L_2$	$L_3$	$L_4$	$L_5$	$L_6$	$L_7$	$L_8$	$L_9$
Score	$4$	$20$	$100$	$500$	$1500$	$5000$	$20000$	$100000$	$500000$

Using the two game processes above as examples: in Figure 2, first an $L_1$ is built, gaining $4$ points. Then the $L_1$ reacts and generates an $L_2$ , gaining another $20$ points. The total is $24$ . In Figure 3, this move scores $4+20+100+500=624$ points.

To reduce the difficulty, the game also provides two items: “star” and “bomb”. At the start of the game, the player is given $p$ stars and $q$ bombs, and can use them at any time. Their functions are:

“Star” item: It can be placed on an empty cell. When a star is placed, it automatically becomes the highest-level building that can trigger a reaction. If no reaction can be triggered at that position, the star becomes $L_1$ . For example, placing a star at the very center in Figure 3, the star automatically becomes $L_3$ . The score of the star is calculated according to the building level it becomes.
“Bomb” item: A bomb can be placed on a cell that already has a building. It destroys the building and turns that cell back into empty. When using a bomb, half of the destroyed building’s score is deducted (i.e. the score added is negative).

During the game, the player must place buildings in the given order, but may interleave the use of the two items at any time. The goal is to achieve the highest possible score through proper operations.

Input Format

This is an output-only problem.

For each test, the first line of the input file contains two integers $n$ , $m$ , indicating that the map has $n$ rows and $m$ columns.

The next line contains two integers $p$ , $q$ , indicating the number of star items and bomb items.

The next $n$ lines contain the initial $n \times m$ map. The character . means an empty cell, and digits $1\sim 9$ represent buildings of the corresponding levels.

The next line contains a number $k$ , indicating the length of the building sequence.

The last line contains $k$ space-separated integers between $1\sim 9$ , indicating the content of the building sequence.

Output Format

For the given $10$ input files tritown1.in ~ tritown10.in, you need to submit your output files tritown1.out ~ tritown10.out respectively.

Each output file contains the player’s game commands. There are $4$ types of commands:

Command	Meaning
`PUT x y`	Place the next unit in the building sequence into the empty cell at row $x$ , column $y$ .
`STAR x y`	Place a star item into the empty cell at row $x$ , column $y$ .
`BOMBER x y`	Place a bomb at row $x$ , column $y$ . This cell must be non-empty.
`END`	End the game and settle the current score.

The output must end with the END command. The player may end the game at any time.

PUT 1 2
PUT 1 1
STAR 2 1
END

Hint

Sample Explanation

This sample corresponds to the figure below:

The first move scores $4+20+100=124$ .

The second move scores $100$ .

The third move scores $100+500=600$ .

The total score is $124+100+600=824$ .

Scoring

For each test, we provide $9$ scoring parameters $a_{10}, a_9, \ldots, a_2$ , one per line in this order, in the additional files tritown1.ans ~ tritown10.ans. If your output is invalid, you get $0$ points. Otherwise, let your game score be $w_{user}$ . Your score is given by the table below:

Score	Condition	Score	Condition
10	$w_{user}\geq a_{10}$	5	$w_{user}\geq a_5$
9	$w_{user}\geq a_9$	4	$w_{user}\geq a_4$
8	$w_{user}\geq a_8$	3	$w_{user}\geq a_3$
7	$w_{user}\geq a_7$	2	$w_{user}\geq a_2$
6	$w_{user}\geq a_6$	1	$w_{user}>0$

If multiple conditions are satisfied, take the highest score among them.

Additional Files

The checker needs to be compiled before use.

Please go to Github to download the latest source code of testlib.h.

Translated by ChatGPT 5

#P5570. [NOI2012] 三重镇