ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Open Personal Contest 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Time Limit Exceeded

Time limit: 1.5 second
Memory limit: 64 MB
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 compilers.
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 three forms:
<label>: <command>
Here <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), and <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 notation: <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:
print <varnum>
<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>
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>
if <varnum> < <varnum> goto <label>
Commands in a program are executed successively. The 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: addition (+), subtraction (-), multiplication (*), integer division (/), remainder taking (%), and bitwise logic operations: `or' (or), `and' (and), `exclusive or' (xor), and negation (not). 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. The if ... goto command works just as the goto 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 print commands). 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
      Print Y
      y = Y - 5
      Print y
        value = 15
        value = not value
        value = value or 4
        print value
        value = 0
        value = value - 1
        Value = value % 6
        ValueA = value % -6
        goto loop
Program terminated. Variables state:
Value: 3
ValueA: 3
value: -2499999
Problem Author: Aleksandr Klepinin
Problem Source: The 7th USU Open Personal Contest - February 25, 2006
To submit the solution for this problem go to the Problem set: 1438. Time Limit Exceeded