ZOJ Problem Set - 1190
As you know, writing programs is often far from being easy. Things become even harder if your programs have to be as fast as possible. And sometimes there is reason for them to be. Many large programs such as operating systems or databases have ``bottlenecks'' - segments of code that get executed over and over again, and make up for a large portion of the total running time. Here it usually pays to rewrite that code portion in assembly language, since even small gains in running time will matter a lot if the code is executed billions of times.
In this problem we will consider the task of automating the generation of optimal assembly code. Given a function (as a series of input/output pairs), you are to come up with the shortest assembly program that computes this function.
The programs you produce will have to run on a stack based machine, that supports only five commands: ADD, SUB, MUL, DIV and DUP. The first four commands pop the two top elements from the stack and push their sum, difference, product or integer quotient , respectively, on the stack. The DUP command pushes an additional copy of the top-most stack element on the stack.
So if the commands are applied to a stack with the two top elements a and b (shown to the left), the resulting stacks look as follows:
At the beginning of the execution of a program, the stack will contain a single integer only: the input. At the end of the computation, the stack must also contain only one integer; this number is the result of the computation.
There are three cases in which the stack machine enters an error state:
A DIV-command is executed, and the top-most element of the stack is 0.
A ADD, SUB, MUL or DIV-command is executed when the stack contains only one element.
An operation produces a value greater than 30000 in absolute value.
Output a blank line after each test case.
Source: Southwestern Europe 1998