10/04/2025 22:08:02

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1800. Робот

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Робот-марсоход "ТцТцПетя" двигается по поверхности Марса как ему вздумается, отправляя на Землю информацию о своих передвижениях.

"ТцТцПетя" пользуется следующей системой координат: начало координат совпадает с его начальным положением, ось

$"OY"$ направлена в сторону, в которую он направлен в начальный момент времени (при высадке на Марс).

Передвигается "ТцТцПетя" следующим образом: после высадки на Марс он проезжает вперед какое-то целое число сантиметров, от

$1$ до

$10^6$ ; затем поворачивает на 90 градусов либо налево, либо направо; после чего снова проезжает вперед от

$1$ до

$10^6$ сантиметров; и снова поворачивает на 90 градусов либо налево, либо направо; и так далее. Наконец, проехав последний отрезок (также длиной от

$1$ до

$10^6$ сантиметров), он останавливается и начинает передавать на Землю описание своего маршрута.

В итоге Центр Управления получил от "ТцТцПети" следующее сообщение: "Я сделал

$n$ передвижений. Сообщаю

$n-1$ поворот, который я совершил: последовательность поворотов. В итоге я оказался в точке с координатами

$(x,\ y)$ . Мне тут нравится. Конец связи."

И тут-то создатели "ТцТцПети" поняли, что забыли запрограммировать его, чтобы он сообщал длины своих передвижений!

Теперь их интересует хоть какой-нибудь вариант пути "ТцТцПети", который удовлетворяет полученным от него данным. Помогите им.

В первой строке входного файла содержатся три целых числа

$x$ ,

$y$ ,

$n$ (

$-100\ 000\ ≤\ x,\ y\ ≤\ 100\ 000$ ;

$1\ ≤\ n\ ≤\ 100\ 000$ ) – конечные координаты "ТцТцПети" и количество передвижений, которые он совершил.

Вторая строка имеет длину

$n-1$ и состоит из символов L и R – это последовательность поворотов, которые совершил "ТцТцПетя". Символ L обозначает поворот налево на 90 градусов, символ R – направо на 90 градусов.

Если информация противоречива и двигаться подобным образом робот не мог, выведите в выходной файл слово Impossible.

В противном случае выведите

$n$ целых чисел от

$1$ до

$10^6$ – длины передвижений "ТцТцПети" в сантиметрах, такие что с учетом указанных им поворотов, "ТцТцПетя" заканчивает движение в точке

$(x,\ y)$ . Числа должны быть разделены пробелами и/или переводами строк.

Пример ввода 1

-2 -1 4
RRR

Пример вывода 1

1 1 2 3

Пример ввода 2

4 1 5
LRRL

Пример вывода 2

Impossible

Пример ввода 3

0 10 1

Пример вывода 3

Примечание: поверхность Марса в рамках данной задачи считается плоской.

Источник: командный чемпионат школьников Санкт-Петербурга по программированию, 2010

25/06/2012	Лето 2012 - дорешивание ( 9G)
09/07/2012	Лето 2012 - 9 (G)