printРабочее место участника

printЗадачи

1886. Addictive Bubbles

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Alice is a mobile game developer. She writes a new port of the Chain Shot! game (also known as SameGame, Jawbreaker, Bubble Shot, etc) called Addictive Bubbles.
The game is played on a rectangular board filled with color bubbles. On each turn player selects a group of adjacent bubbles of the same color. Selected bubbles are removed from the board. Bubbles that are no longer supported fall down. If there are empty columns, they are removed.

24388.png

The number of points scored by the move is a square of the number of bubbles in the selected group. For the sample turn shown on the figure, 49 points are scored.
Turns are repeated until the board is empty. The total number of points is the sum of points scored on each turn.
The blueprint of the level consists of board dimensions and the number of bubbles of each color.
Your task is to help Alice write a bonus level generator. Given the blueprint, generator must produce a level that allows a skillful player to score the maximum possible number of points compared to all levels with the same blueprint.
Input
The input file contains the blueprint.
The first line of the input file contains three positive integers `h`, `w` and `c` — number of rows and columns of the board, and the number of colors (`1\ ≤\ h,w\ ≤\ 10`; `1\ ≤\ c\ ≤\ 9`).
The second line of the input file contains `c` positive integer numbers — the number of bubbles of each color. The total number of bubbles is `h\ *\ w`.
Output
Output the designed level — a `h\ times\ w` matrix of characters. The bubbles of the first color must be denoted by '1', the second color — by '2', etc.

Sample Input

3 5 3
4 4 7

Sample Output

31233
12211
33233
A sequence of turns, yielding the maximum possible number of points — 81:

24389.png

Source: ACM ICPC NEERC, 2012
loading