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

Условие

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

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

У машины имеется единственный 16-битный регистр — аккумулятор. Все операции производятся с этим регистром. В случае переполнения значение берется по модулю 2¹⁶ в пределах от −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 в языке Паскаль. Все числа целые.

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

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

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

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 раза

R=2
D*1
R=3

DIVISION BY ZERO
2
0
предыдущая строчка повторяется 32767 раз

R=-1
W*1
W*1
A=2

RUN-TIME ERROR
-1
-1
0
предыдущая строчка повторяется 32766 раз

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

Условие

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

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

• ``bswap sp'' имеет код инструкции 0F CC;
• ``pop sp'' имеет код инструкции 5C;
• сегмент памяти имеет длину 65536 байт;
• Память считается зацикленной — после ячейки с адресом FFFF идет ячейка с адресом 0000 (все адреса и коды даны в шестнадцатеричной системе);
• ``pop sp'' берет значение двухбайтового слова по адресу, на который указывает sp, и загружает его в sp (младший байт идет первым).

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

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

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

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

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

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

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

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

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

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-машина ≡

Условие

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

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

• v(a)=i, если a записан как =i.
• v(a)=c(i), если a записан как i.
• v(a)=c(c(i)), если a записан как *i.

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

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

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

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

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

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

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

Ограничения

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

4 1
READ  0
ADD   =1
WRITE 0
HALT
5

6

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