Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1886. Addictive Bubbles
Задачи на построениеОлимпиадные задачи на английском языке
| 06/12/2012 | Занятие 13 (Задачи NEERC 2012) (A) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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.
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:
Source: ACM ICPC NEERC, 2012
