Задача №114869. Угадай путь
Это интерактивная задача.
Вы готовитесь принять участие в соревнованиях по робототехнике. С помощью запусков робота на специальном поле с установленными на нём датчиками вам предстоит определить один из кратчайших путей по этому полю, который загадало жюри.
Поле, на котором предстоит запускать робота, имеет вид таблицы с \(m\) строками и \(n\) столбцами. Будем обозначать как \((i, j)\) клетку, лежащую в \(i\)-й строке и \(j\)-м столбце (\(1 \le i \le m\), \(1 \le j \le n\)). Любой путь, по которому можно запустить робота, должен начинаться в левой верхней клетке, имеющей координаты \((1, 1)\), проходить по некоторым клеткам поля и заканчиваться в правой нижней клетке, имеющей координаты \((m, n)\).
За один шаг робот может переместиться на одну клетку вниз или на одну клетку вправо. Таким образом, если робот находится в клетке с координатами \((i, j)\), то он может переместиться в клетку с координатами \((i + 1, j)\) или в клетку с координатами \((i, j + 1)\). Робот не может выходить за границы поля. Путь робота состоит из \(m + n - 2\) шагов, при выполнении которых робот перемещается из клетки с координатами \((1, 1)\) в клетку с координатами \((m, n)\), посещая при этом некоторые клетки поля.
Жюри соревнований загадало некоторый путь, по которому должен проехать робот. Этот путь неизвестен участникам. В каждой клетке, по которой проходит этот путь, был установлен специальный датчик. Когда робот оказывается в клетке, где установлен датчик, датчик фиксирует появление там робота.
Участник может несколько раз запустить своего робота вдоль любого корректного пути из клетки \((1, 1)\) в клетку \((m, n)\). После каждого запуска жюри сообщает в каких клетках датчики зафиксировали появление робота. Задачей участника является, запустив робота не более \(10\) раз, определить путь, который был загадан жюри.
Сначала на вход вашей программе подается два целых числа \(m\) и \(n\) — размеры поля, на котором запускается робот (\(1 \le m, n \le 1000\), \(m + n > 2\)).
После этого программа может делать запросы, каждый запрос соответствует запуску робота.
Для выполнения запроса необходимо вывести отдельной строке « ? \(s\) », где \(s\) — строка, задающая путь, по которому должен проехать робот. Эта строка должна иметь длину \(n+m-2\) и состоять из символов « D » и « R ». Если \(i\)-й символ строки равен « D », то на \(i\)-м шаге робот перемещается вниз, а если \(i\)-й символ строки равен « R », то вправо. Робот начинает путь в клетке с координатами \((1, 1)\), после исполнения всех шагов он должен оказаться в клетке с координатами \((m, n)\).
В ответ на запрос программа жюри выводит целое число \(t\) — количество клеток, в которых датчики зафиксировали прохождение робота (\(2 \le t \le m + n - 1\)). В следующих \(t\) строках она выводит по два целых числа \(r_i\), \(c_i\) — координаты клеток \((r_i, c_i)\), в которых датчики зафиксировали прохождение робота (для всех \(1 \le i \le t\) выполнено \(1 \le r_i \le m\), \(1 \le c_i \le n\)). Гарантируется, что все \(t\) клеток различны и выведены по возрастанию \(r_i\), а при равенстве \(r_i\) по возрастанию \(c_i\).
Определив корректный путь, ваша программа должна вывести строку « ! \(s\) », где \(s\) — строка, задающая в описанном выше формате загаданный жюри путь.
Если ваша программа сделает более \(10\) запросов запуска робота, задаст некорректный запрос или неверно угадает путь, она получит вердикт « Wrong Answer ».
3 4 RDRDR
2