Optimal Programs#1756
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 a 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 a large portion of the total running time. It is usually worthwhile to rewrite such code segments 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 (described by a series of input/output pairs), you are to come up with the shortest assembly program that computes this function.
Your program 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, onto the stack. The DUP command pushes a copy of the top-most stack element onto the stack.
If the commands are applied to a stack with the two top elements and (on top), the resulting stacks appear as follows:
At the beginning of program execution, the stack will contain a single integer: the input. At the end of computation, the stack must also contain only one integer, which is the result of the computation.
The stack machine will enter an error state in three cases:
A DIV command is attempted when the top-most stack element is .
An ADD, SUB, MUL, or DIV command is attempted when the stack contains only one element.
An operation produces a value greater than or less than (in absolute value).
The input consists of a series of function descriptions. Each description starts with a line containing a single integer (n \leq 10), the number of input/output pairs. The next two lines contain integers each: the first line contains the inputs (all different), and the second line contains the corresponding outputs. All numbers will be at most in absolute value.
The input is terminated by a description with n = 0. This test case should not be processed.
You are to find the shortest program that computes a function , such that f(x_i) = y_i for all i \in \{1, \ldots, n\}. This means that the program must not enter an error state when executed on the given inputs x_i, though it may enter an error state for other inputs. Consider only programs with at most commands.
For each function description, output the description number first. Then output the sequence of commands comprising the shortest program to compute the given function. If there is more than one such program, output the lexicographically smallest one. If there is no program of at most commands that computes the function, output the string "Impossible". If the shortest program consists of zero commands, output "Empty sequence".
Print a blank line after each test case.
Beispiel 1