Задача D. 2048

Автор:М. Спорышев   Ограничение времени:5 сек
Ввод / вывод:интерактивный   Ограничение памяти:256 Мб
Максимальный балл:1  

Условие

Данная задача является интерактивной.

Задача состоит в прохождении игры 2048 с наилучшим результатом.

2048 играется на поле N × M клеток. Клетки, в которых записаны числа, сдвигаются по нажатию пользователем клавиш курсора.

После каждого хода в случайном пустом поле появляется число 2, либо 4. Клетки сдвигаются в заданном пользователем направлении, пока их не остановит либо другая непустая клетка, либо граница поля.

Если две клетки с одинаковыми числами сталкиваются друг с другом во время сдвига, они объединяются в одну клетку с числом равным их сумме.

Клетка не может быть объединена с другими более одного раза во время сдвига. Клетки сдвигаются и объединяются последовательно от первого к последнему в направлении движения.

Система оценивания

На каждом тесте участник получает количество баллов, равное степени двойки максимального из чисел на доске на момент конца игры.

Протокол взаимодействия

На первом шаге ваша программа должна считать два целых числа N, M — размеры поля.

Далее, на каждом шаге взаимодействия ваша программа должна:

  1. Считать целое число a0,0 из входного потока.
  2. Если a0,0 равно  − 1, игра закончена, ваша программа должна завершиться.
  3. Иначе, считать N ⋅ M − 1 чисел ai,j — числовые значения клеток, выведенные построчно.

    Соответствующая клетка пуста, если ai,j равно 0.

    a0,0 — числовое значение в первой клетке или 0, если клетка пуста.

  4. Выведите символ команды сдвига ('l', 'r', 'u' или 'd' для сдвига влево, вправо, вверх или вниз соответственно) с последующим символом конца строки.

    Не забудьте очистить буфер. (flush)

Формат входных данных

Первая строка входного потока состоит из двух чисел N и M  — размеры поля.

Далее на каждом шаге следует N строк по M чисел, задающих каждую клетку. 0, если клетка пустая.

Входной поток содержит единственное число  − 1, если игра окончена.

Формат выходных данных

В выходной поток на каждой итерации необходимо вывести единственный символ, характеризующий направление сдвига и символ конца строки.

Символ 'l'  — движение плиток влево, 'r'  — вправо, 'u'  — вверх, 'd'  — вниз.

Ограничения

Количество шагов не превышает 104

2 ≤ N, M ≤ 10


0.063s 0.012s 13