Подразделы

Другие разделы

Дата и время

09/04/2025 10:08:16

Авторизация

Зарегистрироваться
Восстановить пароль

Лето 7

A. Пересечение окружностей B. Set me C. Ладьи D. Зеркала E. Вопль F. Робот G. Общая подстрока

F. Робот

Ограничения: время – 5s/10s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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/