Time Limit Exceeded. A sad verdict of the checking system, which
often means that a wrong approach was used for solving the problem.
Probably, each ACM contestant has got this verdict at least once in
his ACM career. Of course, at such moments a contestant wants
computers to execute programs a bit quicker. It is a pity that
a correct algorithm (of course, it's correct!) does not work
only because the judges are using slow computers and inefficient
Here is a possibility for you to create a really quick code
that executes other's programs.
The input contains a program in the following format.
Each nonempty line of the file may have one of the following
<label> is the string's label in the program (the label
is unique within the program and consists of English letters,
the case (upper or lower) does not matter),
<command> is a command. The list of possible commands
is given below. The cases of the letters used in a command
may also be arbitrary.
In order to describe command formats, we will need the following
<variable> is a name of a variable (consists of English
letters, the case matters here);
<number> is an integer (all integers are in the range from -109 to 109);
<varnum> is either a name of a variable or an integer.
A program may contain the following commands:
<variable> = <varnum>
<variable> = <varnum> + <varnum>
<variable> = <varnum> - <varnum>
<variable> = <varnum> * <varnum>
<variable> = <varnum> / <varnum>
<variable> = <varnum> % <varnum>
<variable> = <varnum> or <varnum>
<variable> = <varnum> and <varnum>
<variable> = <varnum> xor <varnum>
<variable> = not <varnum>
if <varnum> == <varnum> goto <label>
if <varnum> != <varnum> goto <label>
if <varnum> >= <varnum> goto <label>
if <varnum> > <varnum> goto <label>
if <varnum> <= <varnum> goto <label>
if <varnum> < <varnum> goto <label>
Commands in a program are executed successively.
end command terminates the program. The
print command adds to the output file a line
containing the command's argument.
The assignment command works as usual (the variable is assigned the
result of processing the expression after the '=' symbol).
The operations have the following meaning:
+), subtraction (
-), multiplication (
integer division (
/), remainder taking (
and bitwise logic operations: `or' (
or), `and' (
`exclusive or' (
xor), and negation (
We assume that during the computation process, all values are stored as
4-byte integers, negative values are stored in a two's complement representation.
The result of a
goto command is that the program continues
work from the line with the specified label.
if ... goto command works just as the
command if the condition after
if is true, otherwise
the program jumps to the next line.
After executing ten million commands, the work of the program
is stopped forcibly and the diagnostic information is output.
You may assume that programs are syntactically correct, operands are always separated by at least one space, before being used each variable is initialized, length of names of variables and labels is limited by 50, and divisions by zero and overflows never happen. Assume also that program contains no more than 2000 lines and the
print command is executed not more than 100 times. Any number of spaces may occur in any place of the program, in the beginning of line, at the end of line, in empty lines, but not between label name and ':'.
The output should contain the result of executing the
program given in the input (i.e., it should contain lines
produced by the
If the program is stopped forcibly, then after the produced
output you should present the diagnostic information in the
following format. First you should print
"Program terminated. Variables state:".
After that you should output the list of initialized to this moment variables and their
values in the following format:
<variable name>: <value>.
The list of variables should be ordered lexicographically with
respect to the variables' names.
X = 5
Y = 1
loop: Y = Y * X
X = X - 1
if X >= 1 goto LOOP
y = Y - 5
value = 15
value = not value
value = value or 4
value = 0
value = value - 1
Value = value % 6
ValueA = value % -6
Program terminated. Variables state:
Problem Author: Aleksandr Klepinin
Problem Source: The 7th USU Open Personal Contest - February 25, 2006