Васе очень нравится игра «2048», но ему не хватает в ней гибкости. Он решил создать свою версию, где размер доски, возможные номиналы плиток и цель игры могут меняться. Ваша задача — написать движок-валидатор для этого турнира.
Игра происходит на квадратном поле размера \( X \times X \) (в данной задаче \( X = 5 \)).
- Слияние. При сдвиге в одном из четырёх направлений плитки с одинаковым номиналом объединяются, если они «налетают» друг на друга. Номинал новой плитки равен сумме двух предыдущих. Одна плитка не может участвовать в слиянии дважды за один ход. Порядок слияния соответствует классической игре 2048. К примеру, строка
22200 при сдвиге вправо превратится в 00024. Под нулём подразумеваются пустые клетки.
- Ход. Считается совершённым, если хотя бы одна плитка изменила своё положение или произошло слияние.
- Очерёдность. После каждого успешного хода на поле должна появиться новая плитка.
Формат входных данных
В первой строке содержится целое число \( n \) (\( 1 \le n \le 10 \)) — количество возможных номиналов новых плиток.
Во второй строке содержатся \( n \) целых различных чисел \( a_1, a_2, \ldots, a_n \) (\( 2 \le a_i \le 2^{10} \)) — доступные номиналы для новых плиток. Гарантируется, что \( a_i \) — степень двойки.
В третьей строке содержится целое число \( m \) (\( 2^{11} \le m \le 2^{20} \)) — минимальная стоимость плитки для победы.
В четвёртой строке содержится целое число \( q \) (\( 2 \le q \le 10^4 \)) — количество запросов.
Далее следуют \( q \) запросов. Каждый запрос начинается с типа операции \( T \). Номер запроса \( x \) считается с нуля.
Типы запросов:
- Тип 1. Вывести текущее состояние доски в виде матрицы \( X \times X \). Пустые клетки выводятся как 0.
- Тип 2 (Появление). На следующей строке даны \( x, y, b \): \( x, y \) — координаты (\( 0 \le x, y < X \)); \( b \) — номинал (\( 2 \le b \le 2^{10} \)).
- Тип 3 (Ход). На следующей строке дано число \( d \) — направление: 0 — вверх, 1 — вправо, 2 — вниз, 3 — влево.
Примечание. Гарантируется, что самым первым игровым запросом будет запрос типа 2. Проверка на поражение производится сразу после появления новой плитки.
Формат выходных данных
На каждый запрос первого типа нужно вывести 5 строк по 5 чисел через пробел — доску с плитками. Если плитка пустая, следует вывести 0.
Если происходит одно из следующих событий, программа должна вывести соответствующее сообщение, после чего завершить работу. Вместо \( x \) следует написать номер текущего хода, считая с нуля.
| Событие |
Сообщение |
| Победа: на поле появилась плитка номиналом не меньше \( m \) |
Player won. Step: x |
| Поражение: нет ни одного хода (тип 3), который сдвинет плитки |
Player lost. Step: x |
| Нарушение очереди: два появления или два хода подряд |
Incorrect step. Step: x |
| Неэффективный ход: ход (тип 3) не изменил состояние доски |
Incorrect step. Step: x |
| Некорректный спавн: клетка занята или номинал недопустим |
Incorrect step. Step: x |
Комментарий. После победы, поражения или некорректного хода оставшийся ввод следует игнорировать.
| № | Входные данные | Выходные данные |
|
1
|
1
2
2048
2
2
0 0 2
1
|
2 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
|
|
2
|
1
2
2048
6
2
0 0 2
3
1
2
0 3 2
3
1
2
0 0 2
1
|
2 0 0 0 4
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
|