시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
8 초 (추가 시간 없음) | 512 MB | 1 | 1 | 1 | 100.000% |
Rikka found a futuristic coat covering her body when waking up.
"It's cold at a high place like here."
It is the sound from the bankrupt boy standing there.
"Don't show that face... 'Bankrupt' doesn't mean that for me. I do have run out of my money, but I still have a job... And nobody can pull me out of my chair in the net bar for debts. "
Rikka knows that he has managed to smile to her. She is too weak, inexperienced and naive to say anything, but at least she could do something... The clashing coins remind her.
"Do you know 'Coin Fighting'? It used to be popular on the earth..."
"I'm a lunar native."
"Sorry... But I thought it may be... Good for you now..." Rikka's voice is reducing. Maybe her words hurt the boy who must be extremely sensitive to "coins" now.
"What's its rule?"
...
"Thank you, earthling." He reached his hand out and little lovely Rikka caught it, with thanks to and for both young juveniles. "We will meet again at the crossing of our fate."
"Jyaou Shingan Wa Saikou Desu!"
There are $m$ coin stacks. Each of them has $n$ coins initially, but their capacities are unlimited. They are lined up, forming an $n \times m$ grid as columns. Let $(i, j)$ be the $i$-th position from bottom to top in the $j$-th stack from left to right. A position $(x, y)$ is less than $(x', y')$ if and only if $x < x'$ or $(x = x', y < y')$.
There are two categories of coins: ordinary ones and special ones. Ordinary coins are divided into $6$ types by their denominations: $\{1, 5, 10, 50, 100, 500\}$; special coins are divided into two types: $\{X, Y\}$. Hence there are $8$ types of coins in total.
Each ordinary coin is either inactive or active, while special coins are always inactive even if they should be activated.
Ordinary coins can be merged into a higher level or removed by some rules. Each denomination has a basic merging threshold, of $\{5, 2, 5, 2, 5, 2\}$ respectively. If a four-connected component (explained in the section "Notes", the same below) of the same denomination contains at least one active coin, and its size is not less than the corresponding threshold, then it is removable.
While removing a removable component, one can get a score increment of its size. Besides, if the same denomination of the removed coins is less than $500$, one additional active coin of the denomination one level higher will be generated and placed at the least position among the places of the removed coins. Nothing will be placed when the same denomination of the removing coins is $500$. Notice that no matter how many coins are removed, no more than one coin will be placed.
A game is made up of some rounds. Each round is described in order as follows:
As mentioned above, a valid operation is determined by $(t, x)$, the type and the stack chosen, respectively. A valid operation must gain at least a score incerment of $1$. If there is no valid operation for a round, then the game ends.
In each round, the boy chooses a best operation among all valid ones. For two different valid operations $o_1 = (t_1, x_1), o_2 = (t_2, x_2)$, he compares them as follows:
Could you please play a referee for them?
Given the initial stacks, please implement the boy's operations. You need to calculate the total number of rounds. And for each round, the type and the stack chosen are wondered, and so is the score he gets.
The first line contains two integers $n, m (1\le n\le 2000, 1\le m\le 20)$, the initial number of coins in each stack and the number of stacks, respectively.
Each of the following $n$ lines contains a string consisting of $\{A, B, C, D, E, F, X, Y\}$, where characters $\{A, B, C, D, E, F\}$ refers to denominations $\{1, 5, 10, 50, 100, 500\}$ respectively, and the $j$-th character in the $i$-th line describes the type of the coin at $(i, j)$. Notice that the character matrix is upside down for input.
It is guaranteed that there are at most $20$ special coins (i.e. the coins of types $X$ and $Y$).
Output a single integer $K$ at the first line, the total number of rounds.
Each of the following $K$ lines contains a character and two integers. The character describes the type (in $\{A, B, C, D, E, F, X, Y\}$, as the input) which he chooses in that round, and the integers are the index of the chosen stack and the score increment in that round, respectively.
6 3 EEF EED ACC AAC AAC AAC
3 A 1 12 D 2 7 F 2 2
6 3 EEF EED ABC AAC AAC XAX
2 X 3 22 F 2 2
6 3 EEF EED ACC AAC AAC YAY
1 Y 3 12
7 2 EE FF FA AD DC EE YY
2 Y 1 9 D 1 2
Two positions $(x_1, y_1), (x_2, y_2)$ are four-adjacent if and only if $\lvert x_1 - x_2 \rvert + \lvert y_1 - y_2 \rvert = 1$.
Two positions $a, b$ are four-connected if and only if there exists a sequence of positions $a, c, \dots, b$ beginning with $a$ and ending with $b$ such that every two adjacent positions in the sequence are four-adjacent.
A set of coins $S$ is four-connected if and only if positions of every two coins in it are four-connected.
A four-connected component is a four-connected set of coins such that there doesn't exist a four-connected proper superset of it.
A position $(x_1, y_1)$ is over $(x_2, y_2)$ if and only if $x_1 = x_2 + 1, y_1 = y_2$.
In step 2, when you pick a coin, it is moved out from the stacks and put into a buffer.