ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1231. Тьюринг: раз, два, три, …

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Problem illustration
Машина Тьюринга используется для исследований вычислимости и хорошо знакома людям, занимающимся теорией алгоритмов. Дадим краткое описание этой абстракции. Машина Тьюринга — автоматическое устройство, которое работает с лентой (1) потенциально неограниченной длины. Лента разделена на ячейки, каждая из которых хранит один символ. Одна из ячеек называется текущей (2). В любой момент времени машина Тьюринга находится в некотором состоянии, которое записано в управляющем устройстве (4). Кроме того, головка чтения/записи (3) управляющего устройства указывает на текущую ячейку.
Управляющее устройство выполняет одно действие за единицу времени (шаг). Действие включает возможное изменение состояния, возможное изменение символа в текущей ячейке и возможное движение головки чтения/записи в соседнюю ячейку. Эти действия определены в специальной таблице, называемой управляющей таблицей. Обозначим движение вдоль ленты следующими символами: "<" — влево, ">" — вправо, "=" — движение отсутствует.
Управляющая таблица является программой для машины Тьюринга. Работа машины Тьюринга считается завершённой, когда ни одна строка управляющей таблицы не содержит комбинации текущего символа и текущего состояния.
Пример управляющей таблицы:
Текущее состояние Текущий символ Новое состояние Новый символ Движение
1 - 2 - >
2 - 3 + >
3 # 4 # <
4 + 4 + <
4 - 5 - =
Замечание. Этот пример только иллюстрирует определение таблицы.
Исходные данные для машины Тьюринга заранее помещаются в клетки ленты. Результат записывается на ту же ленту. Будем считать, что исходное состояние машины Тьюринга равно 1, а входные данные на ленте ограничены символами '#' с обоих концов. (Все ячейки ленты, кроме заполненных минусами, заполнены символами '#'.) Головка управляющего устройства указывает на самый левый символ '−' входных данных. В начале работы лента содержит знак '−' (минус), повторённый n раз (1 ≤ n ≤ 200), а ввод вашей программы содержит целое число k.
Представьте, что минусы расположены по кругу. Начиная с первого, каждый k-й незачёркнутый минус зачёркивается, то есть превращается в '+' (плюс). Исполнение останавливается, когда остаётся только один незачёркнутый минус. Ваша задача — описать управляющую таблицу для машины Тьюринга, которая зачеркнёт все минусы, кроме одного (его позиция определена в соответствии с описанным выше алгоритмом, но вы можете использовать любой способ нахождения позиции) для заданного k. Например, для n = 10 и k = 3 четвёртый минус останется незачёркнутым.
Разрешается записывать на ленту следующие символы: '+', '#', 'A'..'Z'. Клетки, изначально заполненные минусами, могут содержать только символы '−' и '+'. Клетка, в которой останется минус, не должна меняться. После выполнения головка чтения/записи должна указывать на незачёркнутый минус. Количество шагов s не должно превосходить 1 000 000. Количество строк p в таблице управления не должно превосходить 10 000. Размер ленты ограничен 10 001 ячейкой (5000 с каждой стороны от начального положения головки чтения/записи).

Исходные данные

Ввод содержит целое число k (1 ≤ k ≤ 200).

Результат

Вывод описывает управляющую таблицу машины Тьюринга для заданного значения k. Первая строка вывода содержит число строк p таблицы (1 < p < 10 000). Затем следует p строк, описывающих саму таблицу. Каждая строка таблицы содержит пять элементов: текущее состояние (целое число), текущий символ (символ), новое состояние (целое число), новый символ (символ), направление движения (символ). Элементы строки разделены одиночными пробелами. Номера состояний могут быть от 1 до 30 000.

Пример

исходные данныерезультат
2
5
1 - 2 - >
2 - 3 + >
3 # 4 # <
4 + 4 + <
4 - 5 - =

Замечания

Обратите внимание, что этот пример правилен только для n = 2. Он только показывает формат вывода.
Источник задачи: Четвертьфинальные соревнования ACM ICPC 2002–2003 в центральном регионе России, Рыбинск, октябрь 2002