Автор: | А. Баранов | Ограничение времени: | 1 сек | |
Входной файл: | input.txt | Ограничение памяти: | 16 Мб | |
Выходной файл: | output.txt |
Вася изобрел устройство, работающее по принципу конечного автомата. На вход ему подается циклическая цепочка (строка) символов, по которой двигается специальный указатель. За один такт устройства оно считывает символ, находящийся в текущей позиции указателя, и выполняет некоторое действие, определенное специальной таблицей команд.
Каждая i-я команда в такой таблице задается набором следующих значений: Si Ci Qi Hi, где Si — текущее состояние устройства; Ci — символ в текущей позиции; Qi — состояние, в которое следует перейти; Hi указывает величину, на которую необходимо сдвинуть указатель (положительные значения — вправо, отрицательные — влево).
Известно также, что программа прекратит свою работу в одном из следующих случаев:
Для некоторой заданной строки и таблицы команд требуется определить начальные условия (номер позиции и состояние)
при которых указанное устройство выполнит максимально возможное число шагов.
В начале входного файла "input.txt" хранится строка T, состоящая из цифр и строчных символов латинского алфавита.
Далее указано натуральное число M, за которым следует ровно M команд, записанных в указанном выше формате.
Выходной файл "output.txt" должен содержать номер стартовой позиции и начальное состояние.
При этом полагается, что нумерация позиций в строке начинается с нуля.
Гарантируется, что заданная программа является корректной
и не содержит взаимоисключающих инструкций.
0 < |T| ≤ 500, 0 ≤ (Si, Qi) < 1000, 0 ≤ |Hi| ≤ |T|,
0 < M ≤ 36 ⋅ 1000
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|