Gnirut
Недавно в архивах ACM были обнаружены интересные документы, содержащие отчет о первой версии соревнования ACM ICPC, которое прошло в Блетчли-Парке, Англия, в 1943 году.
В этом соревновании программы участников выполнялись на упрощенной версии детерминированной машины Тьюринга, с которой многие из вас, вероятно, знакомы. В этой версии лента не бесконечна: ячейки пронумерованы от 0 до 10^3-1 включительно, слева направо. Используется унарный алфавит, то есть перед началом программы лента инициализируется строкой из n единиц, за которыми следуют нули, где n — это числовое значение входных данных. После выполнения программы на ленте должно остаться m единиц, за которыми следуют нули, где m — это числовое значение ожидаемого вывода. Головка ленты изначально находится в позиции 0, а состояния пронумерованы, начиная с 0, которое является начальным состоянием. Машина работает следующим образом: для каждого состояния q и каждого бита c (0 или 1) существует не более одного правила, определяющего следующее состояние, если символ под головкой c, а текущее состояние q; правило также указывает, какой символ записать в текущую позицию и в каком направлении должна двигаться головка. Если ни одно правило не применимо, машина останавливается.
К сожалению, в архивах сохранились только вердикты судей, без самих машин Тьюринга или тестов. В отличие от современных соревнований, в этом конкурсе для каждого теста был отдельный вердикт.
Это открытие заинтересовало известного авантюриста Зафода Библброкса, который решил создать примеры машин и входных/выходных "файлов", которые могли бы вызвать эти вердикты. Несмотря на все ваши попытки убедить его в бесполезности этой затеи, вы вынуждены написать программу, которая генерирует такие примеры. Ваша программа должна принимать серию вердиктов для одной из машин Тьюринга и возвращать спецификации машины, а также серию тестов, для которых вердикты совпадают с полученными.
Мы считаем, что вывод для машины будет MLE (превышение лимита памяти), если машина пытается обратиться к ячейке за пределами диапазона ленты; TLE (превышение лимита времени), если она выполняется не менее 10^4 итераций без остановки или ошибки MLE; WA (неверный ответ), если машина останавливается, но результат неверен, и AC (принято), если машина останавливается и результат верен.
Входные данные
Входные данные состоят из нескольких (не более 30) серий вердиктов. Первая строка каждой серии содержит 1 ≤ N ≤ 100, количество вердиктов в серии. Следующие N строк содержат одно из слов TLE, MLE, WA и AC.
Конец ввода обозначается случаем с N = 0, который не должен обрабатываться.
Выходные данные
Для данного теста ваша программа должна выводить данные в следующем формате:
Первая строка содержит 1 ≤ M ≤ 1000, количество правил для машины, и N, количество тестов для машины Тьюринга.
Далее следуют M строк, каждая из которых содержит правило в формате q_prev c_prev q_next c_next mov. q_prev — это состояние машины до применения правила, c_prev — содержимое (либо 0, либо 1) ленты в текущей позиции p до применения правила, q_next — состояние машины после применения правила, c_next — содержимое позиции p после применения правила, и mov — направление, в котором головка ленты перемещается на один шаг после применения правила ("L", если она перемещается влево, и "R", если она перемещается вправо). Состояния должны быть целыми числами от 0 до 1000 включительно. Машина Тьюринга должна быть детерминированной, то есть не более одного перехода от любой пары (q_prev, c_prev), и он не должен повторяться в вашем выводе. После этого следуют N строк, каждая из которых содержит два числа, разделенных пробелом, X и Y, 1 ≤ X, Y ≤ 1000. X — это значение входных данных для программы, а Y — значение ожидаемого вывода.
Примечание: Хотя это рекомендуемый синтаксис, другие комбинации новых строк и пробелов также могут быть приняты.