| Автор: | Зимние сборы 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), определяемая следующим образом:
Программа для RAM-машины представляет собой пронумерованную (начиная с 0) последовательность команд для процессора. Процессор RAM-машины умеет исполнять следующие команды:
| Команда | Действие | Описание |
|---|---|---|
| LOAD a | c(0) ← v(a) | Загружает в регистр 0 значение v(a) |
| STORE i | c(i) ← c(0) | Загружает в регистр i значение регистра 0 |
| STORE *i | c(c(i)) ← c(0) | Загружает в регистр c(i) значение регистра 0 |
| ADD a | c(0) ← c(0)+v(a) | Складывает c(0) и v(a) |
| SUB a | c(0) ← c(0)-v(a) | Вычитает из c(0) значение v(a) |
| MULT a | c(0) ← c(0) × v(a) | Умножает регистр 0 на v(a) |
| DIV a | c(0) ← c(0) div v(a) | Целочисленное деление регистра 0 на v(a) |
| READ i | c(i) ← вход | Читает из ввода значение в регистр i |
| READ *i | c(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 | | Окончание работы программы |
Вашей задачей будет промоделировать работу RAM-машины. При моделировании вы можете считать, что RAM-машина содержит всего 1000 регистров (пронумерованных от 0 до 999), и работает с 16-битными знаковыми целыми числами. Деление работает так же, как операция div в языке Паскаль.
В первой строке входного файла содержатся числа m и n — число команд в программе и количество чисел на входной ленте RAM-машины. Далее в m строках записана программа для RAM-машины, по одной команде на строку, в каждой строке записаны название команды и операнд (если он есть), разделенные пробелами. После описания программы идут n целых чисел, разделенные произвольным количеством пробелов и переводов строки — числа, которые будут читаться со входной ленты при выполнении команд READ.
Гарантируется, что входные данные корректны, что программа не будет использовать значения регистров, в которые не загружено никакое число, а также читать с устройства ввода больше чисел, чем присутствует в описании входных данных или переходить на команду с номером, которой нет в программе. Кроме того, программа не будет исполнять больше, чем 10,000,000 команд. Также программа не будет исполнять операций, которые могут приводить к переполнению или любой другой ошибке (например, делению на 0).
В выходной файл должны быть выведены (по одному на строку) все числа, которые исполняемая программа выдала с помощью команды WRITE.
| № | Входной файл (ram.in) |
Выходной файл (ram.out) |
|---|---|---|
| 1 | |
|
| 2 | |
|