Gnirut#6924

Gnirut

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$ ; правило також визначає символ, який потрібно записати на поточній позиції, і в якому напрямку повинна рухатися головка. Коли жодне правило не застосовується, машина зупиняється.

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

Це відкриття привернуло увагу відомого авантюриста Зафода Біблброкса, який має намір розпочати проект зі створення прикладів машин та вхідних/вихідних "файлів", які могли б спричинити ці вердикти. Не лише всі ваші зусилля змусити його зрозуміти марність такого підприємства зазнали невдачі, але ви також були змушені написати для нього програму, яка генерує такі приклади. Ваша програма повинна отримати серію вердиктів про одну з машин Тюрінга, поданих учасниками, і повернути специфікації машини Тюрінга, а також серію тестових випадків, для яких вердикти є такими, які ви отримали.

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

Вхідні дані

Вхід складається з певної кількості (не більше $30$ ) серій вердиктів. Перша строка для кожної містить $1 \leq N \leq 100$ 1 \le N \le 100, кількість вердиктів у випадку. Наступні $N$ рядків містять одне з слів TLE, MLE, WA і AC.

Кінець вводу позначається випадком з $N = 0$ N = 0, який не слід обробляти.

Вихідні дані

Для даного тестового випадку для вашої програми ваш вихід повинен відповідати наступному формату:

Перша строка містить $1 \leq M \leq 1000$ 1 \le M \le 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 \leq X, Y \leq 1000$ 1 \le X, Y \le 1000. $X$ — це значення вхідних даних для програми, а $Y$ — це значення очікуваного виходу.

Примітка: Хоча це рекомендований синтаксис, інші комбінації нових рядків і пробільних символів також можуть бути прийняті.

Приклади

Приклад 1