0049. Indirect Machine

Input file name: indirect.in
Output file name: indirect.out
Time limit: 2 s
Memory limit: 64 megabytes

Your task is to simulate a simple indirect machine designed for execution of arithmetic operations.

This machine has 32768 16-bit integer cells numbered from 1 to 32768. When machine reads or writes one of them, it first examines a number currently written in this cell. If the number is non-negative, the operation is performed with this cell. Otherwise absolute value of the written number is treated as a new address for this operation and all the above repeats again. If the machine enters a loop, it is considired a run-time error and the program halts.

The machine has only one 16-bit integer register called accumulator. All arithmetic operations are performed in this register. In case of overflow the value is taken modulo 216 (in range -32768…32767, as for most computing systems).

The program for this machine consists of no more than 262144 instructions which may be selected from the following set:

  1. A*memory – adds the value of the specified memory cell to the value in accumulator.
  2. S*memory – subtracts the value of the specified memory cell from the value of accumulator.
  3. M*memory – multiplies the value of accumulator by the value of the specified memory cell.
  4. D*memory – divides the value of accumulator by the value of the specified memory cell.
  5. O*memory – writes to the accumulator the remainder of division of the value of accumulator by the value of the specified memory cell.
  6. R*memory – reads the value of the specified memory cell to the accumulator.
  7. W*memory – writes the value of the accumulator to the specified memory cell.
  8. A=constant – adds the specified integer constant to the accumulator.
  9. S=constant – subtracts the specified integer constant from the accumulator.
  10. M=constant – multiplies the accumulator by the specified integer constant.
  11. D=constant – divides the accumulator by the specified integer constant.
  12. O=constant – writes to the accumulator the remainder of division of the value of accumulator by the specified integer constant.
  13. R=constant – writes to the accumulator the value of the specified integer constant.

All memory references during the execution of these commands are made by the way described above. The division and taking the remainder work as div and mod instructions in Pascal.

Input file

The input file will contains a correct program for the indirect machine, one instruction per line. There will be no more than 262144 instructions. The machine starts with zero accumulator and zero memory. It is guaranteed that all immediate memory addresses in the input file instructions are correct and do not lie outside the range 1…32768.

Output file

The first line of the output is considered the program termination code. If the last instruction was executed successfully, this line has to contain string SUCCESSFUL TERMINATION. If a division by zero occurs, output there the string DIVISION BY ZERO. In case of run-time error write in the first line the text RUN-TIME ERROR. The second line contains the value of the accumulator after termination. The next 32768 lines contain 32768 integer numbers – the values of memory cells from 1 to 32768 after the termination of the program. In case of the run-time error or division by zero the program immediately stops and the values correspond to the state of memory and accumulator before erroneous instruction.

Examples:

indirect.inindirect.out
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 --- above line repeats 32763 times ---
R=2 D*1 R=3 DIVISION BY ZERO 2 0 --- above line repeats 32767 times ---
R=-1 W*1 W*1 A=2 RUN-TIME ERROR -1 -1 0 --- above line repeats 32766 times ---


Source: Petrozavodsk training camp, Summer 2002. Conclusive contest
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version