Задача №113900. Робот в поле
Любимое занятие Андрюши — компьютерные игры. Недавно он обнаружил новую очень интересную игру.
Мир игры представляет собой бесконечное поле, разбитое на клетки, а каждая клетка имеет свои внутриигровые координаты. Игрок управляет роботом, стоящим изначально в клетке с координатами (0, 0) . Нажимая на соответствующие клавиши клавиатуры, игрок может перемещать робота влево, вверх, вправо и вниз. Строго говоря, управление роботом происходит следующим образом:
- Нажав на кнопку « L », игрок уменьшит первую координату робота на 1 .
- Нажав на кнопку « U », игрок увеличит вторую координату робота на 1 .
- Нажав на кнопку « R », игрок увеличит первую координату робота на 1 .
- Нажав на кнопку « D », игрок уменьшит вторую координату робота на 1 .
Задача игрока состоит в том, чтобы привести робота в клетку с заданными координатами ( x , y ) . Кому-то из вас данная игра может показаться очень простой, но у Андрюши никак не получалось ее пройти. В конце концов, он совсем отчаялся и узнал у своего друга Жени, на какие клавиши и в каком порядке надо нажимать, чтобы пройти игру. Но все оказалось не так просто! Прохождение Жени не подошло Андрюше, видимо, тот перемещался в другую клетку, и он очень сильно разозлился! Он так сильно надавил на некоторые клавиши, что они сломались и перестали реагировать на нажатия. К своему удивлению Андрюша заметил, что эти поломки могут ему даже помочь!
Андрюша решил проверить, можно ли всё-таки пройти игру, воспользовавшись прохождением Жени и сломав некоторые клавиши между некоторыми нажатиями. Если какая-то клавиша сломана, то при последующих нажатиях этой клавиши робот не будет менять своего местоположения. Андрюша может сломать любую клавишу после некоторого нажатия, причем он может сломать несколько клавиш после одного и того же нажатия. Более того, Андрюша может сломать любые клавиши перед началом прохождения игры, если это поможет достичь заданной клетки. Даже если цель будет достигнута, Андрюша сломает оставшиеся клавиши, чтобы больше не возвращаться к этой игре.
Он попросил вас помочь ему справиться с этой задачей.
В первой строке входных данных находится единственное целое n ( 1 ≤ n ≤ 1 000 000 ) — количество ходов в Женином прохождении игры.
Следующая строка содержит n символов « L », « U », « R », « D » — описание прохождения.
В третьей строке содержится пара чисел x , y ( - 1 000 000 ≤ x , y ≤ 1 000 000 ) — координаты клетки, в которой робот должен остановиться после всех нажатий.
Если никакие поломки клавиш не помогут Андрюше пройти игру, выведите единственное число - 1 .
В противном случае выведите четыре числа — номера нажатий, после которых нужно сломать клавиши « L », « U », « R », « D » соответственно. Если некоторую клавишу нужно сломать до начала игры, выведите для нее число 0 . Так как Андрюша ломает оставшиеся целыми клавиши после игры, то вы должны вывести число в диапазоне от 0 до n для каждой клавиши .
Если существует несколько правильных вариантов ответа, выведите любой из них.
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
В первом тесте из условия клетка назначения находится слишком далеко от стартовой позиции, и добраться до неё за не более чем 4 нажатия невозможно.
Во втором тесте из условия можно сломать все кнопки с самого начала, тогда робот не сдвинется с места и автоматически окажется в требуемой позиции.
В третьем тесте из условия, если сломать кнопки, как указано в ответе, итоговая последовательность действий, проделанных роботом, будет выглядеть как LURDRD и приведёт его в требуемую позицию.
4 LRUD 3 2
-1
4 DURL 0 0
3 1 0 0
8 LLURDRRD 1 -1
0 0 5 7