Задача №112775. The Cake is a Lie
GLaDOS приготовила для Челл новое, последнее испытание! В его рамках ей предстоит найти торт. Но всё не так-то просто — у неё отобрали портальную пушку и завязали глаза. Единственное, что Челл известно, — что она находится в прямоугольной комнате, выложенной квадратной плиткой, и что где-то в этой комнате расположен торт. Всё что остаётся делать Челл, — слепо переходить с плитки на плитку в поисках торта.
Кроме того, так как действие происходит в Лаборатории Исследования Природы Порталов, на каждой стене комнаты расположен портал, связанный с противоположной стеной. Формально: рассмотрим комнату как прямоугольную сетку размера \(W × H\) и введем систему координат так, чтобы левая нижняя ячейка сетки имела координаты (0, 0), а правая верхняя — (\(W − 1, H − 1\)). За один шаг Челл может перейти в одну из четырёх соседних ячеек, причём попытка пройти сквозь стену приводит к тому, что Челл появляется с противоположной стороны комнаты. Например, шаг вниз из ячейки (\(x\), 0) приведёт в ячейку (\(x, H −1\)), а шаг влево из ячейки (0, \(y\)) приведёт в ячейку (\(W −1\), \(y\)).
Чтобы сделать испытание сложнее, GLaDOS не сообщила Челл ни размеры комнаты, ни координаты её изначального положения, ни координаты торта. Более того, так как у Челл завязаны глаза, а портальная технология достигла совершенства в своём развитии, Челл даже не может определить, прошла ли она очередным ходом через портал или нет.
Челл может найти торт, только оказавшись в одной клетке с ним. Помогите ей пройти последнее испытание!
Это интерактивная задача.
Ваша программа будет общаться с тестирующей системой по протоколу, описанному ниже. Вам разрешается произвести не более 200 000 ходов.
Чтобы переместиться в соседнюю ячейку, выведите строку, содержащую ровно один символ, задающий направление перемещения: «U» — вверх; «D» — вниз; «L» — влево; «R» — вправо. Затем вы должны считать строку, в которой будет находиться ровно один символ, обозначающий результат перемещения:
• «Y» — после произведённого хода Челл оказалась в клетке с тортом;
• «N» — после произведённого хода Челл оказалась в клетке, не содержащей торт;
• «E» — служебный символ, обозначающий, что после произведённого хода Челл всё ещё не нашла торт, а ваша программа превысила ограничение на количество ходов.
Обратите внимание, после считывания символа «Y» или «E» вы обязательно должны сразу завершить вашу программу. В противном случае, вердикт тестирующей системы может быть некорректным!
Гарантируется, что в клетке, в которой исходно находится Челл, нет торта.
В точности соблюдайте формат выходных данных. После вывода каждой строки сбрасывайте буфер вывода — для этого используйте команды flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в C/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.
Пояснение к примеру из условия. В примере из условия поле может выглядеть следующим об- разом:
Обозначим за \(Q\) количество ходов, которое произвела ваша программа, прежде чем найти тортик. Помимо общего ограничения \(Q \le 200 000\), для каждой группы тестов может быть своё ограничение, связывающее \(Q\) и \(S\), где \(S = W \cdot H\) — площадь комнаты. При превышении любого из этих ограничений, ваша программа получает вердикт Wrong Answer.
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
Для установки правильности вашей программы жюри может запускать её произвольное количество раз для одной и той же комнаты, располагая в ней торт в различных места