Начало
Лето 7
F. Робот
Олимпиадные задачи на русском языке| 02/07/2007 | Лето 2007 дорешивание ( 7F) |
| 16/07/2007 | Лето 2007 - 7 (F) |
Ограничения: время – 5s/10s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Некоторый заводской цех представляет собой прямоугольник размером `M` на `N` метров
`(1\ ≤\ M,\ N\ ≤\ 30)`. Инженер-конструктор Петя создал робота, который может перемещаться по территории цеха и выполнять некоторую общественно-полезную работу. Робот может перемещаться только по плитам, размером 1 на 1 метр, которыми выложен пол цеха, и только параллельно осям координат.
У робота есть 4 регистра состояния: `A`, `B`, `C` и `D`. Каждый регистр может принимать одно из двух значений – TRUE или FALSE. На некоторых плитах цеха стоят радио-триггеры, которые переключают состояние каких-то регистров робота. Также на некоторых других плитах могут находиться радиомаяки, которые в зависимости от истинности формулы, соответствующей данному маяку, заставляют робота повернуть на 90 градусов налево или направо. В случае истинности совершается поворот направо.
Спецслужбы заинтересовались разработкой Пети, и решили проверить пригодность робота для работ в условиях радиации, под водой, в кратерах вулканов, на других планетах и много где еще. Для испытаний из цеха было вынесено все оборудование, поставлено некоторое количество радиомаяков и триггеров. Начиная с некоторой пустой плиты `X_0`, `Y_0` под начальным углом `A_0` (0, 90, 180 или 270 градусов, отсчитывая от направления вверх по часовой стрелке) был запущен робот. Изначально состояния всех регистров робота – FALSE.
Аккумуляторных батарей робота хватит на `K\ (0\ <\ K\ ≤\ 10^9)` перемещений на соседнюю плиту. После этого он остановится. Кроме того, возможен такой вариант, что Петя неправильно расставил триггеры и маяки, поэтому на некотором шаге робот врежется в стену цеха. Необходимо определить, уцелеет ли робот после испытаний и на какой клетке он остановится в случае положительного ответа на первый вопрос.
Оси координат направлены из левого верхнего угла – точки (1, 1) – соответственно вправо и вниз. `M` – размер цеха по горизонтали, а `N` – по вертикали. Количество триггеров – `P` – не превосходит 10000, а радиомаяков – `Q` – 25.
На первой строке входного файла записаны 8 чисел – `M,\ N,\ P,\ Q,\ K,\ X_0,\ Y_0,\ A_0`. Далее на `P` строках записаны триггеры в формате "`X\ Y\ R`", где `R` – название регистра. Далее на `Q` строках записаны радиомаяки в формате "`X\ Y\ F`", где `F` – булева функция от переменных `A…D` длиной не более 250 символов, заданная корректной формулой, причем:
- A, B, C, D, TRUE, FALSE – корректные формулы
- Если `F` – корректная формула, то "(`F`)" и "NOT `F`" – корректные формулы
- Если `F` и `G` – корректные формулы, то "`F` AND `G`", "`F` OR `G`" и "`F` XOR `G`" – корректные формулы
- Операция NOT имеет наивысший приоритет, остальные операции имеют одинаковые приоритеты и выполняются слева направо, т.е. A AND NOT B OR C XOR D эквивалентно (((A AND (NOT B)) OR C) XOR D)
- регистр букв не имеет значения
- корректная формула не содержит лишних пробелов
В случае успешного исхода вывести координаты плиты, где остановится робот. В случае краха эксперимента вывести в выходной файл единственное число `-1`.
Пример ввода
8 8 1 9 420000001 3 4 180 3 3 A 3 5 FALSE 6 5 FALSE 6 2 FALSE 3 2 A 3 1 FALSE 1 1 FALSE 1 8 FALSE 2 8 FALSE 2 2 TRUE
Пример вывода
3 5
В соответствии с рисунком, робот будет двигаться по «восьмерке» суммарной длиной 42 метра. Следовательно, прохождение `42n+1`метра эквивалентно прохождению 1 метра, т.е. робот остановится на плите с координатами (3, 5).
Источник: http://neerc.ifmo.ru/school/archive/