Тюрінг#6923

Тюрінг

1 секунда

64 мегабайти

Середня

Деякі цікаві документи нещодавно були знайдені в архівах ACM. Вони містять опис оригінальної версії змагання ACM ICPC, яке відбулося в Блетчлі-Парк, Англія, у $1943$ році.

У цьому першому конкурсі програми, подані учасниками, виконувалися на спрощеній версії детермінованої машини Тюрінга, з якою, без сумніву, більшість з вас знайомі. У цій версії стрічка не є нескінченною. Замість цього, комірки стрічки пронумеровані від $0$ до $1 0^{3} - 1$ 10^3-1 (включно), зліва направо. Використовується унарний алфавіт, що означає, що перед виконанням програми стрічка буде ініціалізована рядком, що складається з $n$ одиниць, за якими йдуть всі нулі, де $n$ — це числове значення вхідних даних, а після виконання вміст стрічки повинен бути $m$ одиниць, за якими йдуть всі нулі, де $m$ — це числове значення відповідного виходу. На початку головка стрічки знаходиться на позиції $0$ , а стани також пронумеровані, починаючи з $0$ , який вважається початковим станом. Машини працюють, як зазвичай: для кожного стану машини $q$ і кожного біта $c$ ( $0$ або $1$ ) існує не більше одного правила, яке визначає, яким буде наступний стан, якщо символ на позиції головки стрічки є $c$ і поточний стан є $q$ ; правило також визначає символ, який потрібно записати на поточну позицію, і в якому напрямку повинна рухатися головка. Коли жодне правило не застосовується, машина зупиняється.

Ваше завдання — написати програму, яка отримує одну з машин Тюрінга, поданих учасниками, а також тестові випадки (пари вхідних і вихідних даних), і повертає вердикт щодо результатів машини для кожного з випадків. Зверніть увагу, що в цьому оригінальному конкурсі, на відміну від поточного, був різний вердикт для кожного тестового випадку, а не загальний.

Вхідні дані

Вхідні дані складаються з серії специфікацій (не більше $30$ ) машини Тюрінга та відповідних тестових випадків.

Структура кожного тестового випадку наступна:

Перший рядок містить $1 \leq N \leq 1000$ 1 \le N \le 1000, кількість правил для машини, та $1 \leq M \leq 100$ 1 \le M \le 100, кількість тестових випадків для машини Тюрінга.

Далі йдуть $N$ рядків, кожен з яких містить правило у форматі $q_{prev}$ q_{\text{prev}} $c_{prev}$ c_{\text{prev}} $q_{next}$ q_{\text{next}} $c_{next}$ c_{\text{next}} $m o v$ . $q_{prev}$ q_{\text{prev}} — це стан машини перед застосуванням правила, $c_{prev}$ c_{\text{prev}} — вміст ( $0$ або $1$ ) стрічки на поточній позиції $p$ перед застосуванням правила, $q_{next}$ q_{\text{next}} — це стан машини після застосування правила, $c_{next}$ c_{\text{next}} — вміст позиції $p$ після застосування правила, а $m o v$ — це напрямок, у якому головка стрічки переміщується на один крок після застосування правила ("L", якщо вона рухається вліво, і "R", якщо вправо). Стани повинні бути цілими числами від $0$ до $1000$ , включно. Машина Тюрінга повинна бути детермінованою; тобто, має бути не більше одного переходу з будь-якої пари ( $q_{prev}$ q_{\text{prev}}, $c_{prev}$ c_{\text{prev}}), і не повинні повторюватися у вашому виході.

Після цього йдуть $M$ рядків, кожен з яких містить два числа, розділені пробілом, $X$ та $Y$ , $1 \leq X, Y \leq 1000$ 1 \le X, Y \le 1000. $X$ — це значення вхідних даних програми, а $Y$ — це значення очікуваного виходу.

Кінець вводу сигналізується випадком з $N = 0$ N = 0 та $M = 0$ M = 0.

Вихідні дані

Ваш вихід повинен бути MLE, якщо машина намагається отримати доступ до будь-якої комірки за межами діапазону стрічки, зазначеного вище; TLE, якщо вона працює принаймні $1 0^{4}$ 10^4 ітерацій без зупинки або виклику помилки MLE; WA, якщо машина зупиняється, але повертає неправильний результат, і AC, якщо машина зупиняється і повертає очікуваний результат.

Вихід для кожного випадку повинен бути в окремому рядку.

Приклади

Приклад 1