BSSPC '21 J3 - Magic Paint Gun Cartridges - Olympiads Online Judge

BSSPC '21 J3 - Magic Paint Gun Cartridges

Points: 5

Time limit: 2.0s

Memory limit: 256M

Author:

Problem types

Minestro is recreating images on the Internet with his magic paint gun when he unexpectedly runs out of cartridges!

Minestro has access to a supply of cartridges in the three primary colors - red, blue and yellow. Each image is represented by a grid of $N$ $N$ rows and $M$ $M$ columns of cells that are all initially empty, with no paint of any color in any cell.

Minestro can consume a single paint cartridge with his gun to add paint of the color of the cartridge to a contiguous sequence of adjacent cells in a single row. It is possible for up to three cartridges to paint their color on the same cell, in which case the resulting color is a mixture of all colors applied, according to the following table:

Color	Symbol	Primary Colors to Mix
White	`.`	None
Red	`R`	Red
Blue	`U`	Blue
Yellow	`Y`	Yellow
Orange	`O`	Red and yellow
Green	`G`	Blue and yellow
Purple	`P`	Red and blue
Brown	`B`	Red, blue, and yellow

Minestro still has one image to paint, so he needs you to tell him the minimum number of red, yellow, and blue paint cartridges he needs to buy — paint cartridges are expensive!

Note: Some Python 2/3 solutions may require PyPy to pass.

Constraints

$1 \le M, N \le 1\,000$ $1 \leq M, N \leq 1 000$

Input Specification

The first line will contain two integers $M$ $M$ and $N$ $N$ , the number of columns and rows of cells in the image, respectively.

The next $N$ $N$ lines will each contain $M$ $M$ characters, each of which is one of the eight characters ., R, O, Y, G, U, P, or B. The $v^{th}$ $v^{t h}$ character on the $i^{th}$ $i^{t h}$ line represents the required color of the $v^{th}$ $v^{t h}$ cell on the $i^{th}$ $i^{t h}$ row.

Output Specification

Output the minimum number of red, yellow, and blue paint cartridges Minestro needs to buy to paint the picture, separated by spaces.

Sample Input 1

Copy

6 4
..RR.P
..OORO
BBB.UU
ROBB..

Sample Output 1

Copy

5 4 4

Explanation for Sample Output 1

Minestro needs $5$ $5$ red cartridges: $2$ $2$ for the first row and $1$ $1$ in every other row. He needs $4$ $4$ yellow cartridges: $2$ $2$ in the second row and $1$ $1$ each in the last two rows. $4$ $4$ blue cartridges are used: $1$ $1$ in the first row, $2$ $2$ in the third, and $1$ $1$ in the last.

Sample Input 2

Copy

18 9
.B................
..YY...........YYY
...YYY.....YYYY...
..YYYYYYYYYYYYY...
.YYBBYYYYYBBYYY...
.RRYYYYBYYYYRRY...
.RRYYYOOOYYYRRY...
..YYYYOOOYYYYYY...
.YYYYYYYYYYYYYY...

Sample Output 2

Copy

10 13 4

Explanation for Sample Output 2

Minestro needs:

$10$ $10$ red cartridges: $1$ $1$ in the first row, $2$ $2$ in the fifth, $3$ $3$ in the sixth, $3$ $3$ in the seventh, and $1$ $1$ in the eighth row.
$13$ $13$ yellow cartridges: $1$ $1$ in the first row, $2$ $2$ in the second and third each, $1$ $1$ in the fourth and fifth each, $2$ $2$ in the sixth and seventh each, and $1$ $1$ cartridge each for the last two rows.
$4$ $4$ blue cartridges: $1$ $1$ in the first row, $2$ $2$ in the fifth, and $1$ $1$ in the sixth row.

Comments

0

QiQi commented on Nov. 14, 2021, 8:51 p.m. ← edit 2 →

Deleted statement

1

Nils_Emmenegger commented on Nov. 14, 2021, 9:29 p.m.

You may find it useful to reread the statement. In particular:

Minestro can consume a single paint cartridge with his gun to add paint of the color of the cartridge to a contiguous sequence of adjacent cells in a single row.

Happy coding!