Задача A. Косвенная машина

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

Условие

Ваша задача — проэмулировать простую косвенную машину, предназначенную для исполнения арифметических операций.

Память этой машины представляет собой 32768 16-битных целых ячеек с номерами от 1 до 32768. Когда машина читает или пишет одну из этих ячеек, она в первую очередь проверяет число, записанное в этой ячейке. Если это число оказывается неотрицательным, то операция производится с этой ячейкой. Иначе абсолютная величина записанного в ячейке числа рассматривается как новый адрес для чтения/записи, и вышеописанный процесс повторяется. Если при выполнении операции чтения/записи машина входит в цикл, это считается ошибкой исполнения, и происходит останов машины.

У машины имеется единственный 16-битный регистр — аккумулятор. Все операции производятся с этим регистром. В случае переполнения значение берется по модулю 216 в пределах от  − 32768 до 32767, как и в большинстве 16-битных систем.

Программа для этой машины состоит из не более чем 262144 инструкций. Вот список возможных команд:

  1. A*memory — складывает значение заданной ячейки памяти с аккумулятором.
  2. S*memory — вычитает значение заданной ячейки памяти из аккумулятора.
  3. M*memory — умножает значение аккумулятора на значение заданной ячейки памяти.
  4. D*memory — делит значение аккумулятора на значение заданной ячейки памяти. Деление производится так же, как в процессорах Intel.
  5. O*memory — записать в аккумулятор значение остатка от деления аккумулятора на значение заданной ячейки памяти.
  6. R*memory — читает значение заданной ячейки памяти в аккумулятор.
  7. W*memory — пишет в заданную ячейку памяти значение аккумулятора.
  8. A=constant — добавляет заданное число к аккумулятору.
  9. S=constant — вычитает заданное число из аккумулятора.
  10. M=constant — умножает аккумулятор на заданное число.
  11. D=constant — делит аккумулятор на заданное число.
  12. O=constant — записывает в аккумулятор остаток от деления аккумулятора на заданное целое число.
  13. R=constant — записывает в аккумулятор заданную константу.

Все обращения к памяти во время исполнения команд делаются так, как описано в начале условия. Деление и взятие остатка работают как операции div и mod в языке Паскаль. Все числа целые.

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

Входной файл содержит корректную программу для косвенной машины, по одной инструкции на строке. Машина начинает работу с нулевым аккумулятором и с нулевой памятью. Все адреса во входном файле корректны и лежат в пределах от 1 до 32768. Все непосредственные аргументы (для операций со знаком равенства `=') удовлетворяют стандартным ограничениям на 16-битные целые.

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

Первая строка выходного файла должна содержать код завершения программы. Если программа завершилась успешно, требуется вывести строчку SUCCESSFUL TERMINATION. Если произошло деление на 0, то нужно вывести строку DIVISION BY ZERO. В случае ошибки исполнения выведите в первой строке RUN-TIME ERROR. Вторая строка должна содержать значение аккумулятора после завершения. Последующие 32768 строк содержат 32768 целых чисел — значения ячеек памяти после завершения программы. В случае ошибки исполнения или деления на ноль программа немедленно завершается и необходимо выводить состояние памяти и аккумулятора перед ошибочной инструкцией.

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

Входной файл (indirect.in) Выходной файл (indirect.out)
1
R=2
A=2
W*1
R=0
S*1
W*1
R*1
S=2
W*1
R=1
W*1
SUCCESSFUL TERMINATION
1
-4
1
0
-2
0
предыдущая строчка повторяется 32763 раза
2
R=2
D*1
R=3
DIVISION BY ZERO
2
0
предыдущая строчка повторяется 32767 раз
3
R=-1
W*1
W*1
A=2
RUN-TIME ERROR
-1
-1
0
предыдущая строчка повторяется 32766 раз

Задача B. Две инструкции

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

Условие

Возможно, самой важной инструкцией процессора 8086 является команда «pop sp», которая берёт значение указателя стека с вершины стека.

В дополнение к этой команде в процессоре 80486 была добавлена другая очень важная инструкция для работы с регистром указателя стека — «bswap sp». Она меняет местами старший и младший байт указателя.

Вам дано начальное значение регистра sp и содержимое памяти. Постройте самую короткую программу, которая после своего завершения получит в sp заданное конечное значение. Программа должна состоять только из операций «pop sp» и «bswap sp».

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

Первая строка содержит два шестнадцатибитных числа в пределах от 0000 до FFFF — начальное и конечное значение регистра sp. Следующие 4096 строк содержат дамп сегмента памяти.

Дамп задается в формате [8 байт][2 пробела][8 байт], где [8 байт] - это 8 значений последовательных байтов, разделенных одним пробелом. Байт задается как шестнадцатеричное число в пределах от 00 до FF, имеющее ровно две цифры.

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

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

Если существует несколько кратчайших программ, выведите лексикографически наименьшую.

Если невозможно решить задачу для заданного дампа и значений sp, выведите единственную строку со словом IMPOSSIBLE.

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

Входной файл (2instr.in) Выходной файл (2instr.out)
1
0003 00EF
00 00 EF 00 02 00 00 00  00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00
предыдущая строчка повторяется ещё 4094 раза
4
5C 0F CC 5C

Задача 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.257s 0.012s 17