Задача №113344. Фишки
Это интерактивная задача. Ваша программа будет взаимодействовать с программой жюри, используя стандартный ввод и вывод.
Программа жюри решила сыграть с вашей программой в игру. На доске \(n \times n\) в двух различных клетках находятся две фишки. Ваша программа должна определить положение фишек. Для этого она может пытаться двигать фишки, а программа жюри будет сообщать результаты передвижений.
За один ход можно выбрать фишку и попросить переместить её на одну клетку влево, вправо, вверх или вниз. Программа жюри сообщает результат перемещения — если клетка в выбранном направлении существует и свободна, то перемещение считается успешным и фишка перемещается в эту клетку. В противном случае перемещение считается неудачным и фишка остается на той же клетке.
Вы выигрываете, если после очередного хода можете назвать исходное положение фишек на доске. Ваша задача — выиграть не более чем за \(6n\) ходов. Введем на доске систему координат таким образом, что клетки имеют координаты \((1, 1),(1, 2), \dots ,(1, n),(2, 1), \dots ,(n, n)\). Команды для перемещения фишки кодируются латинскими буквами следующим образом:
- «U» — переместиться с клетки \((x, y)\) на клетку \((x, y + 1)\).
- «D» — переместиться с клетки \((x, y)\) на клетку \((x, y − 1)\).
- «R» — переместиться с клетки \((x, y)\) на клетку \((x + 1, y)\).
- «L» — переместиться с клетки \((x, y)\) на клетку \((x − 1, y)\).
В самом начале программа жюри сообщает вашей программе натуральное число \(n (2 \le n \le 50)\) — размер доски.
Далее ваша программа должна повторять следующие ходы, выводя в стандартный поток вывода соответствующее сообщение и переводя строку. Перемещение фишки кодируется строкой «0 id c», где id — номер фишки, которую ваша программа хочет переместить (1 или 2), а символ c — направление движения. После каждого перемещения программа жюри сообщает вашей программе результат попытки перемещения:
• «1», если передвижение успешно;
• «0», если нет.
Когда ваша программа считает, что определила начальное положение фишек, следует вывести 5 чисел: «1 \(x_1 y_1 x_2 y_2\)» (\(1 \le x_1, y_1, x_2, y_2 \le n\)) — начальное положение первой фишки \((x_1, y_1)\) и второй фишки \((x_2, y_2)\), соответственно. После вывода этой команды ваша программа должна завершиться. Вывод этой команды не считается ходом и не включается в ограничение \(6n\) на число ходов.
В каждом тесте исходное положение фишек зафиксировано, и программа жюри честно отвечает на запросы вашей программы.
После каждого действия вашей программы выводите символ перевода строки. Если вы используете «writeln» в Паскале, «cout << ... << endl» в C++, «System.out.println» в Java или «print» в Python, сброс потока вывода у вас происходит автоматически, дополнительно делать «flush» не обязательно. Если вы используете другой способ вывода, рекомендуется делать «flush», но все равно обязательно требуется выводить символ перевода строки.
Ниже приведены наиболее типичные причины получения тех или иных сообщений об ошибке.
Если ваша программа соблюдает протокол, но неверно определяет начальное положение фишек, либо выполняет слишком много ходов, вы получите результат «Wrong Answer».
Если ваша программа выводит некорректно отформатированные сообщения программе жюри, то вы получите результат «Presentation Error», либо «Wrong Answer».
Если ваша программа нарушила протокол и ждет ввода в то же время, когда его ждет и программа жюри, то вы получите результат «Idleness Limit Exceeded». Обратите внимание, что к такому же результату может привести и то, что вы не переводите строку после каждого выведенного сообщения, или выводите не тем способом, который описан в начале раздела, и не делаете «flush».