Задача C. RAM-машина

Автор:Зимние сборы 2005   Ограничение времени:2 сек
Входной файл:ram.in   Ограничение памяти:64 Мб
Выходной файл:ram.out  

Условие

RAM-машина — это простейшая модель вычислительной машины, зачастую используемая для анализа различных алгоритмов. Эта машина состоит из процессора, памяти, а также устройств ввода и вывода. Память RAM-машины представляет собой адресное пространство из регистров, в каждом из которых может быть записано некоторое целое число. Устройство ввода — это лента, с которой RAM-машина может читать в память входные данные. Кроме того, RAM-машина может выводить некоторые числа из своей памяти на устройство вывода.

Операндом команды для процессора RAM-машины может являться либо непосредственное значение (записывается =i), либо значение регистра с номером i (записывается i в записи программы, кроме того, для удобства определения системы команд часто используют обозначение c(a) для обозначения регистра с номером, равным значению параметра a), либо значение регистра с номером, записанном в регистре номер i (т.е. c(c(i)), в записи программы это обозначается как *i). Также для удобства описания вводится запись v(a), определяемая следующим образом:

То есть, значение v(a) равно тому значению, которое будет использовано, если операнд команды записан как a.

Программа для RAM-машины представляет собой пронумерованную (начиная с 0) последовательность команд для процессора. Процессор RAM-машины умеет исполнять следующие команды:

КомандаДействиеОписание
LOAD ac(0) ← v(a)Загружает в регистр 0 значение v(a)
STORE ic(i) ← c(0)Загружает в регистр i значение регистра 0
STORE *ic(c(i)) ← c(0)Загружает в регистр c(i) значение регистра 0
ADD ac(0) ← c(0)+v(a)Складывает c(0) и v(a)
SUB ac(0) ← c(0)-v(a)Вычитает из c(0) значение v(a)
MULT ac(0) ← c(0) × v(a)Умножает регистр 0 на v(a)
DIV ac(0) ← c(0) div v(a)Целочисленное деление регистра 0 на v(a)
READ ic(i) ← входЧитает из ввода значение в регистр i
READ *ic(c(i)) ← входЧитает из ввода значение в регистр c(i)
WRITE aвыход ← v(a)Выводит на устройство вывода значение v(a)
JUMP b Безусловный переход на команду номер b
JGTZ b Переход на команду номер b, если c(0)>0
JZERO b Переход на команду номер b, если c(0)=0
HALT Окончание работы программы
Команды выполняются в порядке возрастания номера. Кроме того, после команды JUMP b всегда выполняется команда с номером b, а после команд условного перехода в случае выполнения указанного условия выполняется команда с номером b, а иначе выполняется следующая по номеру команда.

Вашей задачей будет промоделировать работу RAM-машины. При моделировании вы можете считать, что RAM-машина содержит всего 1000 регистров (пронумерованных от 0 до 999), и работает с 16-битными знаковыми целыми числами. Деление работает так же, как операция div в языке Паскаль.

Формат входного файла

В первой строке входного файла содержатся числа m и n — число команд в программе и количество чисел на входной ленте RAM-машины. Далее в m строках записана программа для RAM-машины, по одной команде на строку, в каждой строке записаны название команды и операнд (если он есть), разделенные пробелами. После описания программы идут n целых чисел, разделенные произвольным количеством пробелов и переводов строки — числа, которые будут читаться со входной ленты при выполнении команд READ.

Гарантируется, что входные данные корректны, что программа не будет использовать значения регистров, в которые не загружено никакое число, а также читать с устройства ввода больше чисел, чем присутствует в описании входных данных или переходить на команду с номером, которой нет в программе. Кроме того, программа не будет исполнять больше, чем 10,000,000 команд. Также программа не будет исполнять операций, которые могут приводить к переполнению или любой другой ошибке (например, делению на 0).

Формат выходного файла

В выходной файл должны быть выведены (по одному на строку) все числа, которые исполняемая программа выдала с помощью команды WRITE.

Ограничения

1 ≤ m, n ≤ 1000

Примеры тестов

Входной файл (ram.in) Выходной файл (ram.out)
1
4 1
READ  0
ADD   =1
WRITE 0
HALT
5
6
2
16 5
LOAD  =0
STORE 21
READ  20
READ  *20
LOAD  21
ADD   *20
STORE 21
LOAD  20
SUB   =1
STORE 20
JGTZ  3
READ  0
WRITE *0
WRITE 21
WRITE =0
HALT
3
5 6     7
   2
6
18
0

0.079s 0.011s 13